Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648928 | Discrete Mathematics | 2007 | 21 Pages |
Abstract
Let V1,V2V1,V2 be a partition of the vertex set in a graph GG. For i=1,2i=1,2, let γiγi denote the least number of vertices needed in GG to dominate ViVi. It is known that if GG has order nn and minimum degree two, then γ1+γ2⩽2n/3γ1+γ2⩽2n/3. In this paper, we characterize those graphs of order nn which are edge-minimal with respect to satisfying the conditions of connected, minimum degree at least two, and γ1+γ2=2n/3γ1+γ2=2n/3.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Michael A. Henning, Preben Dahl Vestergaard,