Vizing's conjecture

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 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").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). Since Vizing proposed this conjecture, many mathematicians have worked on it, with partial results described below. For a more detailed overview of these results, see Imrich and Klavžar (2000).

Examples

A 4-cycle "C"4 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 "C"4 ◻ "C"4 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, γ(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).

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 (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, 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.

References


*cite journal
author = Barcalkin, A. M.; German, L. F.
title = The external stability number of the Cartesian product of graphs
format = In Russian
year = 1979
journal = Bul. Akad. Stiince RSS Moldoven
volume = 1
pages = 5–8
id = MathSciNet | id = 0544028

*cite journal
author = Clark, W. Edwin; Suen, Stephen
title = Inequality related to Vizing's conjecture
journal = Electronic Journal of Combinatorics
url = http://www.combinatorics.org/Volume_7/Abstracts/v7i1n4.html
year = 2000
volume = 7
issue = 1
pages = N4
id = MathSciNet | id = 1763970

*cite journal
author = El-Zahar, M.; Pareek, C. M.
year = 1991
title = Domination number of products of graphs
journal = Ars Combin.
volume = 31
pages = 223–227
id = MathSciNet | id = 1110240

*cite journal
author = Fink, J. F.; Jacobson, M. S.; Kinch, L. F.; Roberts, J.
title = On graphs having domination number half their order
year = 1985
journal = Period. Math. Hungar.
volume = 16
pages = 287–293
id = MathSciNet | id = 0833264
doi = 10.1007/BF01848079

*cite journal
author = Gravier, S.; Khelladi, A.
year = 1995
title = On the domination number of cross products of graphs
journal = Discrete Mathematics
volume = 145
pages = 273–277
id = MathSciNet | id = 1356600
doi = 10.1016/0012-365X(95)00091-A

*cite journal
author = Hartnell, B. L.; Rall, D. F.
title = On Vizing's conjecture
year = 1991
journal = Congr. Numer.
volume = 82
pages = 87–96
id = MathSciNet | id = 1152060

*cite book
author = Imrich, Wilfried; Klavžar, Sandi
title = Product Graphs: Structure and Recognition
publisher = Wiley
year = 2000
isbn = 0-471-37039-8

*cite journal
author = Jacobson, M. S.; Kinch, L. F.
title = On the domination of the products of graphs II: trees
journal = J. Graph Theory
volume = 10
year = 1986
pages = 97–106
id = MathSciNet | id = 0830061
doi = 10.1002/jgt.3190100112

*cite journal
author = Klavžar, Sandi; Zmazek, B.
year = 1996
title = On a Vizing-like conjecture for direct product graphs
journal = Discrete Mathematics
volume = 156
pages = 243–246
id = MathSciNet | id = 1405022
doi = 10.1016/0012-365X(96)00032-5

*cite journal
author = Payan, C.; Xuong, N. H.
title = Domination-balanced graphs
year = 1982
journal = J. Graph Theory
volume = 6
pages = 23–32
id = MathSciNet | id = 0644738
doi = 10.1002/jgt.3190060104

*cite journal
author = Vizing, V. G.
title = Some unsolved problems in graph theory
format = In Russian
journal = Uspehi Mat. Naukno.
volume = 23
year = 1968
issue = 6
pages = 117–134
id = MathSciNet | id = 0240000

External links

*mathworld | title = Vizing Conjecture | urlname = VizingConjecture


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • List of mathematics articles (V) — NOTOC Vac Vacuous truth Vague topology Valence of average numbers Valentin Vornicu Validity (statistics) Valuation (algebra) Valuation (logic) Valuation (mathematics) Valuation (measure theory) Valuation of options Valuation ring Valuative… …   Wikipedia

  • Dominating set — For Dominator in control flow graphs, see Dominator (graph theory). Dominating sets (red vertices). In graph theory, a dominating set for a graph G = (V, E) is a subset D of V such that every vertex not in D is joined to at… …   Wikipedia

  • Edge coloring — A 3 edge coloring of the Desargues graph. In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge… …   Wikipedia

  • Coloration de graphe (arêtes) — Coloration des arêtes d un graphe Coloration des arêtes du graphe de Desargues avec trois couleurs. La coloration des arêtes d’un graphe entre dans la catégorie plus générale des problèmes de coloration de graphes, le but étant d’attribuer une… …   Wikipédia en Français

  • Coloration des aretes d'un graphe — Coloration des arêtes d un graphe Coloration des arêtes du graphe de Desargues avec trois couleurs. La coloration des arêtes d’un graphe entre dans la catégorie plus générale des problèmes de coloration de graphes, le but étant d’attribuer une… …   Wikipédia en Français

  • Coloration des arêtes d'un graphe — Coloration des arêtes du graphe de Desargues avec trois couleurs. La coloration des arêtes d’un graphe entre dans la catégorie plus générale des problèmes de coloration de graphes, le but étant d’attribuer une couleur à chaque arête du graphe… …   Wikipédia en Français

  • Total coloring — [ Proper total coloring of Foster Cage with 6 colors. The total chromatic number of this graph is 6 sincethe degree of each vertex is 5 (5 adjacent edges + 1 vertex=6).] In graph theory, total coloring is a type of coloring on the vertices and… …   Wikipedia

  • Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… …   Wikipedia

  • Cartesian product of graphs — In graph theory, the cartesian product G ◻ H of graphs G and H is a graph such that * the vertex set of G ◻ H is the cartesian product V(G) × V(H) ; and * any two vertices (u,u ) and (v,v ) are adjacent in G ◻ H if and only if either ** u = v and …   Wikipedia

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”