Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Notes on the independence number in the Cartesian product of graphs

100%

Abay-Asmerom G., Hammack R., Larson C., Taylor D.

Discussiones Mathematicae Graph Theory

2011

tom 31

nr 1

25-35

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.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Abay-Asmerom G.

1 Hammack R.

1 Larson C.

1 Taylor D.

1 2011

Wyniki wyszukiwania

Notes on the independence number in the Cartesian product of graphs