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 |
Scopus Subject Areas
- Statistics and Probability
- Statistics, Probability and Uncertainty
- Applied Mathematics
User-Defined Keywords
- 3-domination-critical graphs
- Pancyclic graphs