Geodesic
Maximum Independent Sets in Direct Products of Cycles or Trees with Arbitrary Graphs
Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 4, pp. 675-688.

Voir la notice de l'article provenant de la source Library of Science

The direct product of graphs G = (V (G), E(G)) and H = (V (H), E(H)) is the graph, denoted as G×H, with vertex set V (G×H) = V (G)×V (H), where vertices (x1, y1) and (x2, y2) are adjacent in G × H if x1x2 ∈ E(G) and y1y2 ∈ E(H). Let n be odd and m even. We prove that every maximum independent set in Pn×G, respectively Cm×G, is of the form (A×C)∪(B×D), where C and D are nonadjacent in G, and A∪B is the bipartition of Pn respectively Cm. We also give a characterization of maximum independent subsets of Pn × G for every even n and discuss the structure of maximum independent sets in T × G where T is a tree.
Keywords: direct product, independent set 
@article{DMGT_2015_35_4_a6,
     author = {Paj, Tja\v{s}a and \v{S}pacapan, Simon},
     title = {Maximum {Independent} {Sets} in {Direct} {Products} of {Cycles} or {Trees} with {Arbitrary} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {675--688},
     publisher = {mathdoc},
     volume = {35},
     number = {4},
     year = {2015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a6/}
}
TY  - JOUR
AU  - Paj, Tjaša
AU  - Špacapan, Simon
TI  - Maximum Independent Sets in Direct Products of Cycles or Trees with Arbitrary Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2015
SP  - 675
EP  - 688
VL  - 35
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a6/
LA  - en
ID  - DMGT_2015_35_4_a6
ER  - 
%0 Journal Article
%A Paj, Tjaša
%A Špacapan, Simon
%T Maximum Independent Sets in Direct Products of Cycles or Trees with Arbitrary Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2015
%P 675-688
%V 35
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a6/
%G en
%F DMGT_2015_35_4_a6
Paj, Tjaša; Špacapan, Simon. Maximum Independent Sets in Direct Products of Cycles or Trees with Arbitrary Graphs. Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 4, pp. 675-688. http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a6/

[1] G. Abay-Asmerom, R. Hammack, C.E. Larson and D.T. Taylor, Notes on the inde- pendence number in the Cartesian product of graphs, Discuss. Math. Graph Theory 31 (2011) 25-35. doi:10.7151/dmgt.1527

[2] N. Alon, I. Dinur, E. Friedgut and B. Sudakov, Graph products, Fourier analysis and spectral techniques, Geom. Funct. Anal. 14 (2004) 913-940. doi:10.1007/s00039-004-0478-3

[3] S.H. Badalyan and S.E. Markosyan, On the independence number of the strong product of cycle-powers, Discrete Math. 313 (2013) 105-110. doi:10.1016/j.disc.2012.09.008

[4] L.M. Friedler, The independence number of the Cartesian product of graphs, Ars Combin. 99 (2011) 205-216.

[5] D. Greenwell and L. Lovász, Applications of product colouring, Acta Math. Acad. Sci. Hungar. 25 (1974) 335-340. doi:/10.1007/BF01886093

[6] X.B. Geng, J. Wang and H. Zhang, Structure of independent sets in direct products of some vertex-transitive graphs, Acta Math. Sin. (Engl. Ser.) 28 (2012) 697-706.

[7] J. Hagauer and S. Klavžar, On independence numbers of the Cartesian product of graphs, Ars Combin. 43 (1996) 149-157.

[8] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, Second Edition (CRC Press, Boca Raton, FL, 2011).

[9] P.K. Jha, Further results on independence in direct-product graphs, Ars Combin. 56 (2000) 15-24.

[10] P.K. Jha and S. Klavžar, Independence in direct-product graphs, Ars Combin. 50 (1998) 53-63.

[11] S. Klavžar, Some new bounds and exact results on the independence number of Cartesian product graphs, Ars Combin. 74 (2005) 173-186.

[12] A. Klobučar, Independent sets and independent dominating sets in the strong product of paths and cycles, Math. Commun. 10 (2005) 23-30.

[13] D. Korže and A. Vesel, A note on the independence number of strong products of odd cycles, Ars Combin. 106 (2012) 473-481.

[14] B. Larose and C. Tardif, Projectivity and independent sets in powers of graphs, J. Graph Theory 40 (2002) 162-171. doi:10.1002/jgt.10041

[15] S.P. Martin, J.S. Powell and D.F. Rall, On the independence number of the Carte- sian product of caterpillars, Ars Combin. 60 (2001) 73-84.

[16] T. Sitthiwirattham, Independent and vertex covering number on Kronecker product of Pn, Int. J. Pure Appl. Math. 73 (2011) 227-234.

[17] T. Sitthiwirattham and J. Soontharanon, Independent and vertex covering number on Kronecker product of Cn, Int. J. Pure Appl. Math. 71 (2011) 149-157.

[18] S. Špacapan, The k-independence number of direct products of graphs and Hedet- niemi’s conjecture, European J. Combin. 32 (2011) 1377-1383. doi:10.1016/j.ejc.2011.07.002

[19] C. Tardif, Graph products and the chromatic difference sequence of vertex-transitive graphs, Discrete Math. 185 (1998) 193-200. doi:10.1016/S0012-365X(97)00171-4

[20] M. Valencia-Pabon and J. Vera, Independence and coloring properties of direct prod- ucts of some vertex-transitive graphs, Discrete Math. 306 (2006) 2275-2281. doi:10.1016/j.disc.2006.04.013

[21] H. Zhang, Independent sets in direct products of vertex-transitive graphs, J. Combin. Theory Ser. B 102 (2012) 832-838. doi:10.1016/j.jctb.2011.12.005

[22] H. Zhang, Primitivity and independent sets in direct products of vertex-transitive graphs, J. Graph Theory 67 (2011) 218-225. doi:10.1002/jgt.20526

[23] X. Zhu, A survey on Hedetniemi’s conjecture, Taiwanese J. Math. 2 (1998) 1-24.

[24] X. Zhu, The fractional version of Hedetniemi’s conjecture is true, European J. Com- bin. 32 (2011) 1168-1175. doi:10.1016/j.ejc.2011.03.004