On independent domination number of regular graphs
type: Item
instance of: scholarly article
title: On independent domination number of regular graphs
zbMATH Open document ID: 0934.05098
DOI: 10.1016/S0012-365X(98)00350-1
author: Wai Chee Shiu
author: Liang Sun
author: P. C. B. Lam
published in: Discrete Mathematics
publication date: 2000-04-10T00:00:00Z
review text: A subset \(S\) of the vertex set of a graph \(G\) is called independent, if no two of its vertices are adjacent in \(G\). An independent set in \(G\) is maximal, if it is not a proper subset of another independent set of \(G\). The minimum number of vertices of a maximal independent set is the independent domination number \(i(G)\) of \(G\). A conjecture of J. Haviland says that a regular graph \(G\) of degree \(\delta\leq n/2\) (where \(n\) is the number of vertices of \(G\)) has \(i(G)\leq\lceil 2n/3\rceil \delta/2\). In the paper this conjecture is disproved by giving two counterexamples. Then for a connected cubic graph \(G\) with \(n>3\) vertices the inequality \(i(G)\leq 2n/5\) is proved.
reviewed by: Bohdan Zelinka
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1334522
zbMATH Keywords: independent set
zbMATH Keywords: independent domination number
zbMATH Keywords: regular graph
MaRDI profile type: Publication
cites work: Graph-theoretic parameters concerning domination, independence, and irredundance
cites work: The product of the independent domination numbers of a graph and its complement
cites work: Contributions to the theory of domination, independence and irredundance in graphs
cites work: On a Nordhaus-Gaddum type problem for independent domination
cites work: Q4060985
cites work: Two relations between the parameters of independence and irredundance
cites work: On minimum maximal independent sets of a graph
cites work: Independent domination in regular graphs
cites work: Bibliography on domination in graphs and some basic definitions of domination parameters
full work available at URL: s0012-365x(98)00350-1
OpenAlex ID: W2127967904
description: scientific article; zbMATH DE number 1334522