Vizing's conjecture

<h2 id="examples">Examples</h2>

A 4-<a href="/facts/Cycle_graph/bYhnPDHc">cycle</a> 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 <a href="/facts/Hypercube_graph/pwfGEl9J">hypercube graph</a>; it has 16 vertices, and any single vertex can only dominate itself and four neighbors, so three vertices could only dominate 15 of the 16 vertices. Therefore, at least four vertices are required to dominate the entire graph, 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 <a href="/facts/Star_(graph_theory)/PNW0H6eK">star</a> K1,n, its domination number γ(K1,n) is one: it is possible to dominate the entire star with a single vertex at its hub. Therefore, for the graph G = K1,n □ K1,n formed as the product of two stars, Vizing's conjecture states only that the domination number should be at least 1 × 1 = 1. However, the domination number of this graph is actually much higher. It has n2 + 2n + 1 vertices: n2 formed from the product of a leaf in both factors, 2n from the product of a leaf in one factor and the hub in the other factor, and one remaining vertex formed from the product of the two hubs. Each leaf-hub product vertex in G dominates exactly n of the leaf-leaf vertices, so n leaf-hub vertices are needed to dominate all of the leaf-leaf vertices. However, no leaf-hub vertex dominates any other such vertex, so even after n leaf-hub vertices are chosen to be included in the dominating set, there remain n more undominated leaf-hub vertices, which can be dominated by the single hub-hub vertex. Thus, the domination number of this graph is γ(K1,n □ K1,n) = n + 1 far higher than the trivial bound of one given by Vizing's conjecture.
There exist infinite families of graph products for which the bound of Vizing's conjecture is exactly met.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a> For instance, if G and H are both connected graphs, each having at least four vertices and having exactly twice as many total vertices as their domination numbers, then γ(G □ H) = γ(G) γ(H).<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> The graphs G and H with this property consist of the four-vertex cycle C4 together with the <a href="/facts/Rooted_product_of_graphs/JDMRjjD0">rooted products</a> of a connected graph and a single edge.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>

<h2 id="partial-results">Partial results</h2>
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<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> and for graphs with domination number two.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>
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.

<h2 id="upper-bounds">Upper bounds</h2>
Vizing (1968) observed that

