Domination number and neighbourhood conditions
type: Item
instance of: scholarly article
title: Domination number and neighbourhood conditions
zbMATH Open document ID: 0934.05096
DOI: 10.1016/S0012-365X(98)00166-6
author: Beifang Chen
author: Sanming Zhou
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 dominating in \(G\), if each vertex of \(G\) either is in \(S\), or is adjacent to a vertex of \(S\). The minimum number of vertices of a dominating set in \(G\) is the domination number \(\gamma(G)\) of \(G\). In the paper inequalities for \(\gamma(G)\) are found, using certain numbers which concern the neighbourhoods in \(G\). For a subset \(A\) of the vertex set \(V\) of \(G\) the symbolic \(\partial^+(A)\) denotes the set of vertices which are not in \(A\) but are adjacent to a vertex of \(A\). Further \(\overline N(A)= A\cup\partial^+(A)\), and \(d(A)\) is the sum of the degrees of the vertices of \(A\). If \(G\) has \(p\) vertices and \(q\) edges, then \(2q\leq(p- \gamma)(p- \gamma+ 2)-|\partial^+(A)|(p- \gamma+1)+ d(\overline N(A))\). If \(I(A)\) denotes the set of vertices adjacent to all vertices of \(A\) and \(\overline I(A)= A\cup I(A)\), then \[ 2q\leq (p-\gamma-|\overline I(A)|+ 2)(p- \gamma+4)+ d(\overline I(A))- \min\{p- \gamma-|\overline I(A)|+ 2, |A|, |I(A)|, 3\}. \]
reviewed by: Bohdan Zelinka
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1320578
zbMATH Keywords: neighbourhood conditions
zbMATH Keywords: dominating set
zbMATH Keywords: domination number
MaRDI profile type: Publication
cites work: Q5422499
cites work: A compilation of relations between graph invariants
cites work: BOUNDS ON THE DOMINATION NUMBER OF A GRAPH
cites work: A compilation of relations between graph invariants—supplement I
cites work: Estimations for the domination number of a graph
cites work: A generalization of Vizing's theorem on domination
cites work: Q4198056
cites work: Updating the hamiltonian problem—A survey
cites work: Domination in graphs with minimum degree two
cites work: Q3291034
cites work: Q4108373
cites work: Maximum number of edges in connected graphs with a given domination number
cites work: Q5509541
full work available at URL: s0012-365x(98)00166-6
OpenAlex ID: W2059680011
description: scientific article; zbMATH DE number 1320578