# 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

## Access Full Article

top## Abstract

top## How to cite

topG. 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] 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] 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] 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] 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] S. Fajtlowicz, A Characterization of Radius-Critical Graphs, J. Graph Theory 12 (1988) 529-532, doi: 10.1002/jgt.3190120409. Zbl0713.05037
- [6] S. Fajtlowicz, Written on the Wall: Conjectures of Graffiti, available on the WWW at: http://www.math.uh.edu/clarson/graffiti.html.
- [7] M. Garey and D. Johnson, Computers and Intractability (W.H. Freeman and Company, New York, 1979).
- [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] 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] W. Imrich and S. Klavžar, Product Graphs (Wiley-Interscience, New York, 2000).
- [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] 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] 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] 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] C.E. Larson, Graph Theoretic Independence and Critical Independent Sets, Ph.D. Dissertation (University of Houston, 2008).
- [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] L. Lovász and M.D. Plummer, Matching Theory (North Holland, Amsterdam, 1986).
- [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] 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

## Citations in EuDML Documents

top## NotesEmbed ?

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