A [Formula presented]-approximation of Vizing's conjecture for claw-free graphs

Boštjan Brešar; Michael A. Henning

doi:10.1016/j.dam.2020.03.056

A [Formula presented]-approximation of Vizing's conjecture for claw-free graphs

Boštjan Brešar, Michael A. Henning

Mathematics and Applied Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

Vizing's conjecture from 1968 asserts that the domination number of the Cartesian product of two graphs is at least as large as the product of their domination numbers. We prove that for any claw-free graph G and an arbitrary graph H, the inequality γ(G□H)≥[Formula presented]γ(G)γ(H) always holds.

Original language	English
Pages (from-to)	416-422
Number of pages	7
Journal	Discrete Applied Mathematics
Volume	284
DOIs	https://doi.org/10.1016/j.dam.2020.03.056
Publication status	Published - 30 Sept 2020

Keywords

Cartesian product
Claw-free graph
Domination
Vizing's conjecture

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.dam.2020.03.056

Cite this

@article{36a3952aebcb4058b3bb7322d59e403b,

title = "A [Formula presented]-approximation of Vizing's conjecture for claw-free graphs",

abstract = "Vizing's conjecture from 1968 asserts that the domination number of the Cartesian product of two graphs is at least as large as the product of their domination numbers. We prove that for any claw-free graph G and an arbitrary graph H, the inequality γ(G□H)≥[Formula presented]γ(G)γ(H) always holds.",

keywords = "Cartesian product, Claw-free graph, Domination, Vizing's conjecture",

author = "Bo{\v s}tjan Bre{\v s}ar and Henning, {Michael A.}",

note = "Publisher Copyright: {\textcopyright} 2020 Elsevier B.V.",

year = "2020",

month = sep,

day = "30",

doi = "10.1016/j.dam.2020.03.056",

language = "English",

volume = "284",

pages = "416--422",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - A [Formula presented]-approximation of Vizing's conjecture for claw-free graphs

AU - Brešar, Boštjan

AU - Henning, Michael A.

PY - 2020/9/30

Y1 - 2020/9/30

N2 - Vizing's conjecture from 1968 asserts that the domination number of the Cartesian product of two graphs is at least as large as the product of their domination numbers. We prove that for any claw-free graph G and an arbitrary graph H, the inequality γ(G□H)≥[Formula presented]γ(G)γ(H) always holds.

AB - Vizing's conjecture from 1968 asserts that the domination number of the Cartesian product of two graphs is at least as large as the product of their domination numbers. We prove that for any claw-free graph G and an arbitrary graph H, the inequality γ(G□H)≥[Formula presented]γ(G)γ(H) always holds.

KW - Cartesian product

KW - Claw-free graph

KW - Domination

KW - Vizing's conjecture

UR - http://www.scopus.com/inward/record.url?scp=85083066750&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2020.03.056

DO - 10.1016/j.dam.2020.03.056

M3 - Article

AN - SCOPUS:85083066750

SN - 0166-218X

VL - 284

SP - 416

EP - 422

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

A [Formula presented]-approximation of Vizing's conjecture for claw-free graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this