Some results on characterizing the edges of connected graphs with a given domination number (Q1893172)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Some results on characterizing the edges of connected graphs with a given domination number |
scientific article |
Statements
Some results on characterizing the edges of connected graphs with a given domination number (English)
0 references
23 October 1995
0 references
A dominating set in a graph \(G\) is a subset \(D\) of the vertex set \(V(G)\) of \(G\) such that each vertex of \(G\) either is in \(D\), or is adjacent to a vertex of \(D\). The minimum number of vertices of a domination set in \(G\) is called the domination number of \(G\) and denoted by \(\gamma(G)\). In the paper a dominating set \(D\) of \(G\) with exactly \(\gamma(G)\) vertices is considered. One theorem determines the maximum number of edges of a graph with a given domination number and characterizes the graphs having this number of edges and this domination number. Further, the number \(m_ 1(G, D)\) of edges having no end vertex in \(D\) and the number \(m_ 2(G, D)\) of edges having at least one end vertex in \(G\) are considered. Some inequalities for these numbers are found at a general \(\gamma(G)\) and in particular at \(\gamma(G)= 3\) and \(\gamma(G)= 2\).
0 references
dominating set
0 references
domination number
0 references
end vertex
0 references
inequalities
0 references