TRANSACTIONS ON COMBINATORICS
Year:2012 | Volume:1 | Issue:4|Papers Count:7

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 Merrifield-Simmons index of G is defined 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 deter- minants are all equal to a number is exhibited in a table. Using an idea of M. Newman, it is proved that ifG is a graph with n vertices, m edges and { d1, …, dn} is the set of vertex degrees of G, then gcd (2m, d2) divides the determinant of the adjacency matrix of G, where d=gcd (d1, …, dn). Possible determinants of adjacency matrices of graphs with exactly two cycles are obtained.

The first (P1) and the second (P2) multiplicative Zagreb indices of a connected graph G, with vertex set V(G) and edge set E(G), are defined as P1(G)=PuÎV(G) du2 and P2(G)=PuvÎE(G) dudv, respectively, where du 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 y of paths in G which are internally-disjoint and cover 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 orienting the edgesuv of G from u to v provided f(u)<f(v). If the set yf 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 is called a label graphoidal graph and  hi=min {½yf½: 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) hi=q-m, where m is the number of vertices of degree 2 and (ii) hi=q. Also, we determine the value of label graphoidal covering number for unicyclic graphs.

Let n, t1, …, tk be distinct positive integers. A Toeplitz graph G=(V, E) is a graph with V={1, …, n} and E={(i, j)½½i-j½Î{t1, …, tk}}. 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 to compute 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.