Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: Antihole

Sortuj według:

Ogranicz wyniki do:

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

100%

Haynes T., Henning M.

Open Mathematics

2012

tom 10

nr 3

1125-1132

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.

Ograniczanie wyników

1 Open Mathematics

1 Haynes T.

1 Henning M.

1 2012

Wyniki wyszukiwania

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