Vizing's conjecture
In graph theory, Vizing's conjecture concerns a relation between the domination number and the cartesian product of graphs. This conjecture was first stated by Template:Harvx, and states that, if γ(G) denotes the minimum number of vertices in a dominating set for G, then
- γ(G ◻ H) ≥ γ(G)γ(H).
Gravier & Khelladi (1995) conjectured a similar bound for the domination number of the tensor product of graphs, however a counterexample was found by Klavžar & Zmazek (1996). Since Vizing proposed his conjecture, many mathematicians have worked on it, with partial results described below. For a more detailed overview of these results, see Imrich & Klavžar (2000).
Examples
A 4-cycle C4 has domination number two: any single vertex only dominates itself and its two neighbors, but any pair of vertices dominates the whole graph. The product C4 ◻ C4 is a four-dimensional hypercube graph; it has 16 vertices, and any single vertex can only dominate itself and four neighbors, so four vertices are required to dominate the entire graph, matching the bound given by Vizing's conjecture.
It is possible for the domination number of a product to be much larger than the bound given by Vizing's conjecture. For instance, for a star, γ(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.[1]
Partial results
Clearly, the conjecture holds when either G or H has domination number one: for, the product contains an isomorphic copy of the other factor, dominating which requires at least γ(G)γ(H) vertices.
Vizing's conjecture is also known to hold for cycles[2] and for graphs with domination number two.[3]
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.
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.
Notes
References
- Barcalkin, A. M.; German, L. F. (1979), "The external stability number of the Cartesian product of graphs", Bul. Akad. Stiince RSS Moldoven (in Russian), 1: 5–8, MR0544028.
- Clark, W. Edwin; Suen, Stephen (2000), "Inequality related to Vizing's conjecture", Electronic Journal of Combinatorics, 7 (1): N4, MR1763970.
- El-Zahar, M.; Pareek, C. M. (1991), "Domination number of products of graphs", Ars Combin., 31: 223–227, MR1110240.
- 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, doi:10.1007/BF01848079, MR0833264.
- Gravier, S.; Khelladi, A. (1995), "On the domination number of cross products of graphs", Discrete Mathematics, 145: 273–277, doi:10.1016/0012-365X(95)00091-A, MR1356600.
- Hartnell, B. L.; Rall, D. F. (1991), "On Vizing's conjecture", Congr. Numer., 82: 87–96, MR1152060.
- Imrich, Wilfried; Klavžar, Sandi (2000), Product Graphs: Structure and Recognition, Wiley, ISBN 0-471-37039-8.
- Jacobson, M. S.; Kinch, L. F. (1986), "On the domination of the products of graphs II: trees", J. Graph Theory, 10: 97–106, doi:10.1002/jgt.3190100112, MR0830061.
- Klavžar, Sandi; Zmazek, B. (1996), "On a Vizing-like conjecture for direct product graphs", Discrete Mathematics, 156: 243–246, doi:10.1016/0012-365X(96)00032-5, MR1405022.
- Payan, C.; Xuong, N. H. (1982), "Domination-balanced graphs", J. Graph Theory, 6: 23–32, doi:10.1002/jgt.3190060104, MR0644738.
- Vizing, V. G. (1968), "Some unsolved problems in graph theory", Uspehi Mat. Naukno. (in Russian), 23 (6): 117–134, MR0240000.