| Characterization of Connected Graphs with Maximum Domination Number |
| Received:November 02, 1997 Revised:July 01, 1999 |
| Key Words:
connected graph crown domination number domination critical graph
|
| Fund Project:Supported by the National Science Foundation of Jiangxi province. |
|
| Hits: 1944 |
| Download times: 879 |
| Abstract: |
| Let G be a connected graph of order p, and let γ(G) denote the domination number of G. Clearly, γ(G) ≤[p/2]. The aim of this paper is to characterize the graphs G that reaches this upper bound. The main results are as follows: (1) when p is even, γ(G) = p/2 if and only if either G≈C4 or G is the crown of a connected graph with p/2 vertices; (2) when p is odd, γ(G) = (p-1)/2 if and only if every spanning tree of G is one of the two classes of trees shown in Theorem 3.1. |
| Citation: |
| DOI:10.3770/j.issn:1000-341X.2000.04.009 |
| View Full Text View/Add Comment |
