Vizing's conjecture, in graph theory, concerns a relation between the domination number and the Cartesian product of graphs, stating that the domination number of the product is at least the product of the two graphs' domination numbers. It was first stated by Vadim G. Vizing in 1968, and many mathematicians have since worked on it with partial results. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
StatementFor graphs G and H, the domination number of the Cartesian product of G and H is at least the product of the domination numbers of G and H: gamma(G box H) >= gamma(G) gamma(H). 1 Proposed Year Progress Toward ResolutionKnown to hold when either graph has domination number one, for cycles, and for graphs with domination number two; Clark and Suen (2000) proved the domination number of the product is at least half as large as the conjectured bound for all G and H. 1 Classification
Resolution Status Prize Status
Prize Status (category) Connections
In Branch
Source Vizing's Conjecture (Wikipedia)
Sources
1. Vizing's Conjecture (Wikipedia)
Wikimedia FoundationLead section
This conjecture was first stated by Vadim G. Vizing (1968)
Lead section, second sentence
This conjecture was first stated by Vadim G. Vizing (1968), and states that, if γ(G) denotes the minimum number of vertices in a dominating set for the graph G, then
Partial results section
Clark & Suen (2000) proved that the domination number of the product is at least half as large as the conjectured bound, for all G and H.
In Branch: Graph Theory, Lead sentence
In graph theory, Vizing's conjecture concerns a relation between the domination number and the cartesian product of graphs.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.