Abstract
A graph G is 3-domination-critical if its domination number γ is 3 and the addition of any edge decreases γ by 1. Let G be a connected 3-domination-critical graph of order n. Shao etc. proved that if δ(G) ≥ 3 then G is pancyclic, i.e. G contains cycles of each length k, 3 ≤ k ≤ n. In this paper, we prove that the number of 2-vertices in G is at most 3. Using this result, we prove that the graph G - V1 is pancyclic, where V1 is the set of all 1-vertices in G, except G is isomorphic to the graph of order 7 well-defined in the context.
| Original language | English |
|---|---|
| Pages (from-to) | 175-192 |
| Number of pages | 18 |
| Journal | Utilitas Mathematica |
| Volume | 75 |
| Publication status | Published - Mar 2008 |
User-Defined Keywords
- 3-domination-critical graphs
- Pancyclic graphs