Return to search

A Characterization of <sup>P 5</sup>-Free, Diameter-2-Critical Graphs

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 induced path on five vertices. Murty and Simon conjectured that the number of edges in a diameter-2-critical graph of order n is at most n2/4 and that the extremal graphs are the complete bipartite graphs with partite sets whose cardinality differs by at most one. We use an association with total domination to prove that if G is a diameter-2-critical graph with no induced path P5, then G is triangle-free. As a consequence, we observe that the Murty-Simon Conjecture is true for P5-free, diameter-2-critical graphs by TurĂ¡n's Theorem. Finally we characterize these graphs by characterizing their complements.

Identiferoai:union.ndltd.org:ETSU/oai:dc.etsu.edu:etsu-works-16954
Date31 May 2014
CreatorsHaynes, Teresa W., Henning, Michael A.
PublisherDigital Commons @ East Tennessee State University
Source SetsEast Tennessee State University
Detected LanguageEnglish
Typetext
SourceETSU Faculty Works

Page generated in 0.002 seconds