Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2015 | 35 | 4 | 675-688
Tytuł artykułu

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

Treść / Zawartość
Warianty tytułu
Języki publikacji
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.
Słowa kluczowe
Opis fizyczny
  • University of Maribor, FME Smetanova 17 2000 Maribor, Slovenia,
  • [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]
  • [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]
  • [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.[WoS][Crossref]
  • [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[Crossref]
  • [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[Crossref]
  • [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]
  • [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.
  • [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]
Typ dokumentu
Identyfikator YADDA
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.