Discussiones Mathematicae Graph Theory 31(1) (2011)
25-35
doi: 10.7151/dmgt.1527
G. Abay-Asmerom, R. Hammack, C.E. Larson and D.T. Taylor
Department of Mathematics and Applied Mathematics
Virginia Commonwealth University
Richmond, VA 23284, USA
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.
Keywords: independence number, Cartesian product, critical independent set, radius, r-ciliate.
2010 Mathematics Subject Classification: 05C69.
[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. |
[2] | S. Butenko and S. Trukhanov, Using Critical Sets to Solve the Maximum Independent Set Problem, Operations Research Letters 35 (2007) 519-524. |
[3] | E. DeLaVina, C.E. Larson, R. Pepper and B. Waller, A Characterization of Graphs Where the Independence Number Equals the Radius, submitted, 2009. |
[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. |
[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. |
[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. |
[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). |
[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. |
[13] | S. Klavžar, Some New Bounds and Exact Results on the Independence Number of Cartesian Product Graphs, Ars Combin. 74 (2005) 173-186. |
[14] | C.E. Larson, A Note on Critical Independent Sets, Bulletin of the Institute of Combinatorics and its Applications 51 (2007) 34-46. |
[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). |
[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. |
[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. |
Received 27 July 2009
Revised 10 March 2010
Accepted 11 March 2010