An Improved Upper Bound on the Independent Domination Number in Cubic Graphs of Girth at Least Six

被引：3

作者：

Abrishami, Gholamreza ^{[1
]}

Henning, Michael A. ^{[2
]}

机构：

[1] Ferdowsi Univ Mashhad, Fac Math Sci, Dept Appl Math, POB 1159, Mashhad 91775, Razavi Khorasan, Iran

[2] Univ Johannesburg, Dept Math & Appl Math, ZA-2006 Auckland Pk, South Africa

来源：

GRAPHS AND COMBINATORICS | 2022年 / 38卷 / 02期

关键词：

Independent domination; Cubic graphs;

D O I：

10.1007/s00373-021-02446-y

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Henning et al. (Discrete Appl Math 162:399-403, 2014) proved that if G is a bipartite, cubic graph of order n and of girth at least 6, then i(G) <= 4/11n. In this paper, we improve the 4/11-bound to a 5/14-bound, and prove that if G is a bipartite, cubic graph of order n and of girth at least 6, then i(G) <= 5/14 n.

引用

页数：12

共 19 条

[1] ON INDEPENDENT DOMINATION IN PLANAR CUBIC GRAPHS [J].

Abrishami, Gholamreza ;

Henning, Michael A. ;

Rahbarnia, Freydoon .

DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2019, 39 (04) :841-853

[2] Independent domination in subcubic graphs of girth at least six [J].

Abrishami, Gholamreza ;

Henning, Michael A. .

DISCRETE MATHEMATICS, 2018, 341 (01) :155-164

[3] WHAT IS THE DIFFERENCE BETWEEN THE DOMINATION AND INDEPENDENT DOMINATION NUMBERS OF A CUBIC GRAPH [J].

BAREFOOT, C ;

HARARY, F ;

JONES, KF .

GRAPHS AND COMBINATORICS, 1991, 7 (02) :205-208

[4] Independent Domination in Cubic Graphs [J].

Dorbec, Paul ;

Henning, Michael A. ;

Montassier, Mickael ;

Southey, Justin .

JOURNAL OF GRAPH THEORY, 2015, 80 (04) :329-349

[5] Independent domination in graphs: A survey and recent results [J].

Goddard, Wayne ;

Henning, Michael A. .

DISCRETE MATHEMATICS, 2013, 313 (07) :839-854

[6] On the Independent Domination Number of Regular Graphs [J].

Goddard, Wayne ;

Henning, Michael A. ;

Lyle, Jeremy ;

Southey, Justin .

ANNALS OF COMBINATORICS, 2012, 16 (04) :719-732

[7] Independent dominating sets in triangle-free graphs [J].

Goddard, Wayne ;

Lyle, Jeremy .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2012, 23 (01) :9-20

[8]

Haynes T. W, 2020, Series: Developments in Mathematics, V64, DOI DOI 10.1007/978-3-030-51117-3

[9]

Haynes T. W., 2021, STRUCTURES DOMINATIO, V66, DOI [10.1007/978-3-030-58892-2, DOI 10.1007/978-3-030-58892-2]

[10]

Haynes T.W., 2022, Domination in Graphs: Core Concepts

← 1 2 →