Geodesic
Notes on the independence number in the Cartesian product of graphs
Discussiones Mathematicae. Graph Theory, Tome 31 (2011) no. 1, pp. 25-35

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: independence number, Cartesian product, critical independent set, radius, r-ciliate 
@article{DMGT_2011_31_1_a1,
     author = {Abay-Asmerom, G. and Hammack, R. and Larson, C. and Taylor, D.},
     title = {Notes on the independence number in the {Cartesian} product of graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {25--35},
     publisher = {mathdoc},
     volume = {31},
     number = {1},
     year = {2011},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2011_31_1_a1/}
}
TY  - JOUR
AU  - Abay-Asmerom, G.
AU  - Hammack, R.
AU  - Larson, C.
AU  - Taylor, D.
TI  - Notes on the independence number in the Cartesian product of graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2011
SP  - 25
EP  - 35
VL  - 31
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2011_31_1_a1/
LA  - en
ID  - DMGT_2011_31_1_a1
ER  - 
%0 Journal Article
%A Abay-Asmerom, G.
%A Hammack, R.
%A Larson, C.
%A Taylor, D.
%T Notes on the independence number in the Cartesian product of graphs
%J Discussiones Mathematicae. Graph Theory
%D 2011
%P 25-35
%V 31
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2011_31_1_a1/
%G en
%F DMGT_2011_31_1_a1
Abay-Asmerom, G.; Hammack, R.; Larson, C.; Taylor, D. Notes on the independence number in the Cartesian product of graphs. Discussiones Mathematicae. Graph Theory, Tome 31 (2011) no. 1, pp. 25-35. http://geodesic.mathdoc.fr/item/DMGT_2011_31_1_a1/