Maximum number of edges in connected graphs with a given domination number (Q1174141): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Domination alteration sets in graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4099676 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Towards a theory of domination in graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3291034 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Domination critical graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Minimum number of edges in graphs that are both \(P_ 2-\) and \(P_ i- \)connected / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5509541 / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0012-365x(91)90071-9 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2069267595 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 12:07, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Maximum number of edges in connected graphs with a given domination number |
scientific article |
Statements
Maximum number of edges in connected graphs with a given domination number (English)
0 references
25 June 1992
0 references
A dominating set in a graph is a subset \(U\) of its vertices such that each vertex not in \(U\) has a neighbour in \(U\). The domination number is the minimum size of a dominating set. The paper under review shows that a graph with \(n\) vertices, domination number \(d\) (where \(3\leq d\leq n/2)\) and no isolated vertices has at most \(n-d+1\choose 2\) edges. The graphs for which this bound is tight are also characterized. The proof is based on work of \textit{Y. Usami} [``Minimum number of edges in graphs that are both \(P_ 2\)- and \(P_ i\)-connected'', Discrete Math. 44, 195-199 (1983; Zbl 0503.05038)]. The corresponding bound and related characterization for graphs with isolated vertices is due to Vizing.
0 references