Domination in partitioned graphs with minimum degree two (Q870974)
From MaRDI portal
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