Double-critical graphs and complete minors.
Kawarabayashi, Ken-Ichi, Pedersen, Anders Sune, Toft, Bjarne (2010)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
Kawarabayashi, Ken-Ichi, Pedersen, Anders Sune, Toft, Bjarne (2010)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Barát, János, Tóth, Géza (2010)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Teresa Haynes, Michael Henning, Lucas Merwe, Anders Yeo (2014)
Open Mathematics
Similarity:
A graph is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. Let G be a diameter-2-critical graph of order n. Murty and Simon conjectured that the number of edges in G is at most ⌊n 2/4⌋ and that the extremal graphs are the complete bipartite graphs K ⌊n/2⌋,⌊n/2⌉. Fan [Discrete Math. 67 (1987), 235–240] proved the conjecture for n ≤ 24 and for n = 26, while Füredi [J. Graph Theory 16 (1992), 81–98] proved the conjecture for n > n 0 where...
Teresa Haynes, Michael Henning (2012)
Open Mathematics
Similarity:
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...
Albertson, Michael O., Cranston, Daniel W., Fox, Jacob (2009)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Michitaka Furuya (2014)
Discussiones Mathematicae Graph Theory
Similarity:
An edge of a graph is called dot-critical if its contraction decreases the domination number. A graph is said to be dot-critical if all of its edges are dot-critical. A vertex of a graph is called critical if its deletion decreases the domination number. In A note on the domination dot-critical graphs, Discrete Appl. Math. 157 (2009) 3743-3745, Chen and Shiu constructed for each even integer k ≥ 4 infinitely many k-dot-critical graphs G with no critical vertices and k(G) = 1. In this...
Krivelevich, Michael (1998)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Bohdan Zelinka (1979)
Czechoslovak Mathematical Journal
Similarity:
Cariolaro, David, Cariolaro, Gianfranco (2003)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
de Fraysseix, Hubert, Ossona de Mendez, Patrice (2003)
Journal of Graph Algorithms and Applications
Similarity: