Independence and connectivity in 3-domination-critical graphs
type: Item
instance of: scholarly article
title: Independence and connectivity in 3-domination-critical graphs
zbMATH Open document ID: 1015.05063
DOI: 10.1016/S0012-365X(02)00383-7
author: Feng Tian
author: Lianzhu Zhang
published in: Discrete Mathematics
publication date: 2003-03-16T00:00:00Z
review text: Let \(G\) be a finite undirected simple graph. A set of vertices \(S\) is called a dominating set of \(G\), if all vertices of \(G\) are either elements or neighbours of elements of \(S\). The domination number \(\gamma\) of \(G\) is the minimum cardinality of a dominating set of \(G\). A graph is called \(3\)-domination-critical, if it has domination number \(3\) and every addition of an edge yields a graph with domination number \(2\). Let \(G\) be connected and \(3\)-domination-critical and \(\delta\), \(\alpha\), \(\kappa\) be the minimum degree, the independence number, and the connectivity of \(G\), respectively. The authors prove that \(\alpha\leq \kappa+2\) and that if \(\alpha=\kappa+2\), then \(\kappa=\delta\). Furthermore, they give a short proof of a theorem by \textit{E. Wojcicka} [J. Graph Theory 14, 205-215 (1990; Zbl 0702.05058)] which states that if \(G\) is connected, \(3\)-critical and has at least \(7\) vertices, then \(G\) has a Hamilton path.
reviewed by: Clemens Heuberger
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 1882152
zbMATH Keywords: \(3\)-domination-critical graph
zbMATH Keywords: independence number
zbMATH Keywords: connectivity
zbMATH Keywords: Hamilton path
MaRDI profile type: Publication
full work available at URL: s0012-365x(02)00383-7
OpenAlex ID: W1984672596
description: scientific article; zbMATH DE number 1882152