Independent Domination in Bipartite Cubic Graphs

被引：6

作者：

Brause, Christoph ^{[1
,2
]}

Henning, Michael A. ^{[2
]}

机构：

[1] TU Bergakad Freiberg, Inst Discrete Math & Algebra, D-09596 Freiberg, Germany

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

来源：

GRAPHS AND COMBINATORICS | 2019年 / 35卷 / 04期

关键词：

Domination; Independent Domination; Cubic Graphs;

D O I：

10.1007/s00373-019-02043-0

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A set S of vertices in a graph G is an independent dominating set of G if S is an independent set and every vertex not in S is adjacent to a vertex inS. The independent domination number of G, denoted byi(G), is the minimum cardinality of an independent dominating set. In this paper, we study the following conjecture posed by Goddard and Henning (Discrete Math. 313:839-854,2013): If G?K3,3 is a connected, cubic, bipartite graph on n vertices, then i(G)<mml:mfrac>411</mml:mfrac>n. Henning et al.(Discrete Appl. Math. 162:399-403,2014) prove the conjecture when the girth is at least6. In this paper we strengthen this result by proving the conjecture when the graph has no subgraph isomorphic to K-2,K-3.

引用

页码：881 / 912

页数：32

共 14 条

[1] 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

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

Dorbec, Paul ;

Henning, Michael A. ;

Montassier, Mickael ;

Southey, Justin .

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

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

Goddard, Wayne ;

Henning, Michael A. .

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

[4] 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

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

Goddard, Wayne ;

Lyle, Jeremy .

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

[6]

Haynes T. W., 1998, FUNDAMENTALS DOMINAT, V1st, DOI [10.1201/9781482246582, DOI 10.1201/9781482246582]

[7]

Haynes T. W., 1998, DOMINATION GRAPHS AD

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

Henning, Michael A. ;

Loewenstein, Christian ;

Rautenbach, Dieter .

DISCRETE APPLIED MATHEMATICS, 2014, 162 :399-403

[9] THE INDEPENDENT DOMINATION NUMBER OF A CUBIC 3-CONNECTED GRAPH CAN BE MUCH LARGER THAN ITS DOMINATION NUMBER [J].

KOSTOCHKA, AV .

GRAPHS AND COMBINATORICS, 1993, 9 (03) :235-237

[10] On independent domination number of regular graphs [J].

Lam, PCB ;

Shiu, WC ;

Sun, L .

DISCRETE MATHEMATICS, 1999, 202 (1-3) :135-144

← 1 2 →