Maximum Independent Sets in Direct Products of Cycles or Trees with Arbitrary Graphs

Tjaša Paj ; Simon Špacapan

Discussiones Mathematicae Graph Theory, Tome 35 (2015), p. 675-688 / Harvested from The Polish Digital Mathematics Library

Résumé

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.

Détail

Publié le : 2015-01-01

Zbl 1327.05265

EUDML-ID : urn:eudml:doc:276025

Bibliographie

[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[Crossref]

[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[Crossref] | Zbl 1056.05104

[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[WoS][Crossref] | Zbl 1254.05134

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

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

[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.[WoS][Crossref] | Zbl 1334.05100

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

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

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

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

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

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

[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. | Zbl 1289.05353

[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[Crossref] | Zbl 1003.05077

[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. | Zbl 1243.05207

[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. | Zbl 1237.05156

[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[Crossref] | Zbl 1284.05204

[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[Crossref]

[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[Crossref] | Zbl 1111.05040

[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[Crossref]

[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[Crossref][WoS]

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

[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 [Crossref][WoS]