A characterization of diameter-2-critical graphs with no antihole of length four

Teresa W. Haynes, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)

Abstract

A graph G is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. In this paper we characterize the diameter-2-critical graphs with no antihole of length four, that is, the diameter-2-critical graphs whose complements have no induced 4-cycle. Murty and Simon conjectured that the number of edges in a diameter-2-critical graph of order n is at most n 2/4 and that the extremal graphs are complete bipartite graphs with equal size partite sets. As a consequence of our characterization, we prove the Murty-Simon Conjecture for graphs with no antihole of length four.

Original languageEnglish
Pages (from-to)1125-1132
Number of pages8
JournalCentral European Journal of Mathematics
Volume10
Issue number3
DOIs
Publication statusPublished - Jun 2012

Keywords

  • Antihole
  • Diameter critical
  • Diameter-2-critical
  • Total domination critical

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

Dive into the research topics of 'A characterization of diameter-2-critical graphs with no antihole of length four'. Together they form a unique fingerprint.

Cite this