The decay number and the maximum genus of diameter 2 graphs

Hung-Lin Fu*, Ming Chun Tsai, N. H. Xuong

*Corresponding author for this work

Research output: Contribution to journalArticle

4 Scopus citations

Abstract

Let ζ(G) (resp. ξ(G)) be the minimum number of components (resp. odd size components) of a co-tree of a connected graph G. For every 2-connected graph G of diameter 2, it is known that m(G)≥2n(G) - 5 and ξ(G)≤ζ(G)≤4. These results define three classes of extremal graphs. In this paper, we prove that they are the same, with the exception of loops added to vertices.

Original languageEnglish
Pages (from-to)191-197
Number of pages7
JournalDiscrete Mathematics
Volume226
Issue number1-3
DOIs
StatePublished - 1 Jan 2001

Keywords

  • Betti deficiency
  • Decay number
  • Diameter
  • Extremal graphs

Fingerprint Dive into the research topics of 'The decay number and the maximum genus of diameter 2 graphs'. Together they form a unique fingerprint.

Cite this