Currently displaying 1 – 1 of 1

Showing per page

Order by Relevance | Title | Year of publication

Notes on the independence number in the Cartesian product of graphs

G. Abay-AsmeromR. HammackC.E. LarsonD.T. Taylor — 2011

Discussiones Mathematicae Graph Theory

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...

Page 1

Download Results (CSV)