Independent domination in subcubic bipartite graphs of girth at least six

Michael A. Henning; Christian Löwenstein; Dieter Rautenbach

doi:10.1016/j.dam.2013.08.035

Independent domination in subcubic bipartite graphs of girth at least six

Michael A. Henning, Christian Löwenstein, Dieter Rautenbach

Mathematics and Applied Mathematics

Ulm University

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

11 Citations (Scopus)

Abstract

A set S of vertices of 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 in S. The independent domination number of G, denoted by i(G), is the minimum cardinality of an independent dominating set of G. In this paper, we show that if G is a bipartite cubic graph of order n and of girth at least 6, then i(G)≤4n/11.

Original language	English
Pages (from-to)	399-403
Number of pages	5
Journal	Discrete Applied Mathematics
Volume	162
DOIs	https://doi.org/10.1016/j.dam.2013.08.035
Publication status	Published - 10 Jan 2014

Keywords

Cubic graphs
Independent domination

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.dam.2013.08.035

Cite this

@article{ea04bf92db92411eaed7d767fa29800f,

title = "Independent domination in subcubic bipartite graphs of girth at least six",

abstract = "A set S of vertices of 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 in S. The independent domination number of G, denoted by i(G), is the minimum cardinality of an independent dominating set of G. In this paper, we show that if G is a bipartite cubic graph of order n and of girth at least 6, then i(G)≤4n/11.",

keywords = "Cubic graphs, Independent domination",

author = "Henning, \{Michael A.\} and Christian L{\"o}wenstein and Dieter Rautenbach",

year = "2014",

month = jan,

day = "10",

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

language = "English",

volume = "162",

pages = "399--403",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Independent domination in subcubic bipartite graphs of girth at least six

AU - Henning, Michael A.

AU - Löwenstein, Christian

AU - Rautenbach, Dieter

PY - 2014/1/10

Y1 - 2014/1/10

N2 - A set S of vertices of 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 in S. The independent domination number of G, denoted by i(G), is the minimum cardinality of an independent dominating set of G. In this paper, we show that if G is a bipartite cubic graph of order n and of girth at least 6, then i(G)≤4n/11.

AB - A set S of vertices of 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 in S. The independent domination number of G, denoted by i(G), is the minimum cardinality of an independent dominating set of G. In this paper, we show that if G is a bipartite cubic graph of order n and of girth at least 6, then i(G)≤4n/11.

KW - Cubic graphs

KW - Independent domination

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

U2 - 10.1016/j.dam.2013.08.035

DO - 10.1016/j.dam.2013.08.035

M3 - Article

AN - SCOPUS:84887988190

SN - 0166-218X

VL - 162

SP - 399

EP - 403

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

Independent domination in subcubic bipartite graphs of girth at least six

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this