Some results on characterizing the edges of connected graphs with a given domination number (Q1893172): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q4099676 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4198056 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Representatives of Subsets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Maximum number of edges in connected graphs with a given domination number / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5509541 / rank | |||
Normal rank |
Latest revision as of 15:09, 23 May 2024
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