Vizing's conjecture
In graph theory, the Vizing conjecture concerns a relation between the domination number and the cartesian product of graphs. This conjecture was first stated by V. G. Vizing (1968), and states that, if γ(G) denotes the minimum number of vertices in a dominating set for G, then
- γ(G ◻ H) ≥ γ(G)γ(H).
It is known to hold for cycles (Jacobson and Kinch 1986; El-Zahar and Pareek 1991) and for graphs with domination number two (Barcalkin and German 1979). Clark and Suen (2000) proved that the domination number of the product is at least half as large as the conjectured bound.
It is possible for the domination number of a product to be much larger than the bound given by Vizing's conjecture. For instance, γ(K1,n) = 1 but γ(K1,n ◻ K1,n) = n + 1. However, there exist infinite families of graphs for which the bound of Vizing's conjecture is exactly met (Payan and Xuong 1982; Fink et al 1985; Jacobson and Kinch 1986; Hartnell and Rall 1991).
Gravier and Khelladi (1995) conjectured a similar bound for the domination number of the tensor product of graphs, however a counterexample was found by Klavžar and Zmazek (1996).
Upper bounds
Vizing (1968) observed that
- γ(G ◻ H) ≤ min{γ(G)|V(H)|, γ(H)|V(G)|}.
A dominating set meeting this bound may be formed as the cartesian product of a dominating set in one of G or H with the set of all vertices in the other graph.
References
- Barcalkin, A. M.; German, L. F. (1979). "The external stability number of the Cartesian product of graphs". Bul. Akad. Stiince RSS Moldoven. 1: 5–8.
{{cite journal}}:|format=requires|url=(help)CS1 maint: multiple names: authors list (link)
- Clark, W. Edwin; Suen, Stephen (2000). "Inequality related to Vizing's conjecture". Electronic Journal of Combinatorics. 7 (1): N4.
{{cite journal}}: CS1 maint: multiple names: authors list (link)
- El-Zahar, M.; Pareek, C. M. (1991). "Domination number of products of graphs". Ars Combin. 31: 223–227.
{{cite journal}}: CS1 maint: multiple names: authors list (link)
- Fink, J. F.; Jacobson, M. S.; Kinch, L. F.; Roberts, J. (1985). "On graphs having domination number half their order". Period. Math. Hungar. 16: 287–293.
{{cite journal}}: CS1 maint: multiple names: authors list (link)
- Gravier, S.; Khelladi, A. (1995). "On the domination number of cross products of graphs". Discrete Mathematics. 145: 273–277.
{{cite journal}}: CS1 maint: multiple names: authors list (link)
- Hartnell, B. L.; Rall, D. F. (1991). "On Vizing's conjecture". Congr. Numer. 82: 87–96.
{{cite journal}}: CS1 maint: multiple names: authors list (link)
- Imrich, Wilfried; Klavžar, Sandi (2000). Product Graphs: Structure and Recognition. Wiley. ISBN 0-471-37039-8.
{{cite book}}: CS1 maint: multiple names: authors list (link)
- Jacobson, M. S.; Kinch, L. F. (1986). "On the domination of the products of graphs II: trees". J. Graph Theory. 10: 97–106.
{{cite journal}}: CS1 maint: multiple names: authors list (link)
- Klavžar, Sandi; Zmazek, B. (1996). "On a Vizing-like conjecture for direct product graphs". Discrete Mathematics. 156: 243–246.
{{cite journal}}: CS1 maint: multiple names: authors list (link)
- Payan, C.; Xuong, N. H. (1982). "Domination-balanced graphs". J. Graph Theory. 6: 23–32.
{{cite journal}}: CS1 maint: multiple names: authors list (link)
- Vizing, V. G. (1968). "Some unsolved problems in graph theory". Russ. Math. Surv. 23: 125–141.