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

Tjaša Paj; Simon Špacapan

Discussiones Mathematicae Graph Theory (2015)

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

Abstract

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

How to cite

top

Tjaš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. [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. [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. [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. [4] L.M. Friedler, The independence number of the Cartesian product of graphs, Ars Combin. 99 (2011) 205-216. Zbl1265.05458
  5. [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. [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. [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. [8] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, Second Edition (CRC Press, Boca Raton, FL, 2011). Zbl1283.05001
  9. [9] P.K. Jha, Further results on independence in direct-product graphs, Ars Combin. 56 (2000) 15-24. Zbl0994.05103
  10. [10] P.K. Jha and S. Klavžar, Independence in direct-product graphs, Ars Combin. 50 (1998) 53-63. Zbl0963.05069
  11. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [23] X. Zhu, A survey on Hedetniemi’s conjecture, Taiwanese J. Math. 2 (1998) 1-24. Zbl0906.05024
  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 [Crossref][WoS] 

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.