Transactions on Combinatorics
Volume:1 Issue: 3, Sep 2012

et 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 t(G) = k and t(G + e) = k 􀀀 2 for all e 2 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 nite group with the identity e. The subgroup intersection graph 􀀀SI (G) of G is the graph with vertex set V (􀀀SI (G)) = G􀀀e and two distinct vertices x and y are adjacent in 􀀀SI (G) if and only if j hxi \ hyi j > 1, where hxi is the cyclic subgroup of G generated by x 2 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 nite 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 nding 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) = fL(v): v 2 V g be a prescribed list assignment. G is L-L(2; 1)-colorable if there exists a vertex labeling f of G such that f(v) 2 L(v) for all v 2 V; jf(u) 􀀀 f(v)j  2 if dG(u; v) = 1; and jf(u) 􀀀 f(v)j  1 if dG(u; v) = 2. If G is L-L(2; 1)-colorable for every list assignment L with jL(v)j  k for all v 2 V, then G is said to be k-L(2; 1)-choosable. In this paper, we prove all cycles are 5-L(2; 1)-choosabl

n this paper, we dene the common minimal dominating signed graph of a given signed graph and oer 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 Zn and the edge set E(ICGn(D)) = ffa; bg; gcd(a 􀀀 b; n) 2 Dg. 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 = fp1; p2;: :: ; pkg.