Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ Discussiones Mathema...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Discussiones Mathematicae Graph Theory
Article . 1995 . Peer-reviewed
Data sources: Crossref
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article . 1995
Data sources: zbMATH Open
DBLP
Article . 2023
Data sources: DBLP
versions View all 3 versions
addClaim

Vizing's conjecture and the one-half argument

Authors: Bert L. Hartnell; Douglas F. Rall;

Vizing's conjecture and the one-half argument

Abstract

Summary: The domination number of a graph \(G\) is the smallest order, \(\gamma (G)\), of a dominating set for \(G\). A conjecture of \textit{V. G. Vizing} [Vychisl. Sist. 9, 30-43 (1963; Zbl 0194.25203)] states that for every pair of graphs \(G\) and \(H\), \(\gamma (G \square H) \geq \gamma (G) \gamma (H)\), where \(G \square H\) denotes the Cartesian product of \(G\) and \(H\). We show that if the vertex set of \(G\) can be partitioned in a certain way then the above inequality holds for every graph \(H\). The class of graphs \(G\) which have this type of partitioning includes those whose 2-packing number is no smaller than \(\gamma (G) - 1\) as well as the collection of graphs considered by \textit{A. M. Bartsalkin} and \textit{L. F. German} in [Izv. Akad. Nauk Mold. SSR, Ser. Fiz.-Tekh. Math. Nauk 1979, No. 1, 5-8 (1979; Zbl 0457.05053)]. A crucial part of the proof depends on the well-known fact that the domination number of any connected graph of order at least two is no more than half its order.

Keywords

Graph theory, clique, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), domination number, partitioning, Cartesian product, dominating set, Vising's conjecture

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    10
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Top 10%
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
10
Average
Top 10%
Average
Published in a Diamond OA journal