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

Discussiones Mathematicae Graph Theory (2015)

- Volume: 35, Issue: 4, page 675-688
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topTjaša Paj, and Simon Špacapan. "Maximum Independent Sets in Direct Products of Cycles or Trees with Arbitrary Graphs." Discussiones Mathematicae Graph Theory 35.4 (2015): 675-688. <http://eudml.org/doc/276025>.

@article{TjašaPaj2015,

abstract = {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.},

author = {Tjaša Paj, Simon Špacapan},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {direct product; independent set},

language = {eng},

number = {4},

pages = {675-688},

title = {Maximum Independent Sets in Direct Products of Cycles or Trees with Arbitrary Graphs},

url = {http://eudml.org/doc/276025},

volume = {35},

year = {2015},

}

TY - JOUR

AU - Tjaša Paj

AU - Simon Špacapan

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

JO - Discussiones Mathematicae Graph Theory

PY - 2015

VL - 35

IS - 4

SP - 675

EP - 688

AB - 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.

LA - eng

KW - direct product; independent set

UR - http://eudml.org/doc/276025

ER -

## References

top- [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] Zbl1056.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] Zbl1254.05134
- [4] L.M. Friedler, The independence number of the Cartesian product of graphs, Ars Combin. 99 (2011) 205-216. Zbl1265.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 Zbl0294.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] Zbl1334.05100
- [7] J. Hagauer and S. Klavžar, On independence numbers of the Cartesian product of graphs, Ars Combin. 43 (1996) 149-157. Zbl0881.05061
- [8] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, Second Edition (CRC Press, Boca Raton, FL, 2011). Zbl1283.05001
- [9] P.K. Jha, Further results on independence in direct-product graphs, Ars Combin. 56 (2000) 15-24. Zbl0994.05103
- [10] P.K. Jha and S. Klavžar, Independence in direct-product graphs, Ars Combin. 50 (1998) 53-63. Zbl0963.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. Zbl1076.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. Zbl1073.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. Zbl1289.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] Zbl1003.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. Zbl1243.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. Zbl1237.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] Zbl1284.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] Zbl1111.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. Zbl0906.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]

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.