Domination number and neighbourhood conditions (Q1296973)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Domination number and neighbourhood conditions |
scientific article |
Statements
Domination number and neighbourhood conditions (English)
0 references
10 April 2000
0 references
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\}. \]
0 references
neighbourhood conditions
0 references
dominating set
0 references
domination number
0 references