Domination in partitioned graphs with minimum degree two (Q870974): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 02:26, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Domination in partitioned graphs with minimum degree two |
scientific article |
Statements
Domination in partitioned graphs with minimum degree two (English)
0 references
15 March 2007
0 references
Let \(V_1\) and \(V_2\) be a partition of the vertex set in a graph \(G\). For \(i=1,2\), let \(\gamma_i\) denote the least number of vertices needed in \(G\) to dominate \(V_i\). It is known that if \(G\) has order \(n\) and minimum degree two, then \(\gamma_1+\gamma_2\leq 2n/3\). The contribution of this paper is the complete characterization of those graphs of order \(n\) which are edge minimal with respect to satisfying the conditions of connected, minimum degree at least two, and \(\gamma_1+\gamma_2=2n/3\).
0 references
Domination
0 references
Partitioned graphs
0 references
3-subdivision
0 references