Vizing’s conjecture for chordal graphs |
| |
Authors: | Ron Aharoni |
| |
Affiliation: | a Department of Mathematics, Technion, Haifa 32000, Israel b Department of Computer Science, ETH, Zurich, Switzerland |
| |
Abstract: | Vizing conjectured that γ(G□H)≥γ(G)γ(H) for every pair G,H of graphs, where “□” is the Cartesian product, and γ(G) is the domination number of the graph G. Denote by γi(G) the maximum, over all independent sets I in G, of the minimal number of vertices needed to dominate I. We prove that γ(G□H)≥γi(G)γ(H). Since for chordal graphs γi=γ, this proves Vizing’s conjecture when G is chordal. |
| |
Keywords: | Graph theory Domination Vizing&rsquo s conjecture |
本文献已被 ScienceDirect 等数据库收录! |
|