Notes on the independence number in the Cartesian product of graphs

G. Abay-Asmerom; R. Hammack; C.E. Larson; D.T. Taylor

Discussiones Mathematicae Graph Theory (2011)

  • Volume: 31, Issue: 1, page 25-35
  • ISSN: 2083-5892

Abstract

top
Every connected graph G with radius r(G) and independence number α(G) obeys α(G) ≥ r(G). Recently the graphs for which equality holds have been classified. Here we investigate the members of this class that are Cartesian products. We show that for non-trivial graphs G and H, α(G ☐ H) = r(G ☐ H) if and only if one factor is a complete graph on two vertices, and the other is a nontrivial complete graph. We also prove a new (polynomial computable) lower bound α(G ☐ H) ≥ 2r(G)r(H) for the independence number and we classify graphs for which equality holds. The second part of the paper concerns independence irreducibility. It is known that every graph G decomposes into a König-Egervary subgraph (where the independence number and the matching number sum to the number of vertices) and an independence irreducible subgraph (where every non-empty independent set I has more than |I| neighbors). We examine how this decomposition relates to the Cartesian product. In particular, we show that if one of G or H is independence irreducible, then G ☐ H is independence irreducible.

How to cite

top

G. Abay-Asmerom, et al. "Notes on the independence number in the Cartesian product of graphs." Discussiones Mathematicae Graph Theory 31.1 (2011): 25-35. <http://eudml.org/doc/270895>.

@article{G2011,
abstract = { Every connected graph G with radius r(G) and independence number α(G) obeys α(G) ≥ r(G). Recently the graphs for which equality holds have been classified. Here we investigate the members of this class that are Cartesian products. We show that for non-trivial graphs G and H, α(G ☐ H) = r(G ☐ H) if and only if one factor is a complete graph on two vertices, and the other is a nontrivial complete graph. We also prove a new (polynomial computable) lower bound α(G ☐ H) ≥ 2r(G)r(H) for the independence number and we classify graphs for which equality holds. The second part of the paper concerns independence irreducibility. It is known that every graph G decomposes into a König-Egervary subgraph (where the independence number and the matching number sum to the number of vertices) and an independence irreducible subgraph (where every non-empty independent set I has more than |I| neighbors). We examine how this decomposition relates to the Cartesian product. In particular, we show that if one of G or H is independence irreducible, then G ☐ H is independence irreducible. },
author = {G. Abay-Asmerom, R. Hammack, C.E. Larson, D.T. Taylor},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {independence number; Cartesian product; critical independent set; radius; r-ciliate; -ciliate},
language = {eng},
number = {1},
pages = {25-35},
title = {Notes on the independence number in the Cartesian product of graphs},
url = {http://eudml.org/doc/270895},
volume = {31},
year = {2011},
}

TY - JOUR
AU - G. Abay-Asmerom
AU - R. Hammack
AU - C.E. Larson
AU - D.T. Taylor
TI - Notes on the independence number in the Cartesian product of graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2011
VL - 31
IS - 1
SP - 25
EP - 35
AB - Every connected graph G with radius r(G) and independence number α(G) obeys α(G) ≥ r(G). Recently the graphs for which equality holds have been classified. Here we investigate the members of this class that are Cartesian products. We show that for non-trivial graphs G and H, α(G ☐ H) = r(G ☐ H) if and only if one factor is a complete graph on two vertices, and the other is a nontrivial complete graph. We also prove a new (polynomial computable) lower bound α(G ☐ H) ≥ 2r(G)r(H) for the independence number and we classify graphs for which equality holds. The second part of the paper concerns independence irreducibility. It is known that every graph G decomposes into a König-Egervary subgraph (where the independence number and the matching number sum to the number of vertices) and an independence irreducible subgraph (where every non-empty independent set I has more than |I| neighbors). We examine how this decomposition relates to the Cartesian product. In particular, we show that if one of G or H is independence irreducible, then G ☐ H is independence irreducible.
LA - eng
KW - independence number; Cartesian product; critical independent set; radius; r-ciliate; -ciliate
UR - http://eudml.org/doc/270895
ER -

References

top
  1. [1] B. Bresar and B. Zmazek, On the Independence Graph of a Graph, Discrete Math. 272 (2003) 263-268, doi: 10.1016/S0012-365X(03)00194-8. Zbl1028.05073
  2. [2] S. Butenko and S. Trukhanov, Using Critical Sets to Solve the Maximum Independent Set Problem, Operations Research Letters 35 (2007) 519-524. Zbl1149.90375
  3. [3] E. DeLaVina, C.E. Larson, R. Pepper and B. Waller, A Characterization of Graphs Where the Independence Number Equals the Radius, submitted, 2009. Zbl1256.05164
  4. [4] P. Erdös, M. Saks and V. Sós, Maximum Induced Trees in Graphs, J. Combin. Theory (B) 41 (1986) 61-69, doi: 10.1016/0095-8956(86)90028-6. 
  5. [5] S. Fajtlowicz, A Characterization of Radius-Critical Graphs, J. Graph Theory 12 (1988) 529-532, doi: 10.1002/jgt.3190120409. Zbl0713.05037
  6. [6] S. Fajtlowicz, Written on the Wall: Conjectures of Graffiti, available on the WWW at: http://www.math.uh.edu/clarson/graffiti.html. 
  7. [7] M. Garey and D. Johnson, Computers and Intractability (W.H. Freeman and Company, New York, 1979). 
  8. [8] J. Hagauer and S. Klavžar, On Independence Numbers of the Cartesian Product of Graphs, Ars. Combin. 43 (1996) 149-157. Zbl0881.05061
  9. [9] P. Hell, X. Yu and H. Zhou, Independence Ratios of Graph Powers, Discrete Math. 127 (1994) 213-220, doi: 10.1016/0012-365X(92)00480-F. Zbl0795.05054
  10. [10] W. Imrich and S. Klavžar, Product Graphs (Wiley-Interscience, New York, 2000). 
  11. [11] W. Imrich, S. Klavžar and D. Rall, Topics in Graph Theory: Graphs and their Cartesian Product, A K Peters (Wellesley, MA, 2008). Zbl1156.05001
  12. [12] P.K. Jha and G. Slutzki, Independence Numbers of Product Graphs, Appl. Math. Lett. 7 (1994) 91-94, doi: 10.1016/0893-9659(94)90018-3. Zbl0811.05033
  13. [13] 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
  14. [14] C.E. Larson, A Note on Critical Independent Sets, Bulletin of the Institute of Combinatorics and its Applications 51 (2007) 34-46. Zbl1135.05051
  15. [15] C.E. Larson, Graph Theoretic Independence and Critical Independent Sets, Ph.D. Dissertation (University of Houston, 2008). 
  16. [16] C.E. Larson, The Critical Independence Number and an Independence Decomposition, submitted, 2009 (available at www.arxiv.org: arXiv:0912.2260v1). Zbl1230.05226
  17. [17] L. Lovász and M.D. Plummer, Matching Theory (North Holland, Amsterdam, 1986). 
  18. [18] M.P. Scott, J.S. Powell and D.F. Rall, On the Independence Number of the Cartesian Product of Caterpillars, Ars Combin. 60 (2001) 73-84. Zbl1071.05554
  19. [19] C.-Q. Zhang, Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems, SIAM J. Discrete Math. 3 (1990) 431-438, doi: 10.1137/0403037. Zbl0756.05095

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.