Displaying similar documents to “Partition numbers, connectivity and Hamiltonicity”

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

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...

A maximum degree theorem for diameter-2-critical graphs

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...

The Connectivity Of Domination Dot-Critical Graphs With No Critical Vertices

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...

Some Toughness Results in Independent Domination Critical Graphs

Nawarat Ananchuen, Watcharaphong Ananchuen (2015)

Discussiones Mathematicae Graph Theory

Similarity:

A subset S of V (G) is an independent dominating set of G if S is independent and each vertex of G is either in S or adjacent to some vertex of S. Let i(G) denote the minimum cardinality of an independent dominating set of G. A graph G is k-i-critical if i(G) = k, but i(G+uv) < k for any pair of non-adjacent vertices u and v of G. In this paper, we establish that if G is a connected 3-i-critical graph and S is a vertex cutset of G with |S| ≥ 3, then [...] improving a result proved...