- Tytuł:
- Notes on the independence number in the Cartesian product of graphs
- Autorzy:
-
Abay-Asmerom, G.
Hammack, R.
Larson, C.
Taylor, D. - Powiązania:
- https://bibliotekanauki.pl/articles/744113.pdf
- Data publikacji:
- 2011
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
independence number
Cartesian product
critical independent set
radius
r-ciliate - Opis:
-
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. - Źródło:
-
Discussiones Mathematicae Graph Theory; 2011, 31, 1; 25-35
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł