Transactions on Combinatorics
Volume:1 Issue: 4, Dec 2012

Let G = (V;E) be a simple graph of order n and size m. An r-matching of G is a set of r edges of G which no two of them have common vertex. The Hosoya index Z(G) of a graph G is defined as the total number of its matchings. An independent set of G is a set of vertices where no two vertices are adjacent. The Merriffield-Simmons index of G is de¯ned as the total number of the independent sets of G. In this paper we obtain Hosoya and Merrifield-Simmons indices of corona of some graphs.

We study the set of all determinants of adjacency matrices of graphs with a given number of vertices. Using Brendan McKay''s data base of small graphs, determinants of graphs with at most $9$ vertices are computed so that the number of non-isomorphic graphs with given vertices whose determinants are all equal to a number is exhibited in a table. Using an idea of M. Newman, it is proved that if $G$ is a graph with $n$ vertices and ${d_1,dots,d_n}$ is the set of vertex degrees of $G$, then $gcd(2m,d^2)$ divides the determinant of the adjacency matrix of $G$, where $d=gcd(d_1,dots,d_n)$. Possible determinants of adjacency matrices of graphs with exactly two cycles are obtained.

The first ($Pi_1$) and the second $(Pi_2$) multiplicative Zagreb indices of a connected graph $G$, with vertex set $V(G)$ and edge set $E(G)$, are defined as $Pi_1(G) = prod_{u in V(G)} {d_u}^2$ and $Pi_2(G) = prod_{uv in E(G)} {d_u}d_{v}$, respectively, where ${d_u}$ denotes the degree of the vertex $u$. In this paper we present a simple approach to order these indices for connected graphs on the same number of vertices. Moreover, as an application of this simple approach, we extend the known ordering of the first and the second multiplicative Zagreb indices for some classes of connected graphs.

Let G = (V, E) be a graph with p vertices and q edges. An acyclic graphoidal cover of G is a collection of paths in G which are internallydisjoint and covering each edge of the graph exactly once. Let f: V! {1, 2,. .. , p} be a bijective labeling of the vertices of G. Let «Gf be the directed graph obtained by rienting the edges uv of G from u to v provided f (u) < f (v). If the set f of all maximal directed paths in»Gf, with directions ignored, is an acyclic graphoidal cover of G, then f is called a graphoidal labeling of G and G s called a label graphoidal graph and l = min {| f |: f is a graphoidal labeling of G} is called the label graphoidal covering number of G. In this paper we characterize graphs for which (i) l = q − m, where m is the number of vertices of degree 2 and (ii) l = q. Also, we determine the value of label raphoidal covering number for unicyclic graphs.

Let $n,t_1,...,t_k$ be distinct positive integers. A Toeplitz graph $G=(V, E)$ denoted by $T_n$ is a graph, where $V ={1,...,n}$ and $E= {(i,j): |i-j| in {t_1,...,t_k}}$.In this paper, we present some results on decomposition of Toeplitz graphs.

Hansen et. al., using the AutoGraphiX software package, conjectured that the Szeged index Sz(G) and the Wiener index W(G) of a connected bipartite graph G with n ≥ 4 vertices and m ≥ n edges, obeys the relation Sz(G) − W(G) ≥ 4n − 8. Moreover, this bound would be the best possible. This paper offers a proof to this conjecture.

The Hosoya index and the Merrifield-Simmons index are two types of graph invariants used in mathematical chemistry. In this paper, we give some formulas for computed these indices for some classes of corona product and link of two graphs. Furthermore, we obtain exact formulas of hosoya and Merrifield-Simmons indices for the set of bicyclic graphs, caterpillars and dual star.