γ
        (
        G
        
        ◻
        
        H
        )
        ≤
        min
        {
        γ
        (
        G
        )
        
          |
        
        V
        (
        H
        )
        
          |
        
        ,
        γ
        (
        H
        )
        
          |
        
        V
        (
        G
        )
        
          |
        
        }
        .
      
    
    {\displaystyle \gamma (G\,\Box \,H)\leq \min\{\gamma (G)|V(H)|,\gamma (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.

<h2 id="notes">Notes</h2>

<ul><li>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, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0544028">0544028</a>.</li>
<li>Brešar, Boštjan; Dorbec, Paul; Goddard, Wayne; Hartnell, Bert L.; Henning, Michael A.; Klavžar, Sandi; Rall, Douglas F. (2012), "Vizing's conjecture: a survey and recent results", <a href="/facts/Journal_of_Graph_Theory/p2B4HmcQ">Journal of Graph Theory</a>, 69 (1): 46–76, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1002%2Fjgt.20565">10.1002/jgt.20565</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2864622">2864622</a>.</li>
<li>Clark, W. Edwin; Suen, Stephen (2000), <a href="http://www.combinatorics.org/Volume_7/Abstracts/v7i1n4.html">"Inequality related to Vizing's conjecture"</a>, Electronic Journal of Combinatorics, 7 (1): N4, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.37236%2F1542">10.37236/1542</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1763970">1763970</a>.</li>
<li>El-Zahar, M.; Pareek, C. M. (1991), "Domination number of products of graphs", <a href="/facts/Ars_Combinatoria_(journal)/g86yo1Wy">Ars Combinatoria</a>, 31: 223–227, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1110240">1110240</a>.</li>
<li>Fink, J. F.; Jacobson, M. S.; Kinch, L. F.; Roberts, J. (1985), "On graphs having domination number half their order", Period. Math. Hungar., 16 (4): 287–293, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF01848079">10.1007/BF01848079</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0833264">0833264</a>.</li>
<li>Gravier, S.; Khelladi, A. (1995), "On the domination number of cross products of graphs", <a href="/facts/Discrete_Mathematics_(journal)/K4e6z8wQ">Discrete Mathematics</a>, 145 (1–3): 273–277, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0012-365X%2895%2900091-A">10.1016/0012-365X(95)00091-A</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1356600">1356600</a>.</li>
<li>Hartnell, B. L.; Rall, D. F. (1991), "On Vizing's conjecture", Congr. Numer., 82: 87–96, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1152060">1152060</a>.</li>
<li>Jacobson, M. S.; Kinch, L. F. (1986), "On the domination of the products of graphs II: trees", <a href="/facts/Journal_of_Graph_Theory/p2B4HmcQ">Journal of Graph Theory</a>, 10: 97–106, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1002%2Fjgt.3190100112">10.1002/jgt.3190100112</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0830061">0830061</a>.</li>
<li>Klavžar, Sandi; Zmazek, B. (1996), "On a Vizing-like conjecture for direct product graphs", <a href="/facts/Discrete_Mathematics_(journal)/K4e6z8wQ">Discrete Mathematics</a>, 156 (1–3): 243–246, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0012-365X%2896%2900032-5">10.1016/0012-365X(96)00032-5</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1405022">1405022</a>.</li>
<li>Payan, C.; Xuong, N. H. (1982), "Domination-balanced graphs", <a href="/facts/Journal_of_Graph_Theory/p2B4HmcQ">Journal of Graph Theory</a>, 6: 23–32, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1002%2Fjgt.3190060104">10.1002/jgt.3190060104</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0644738">0644738</a>.</li>
<li><a href="/facts/Vadim_G._Vizing/oHwYWIsH">Vizing, V. G.</a> (1968), "Some unsolved problems in graph theory", Uspekhi Mat. Nauk (in Russian), 23 (6): 117–134, <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/1968RuMaS..23..125V">1968RuMaS..23..125V</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1070%2FRM1968v023n06ABEH001252">10.1070/RM1968v023n06ABEH001252</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0240000">0240000</a>.</li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="/facts/Eric_W._Weisstein/FbMuVDep">Weisstein, Eric W.</a> <a href="https://mathworld.wolfram.com/VizingConjecture.html">"Vizing Conjecture"</a>. <a href="/facts/MathWorld/yc1jodbq">MathWorld</a>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Payan & Xuong (1982); Fink et al. (1985); Jacobson & Kinch (1986); Hartnell & Rall (1991). - Payan, C.; Xuong, N. H. (1982), "Domination-balanced graphs", Journal of Graph Theory, 6: 23–32, doi:10.1002/jgt.3190060104, MR 0644738 <a href="https://doi.org/10.1002%2Fjgt.3190060104" target="_blank">https://doi.org/10.1002%2Fjgt.3190060104</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Fink et al. (1985). - Fink, J. F.; Jacobson, M. S.; Kinch, L. F.; Roberts, J. (1985), "On graphs having domination number half their order", Period. Math. Hungar., 16 (4): 287–293, doi:10.1007/BF01848079, MR 0833264 <a href="https://doi.org/10.1007%2FBF01848079" target="_blank">https://doi.org/10.1007%2FBF01848079</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Fink et al. (1985). - Fink, J. F.; Jacobson, M. S.; Kinch, L. F.; Roberts, J. (1985), "On graphs having domination number half their order", Period. Math. Hungar., 16 (4): 287–293, doi:10.1007/BF01848079, MR 0833264 <a href="https://doi.org/10.1007%2FBF01848079" target="_blank">https://doi.org/10.1007%2FBF01848079</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Jacobson & Kinch (1986); El-Zahar & Pareek (1991). - Jacobson, M. S.; Kinch, L. F. (1986), "On the domination of the products of graphs II: trees", Journal of Graph Theory, 10: 97–106, doi:10.1002/jgt.3190100112, MR 0830061 <a href="https://doi.org/10.1002%2Fjgt.3190100112" target="_blank">https://doi.org/10.1002%2Fjgt.3190100112</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Barcalkin & German (1979). - 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, MR 0544028 <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0544028" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0544028</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
</ol>

Vizing's conjecture open-in-new

Vizing's conjecture