TRANSACTIONS ON COMBINATORICS
Year:2012 | Volume:1 | Issue:3|Papers Count:6

Let G be a connected spanning subgraph of Ks,s and let H be the complement of G relative to Ks,s. The graph G is k-supercritical relative to Ks,s if gt (G) =k and gt (G+e) =k-2 for all eÎE (H). The 2002 paper by T.W. Haynes, M.A. Henning and L.C. van der Merwe, \Total domination supercritical graphs with respect to relative complements" that appeared in Discrete Mathematics, 258 (2002), 361-371, presents a theorem (Theorem 11) to produce (2k+2) -supercritical graphs relative to K2k+1, 2k+1 of diameter 5, for each k³2. However, the families of graphs in their proof are not the case. We present a correction of this theorem.

Let G be a finite group with the identity e. The subgroup intersection graph  GSI (G) of G is the graph with vertex set V (GSI (G)) =G-e and two distinct vertices x and y are adjacent in GSI (G) if and only if |áxñՈáyñ|>1, where áxñ is the cyclic subgroup of G generated by xÎG. In this paper, we obtain a lower bound for the independence number of subgroup intersection graph. We characterize certain classes of subgroup intersection graphs corresponding to finite abelian groups. Finally, we characterize groups whose automorphism group is the same as that of its subgroup intersection graph.

In this paper, we investigate a problem of finding natural condition to assure the product of two graphs to be hamilton-connected. We present some sucient and necessary conditions for GH being hamilton-connected when G is a hamilton-connected graph and H is a tree or G is a Hamiltonian graph and H is K2.

For a given graph G = (V, E), let L (G) =  {L (u):  u Î V } be a prescribed list assignment. G is L-L(2, 1)-colorable if there exists a vertex labeling f of G such that f (u) Î L(u) for all u Î V; |f (u)-f (u)|³2 if dG(u, u) = 1; and |f (u)-f (u)|³1 if dG (u, u) = 2. If G is L-L (2, 1)-colorable for every list assignment L with |L(u)|³k for all u Î V, then G is said to be k-L(2, 1)-choosable. In this paper, we prove all cycles are 5-L (2, 1)-choosable.

In this paper, we dene the common minimal dominating signed graph of a given signed graph and offer a structural characterization of common minimal dominating signed graphs. In the sequel, we also obtained switching equivalence characterizations: S¯ ~ CMD (S) and CMD(S) ~ N (S), where S¯, CMD (S) and N (S) are complementary signed graph, common minimal signed graph and neighborhood signed graph of S respectively.

A graph is called circulant if it is a Cayley graph on a cyclic group, i.e. its adjacency matrix is circulant. Let D be a set of positive, proper divisors of the integer n > 1. The integral circulant graph ICGn (D) has the vertex set Z n and the edge set E (ICGn (D)) = {{a, b}; gcd (a – b, n) Î D}. Let n = p1p2….pkm, where p1, p2, …., pk are distinct prime numbers and gcd (p1p2…pk, m) = 1. The open problem posed in paper [A. Ilic, The energy of unitary Cayley graphs, Linear Algebra Appl., 431 (2009) 1881-1889] about calculating the energy of an arbitrary integral circulant ICGn (D) is completely solved in this paper, where D = {p1, p2, …., pk}.