Adjoining edges to G\mathbin\squareH to construct a minimal dominating set of size γ(G)γ(H)

2021/11/16 by Allan van Hulst, van Hulst, Allan
Computer Science · Mathematics · #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2111.08371

openalex publication_date 2021/11/16 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28

Abstract

For graphs G,H it is possible to add (|V(G)|-γ(G))(|V(H)|-γ(H)) edges to the Cartesian product G\mathbin\squareH such that a minimal dominating set D of size γ(G)γ(H) emerges. We hypothesize that D is also a minimum dominating set for the resulting graph and show that this implies Vizing's conjecture.

Related

• A note on Vizing's conjecture
• A brief, simple proof of Vizing's conjecture
• A Note on Integer Domination of Cartesian Product Graphs
• An improved bound in Vizing's conjecture
• A Note on Total and Paired Domination of Cartesian Product Graphs