An upper bound on the domination number of n-vertex connected cubic graphs

A. V. Kostochka; B. Y. Stodolsky

doi:10.1016/j.disc.2007.12.009

An upper bound on the domination number of n-vertex connected cubic graphs

A. V. Kostochka^*, B. Y. Stodolsky

^*Corresponding author for this work

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

23 Citations (Scopus)

Abstract

In 1996, Reed proved that the domination number γ (G) of every n-vertex graph G with minimum degree at least 3 is at most 3 n / 8. This bound is sharp for cubic graphs if there is no restriction on connectivity. In this paper we show that γ (G) ≤ 4 n / 11 for every n-vertex cubic connected graph G if n > 8. Note that Reed's conjecture that γ (G) ≤ ⌈ n / 3 ⌉ for every connected cubic n-vertex graph G is not true.

Original language	English
Pages (from-to)	1142-1162
Number of pages	21
Journal	Discrete Mathematics
Volume	309
Issue number	5
DOIs	https://doi.org/10.1016/j.disc.2007.12.009
Publication status	Published - 28 Mar 2009
Externally published	Yes

Funding

The first author was supported in part by NSF grants DMS-0400498 and DMS-0650784 and grants 05-01-00816 and 06-01-00694 of the Russian Foundation for Basic Research.

Funders	Funder number
National Science Foundation	DMS-0400498, DMS-0650784, 05-01-00816, 06-01-00694
Russian Foundation for Basic Research

Keywords

Connected graphs
Cubic graphs
Domination

Access to Document

10.1016/j.disc.2007.12.009

Cite this

@article{67a27208ed3a41ada5330eea77732b2f,

title = "An upper bound on the domination number of n-vertex connected cubic graphs",

abstract = "In 1996, Reed proved that the domination number γ (G) of every n-vertex graph G with minimum degree at least 3 is at most 3 n / 8. This bound is sharp for cubic graphs if there is no restriction on connectivity. In this paper we show that γ (G) ≤ 4 n / 11 for every n-vertex cubic connected graph G if n > 8. Note that Reed's conjecture that γ (G) ≤ ⌈ n / 3 ⌉ for every connected cubic n-vertex graph G is not true.",

keywords = "Connected graphs, Cubic graphs, Domination",

author = "Kostochka, \{A. V.\} and Stodolsky, \{B. Y.\}",

year = "2009",

month = mar,

day = "28",

doi = "10.1016/j.disc.2007.12.009",

language = "English",

volume = "309",

pages = "1142--1162",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - An upper bound on the domination number of n-vertex connected cubic graphs

AU - Kostochka, A. V.

AU - Stodolsky, B. Y.

PY - 2009/3/28

Y1 - 2009/3/28

N2 - In 1996, Reed proved that the domination number γ (G) of every n-vertex graph G with minimum degree at least 3 is at most 3 n / 8. This bound is sharp for cubic graphs if there is no restriction on connectivity. In this paper we show that γ (G) ≤ 4 n / 11 for every n-vertex cubic connected graph G if n > 8. Note that Reed's conjecture that γ (G) ≤ ⌈ n / 3 ⌉ for every connected cubic n-vertex graph G is not true.

AB - In 1996, Reed proved that the domination number γ (G) of every n-vertex graph G with minimum degree at least 3 is at most 3 n / 8. This bound is sharp for cubic graphs if there is no restriction on connectivity. In this paper we show that γ (G) ≤ 4 n / 11 for every n-vertex cubic connected graph G if n > 8. Note that Reed's conjecture that γ (G) ≤ ⌈ n / 3 ⌉ for every connected cubic n-vertex graph G is not true.

KW - Connected graphs

KW - Cubic graphs

KW - Domination

UR - https://www.scopus.com/pages/publications/60549101735

U2 - 10.1016/j.disc.2007.12.009

DO - 10.1016/j.disc.2007.12.009

M3 - Article

AN - SCOPUS:60549101735

SN - 0012-365X

VL - 309

SP - 1142

EP - 1162

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 5

ER -

An upper bound on the domination number of n-vertex connected cubic graphs

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this