Pancyclism of 3-domination-critical graphs with small minimum degree

Wai Chee Shiu, Lian Zhu Zhang

Research output: Contribution to journalJournal articlepeer-review

1 Citation (Scopus)

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 languageEnglish
Pages (from-to)175-192
Number of pages18
JournalUtilitas Mathematica
Volume75
Publication statusPublished - Mar 2008

Scopus Subject Areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty
  • Applied Mathematics

User-Defined Keywords

  • 3-domination-critical graphs
  • Pancyclic graphs

Fingerprint

Dive into the research topics of 'Pancyclism of 3-domination-critical graphs with small minimum degree'. Together they form a unique fingerprint.

Cite this