Graphs that are critical with respect to matching extension and diameter

Abstract

Let G be a simple connected graph on 2n vertices with a perfect matching. For 1 ≤ k ≤ n - 1, G is said to be k-extendable if for every matching M of size k in G there is a perfect matching in G containing all the edges of M. A k-extendable graph G is said to be k-critical (k-minimal) if G+uv (G-uv) is not k-extendable for every non-adjacent (adjacent) pair of vertices u and v of G. The problem that arises is that of characterizing k-extendable, k-critical and k-minimal graphs.In Chapter 2, we establish that δ(G) ≥ 1/2(n + k) is a sufficient condition for a bipartite graph G on 2n vertices to be k-extendable. For a graph G on 2n vertices with δ(G) ≥ n + k 1, n - k even and n/2 ≤ k ≤ n - 2, we prove that a necessary and sufficient condition for G to be k-extendable is that its independence number is at most n - k. We also establish that a k-extendable graph G of order 2n has k + 1 ≤ δ(G) n or δ(G) ≥ 2k + 1, 1 ≤ k ≤ n - 1. Further, we establish the existence of a k-extendable graph G on 2n vertices with δ(G) = j for each integer j Є [k + 1, n] u [2k + 1, 2n 1]. For k = n - 1 and n - 2, we completely characterize k-extendable graphs on 2n vertices. We conclude Chapter 2 with a variation of the concept of extendability to odd order graphs.In Chapter 3, we establish a number of properties of k-critical graphs. These results include sufficient conditions for k-extendable graphs to be k-critical. More specifically, we prove that for a k-extendable graph G ≠ K2n on 2n vertices, 2 ≤ k ≤ n - 1, if for every pair of non-adjacent vertices u and v of G there exists a dependent set S ( a subset S of V (G) is dependent if the induced subgraph G[S] has at least one edge) of G-u-v such that o(G-(S u {u,v})) = S, then G is k-critical. Moreover, for k = 2 this sufficient condition is also a necessary condition for non-bipartite graphs. We also establish a necessary condition, in terms of the minimum degree, for k-critical graphs.We conclude Chapter 3 by completely characterizing k-critical graphs on 2n vertices for k = 1, n - 1 and n - 2.Chapter 4 contains results on k-minimal graphs. These results include necessary and sufficient conditions for k-extendable graphs to be k-minimal. More specifically, we prove that for a k-extendable graph G on 2n vertices, 1 ≤ k ≤ n - 1, the following are equivalent:G is minimalfor every edge e = uv of G there exists a matching M of size k in G-e such that V(M) n {u,v} = ø and for every perfect matching F in G containing M, e Є F.for every edge e = uv of G there exists a vertex set S of G-u-v such that: M(S) ≥ k; o(G-e-S) = S - 2k + 2; and u and v belong to different odd components of G-e-S, where M(S) denotes a maximum matching in G[S].We also establish a necessary condition, in terms of minimum degree, for k-minimal and k-minimal bipartite graphs. In fact, we prove that a k-minimal graph G ≠ K2n on 2n vertices, 1 ≤ k ≤ n - 1, has minimum degree at most n + k - 1. For a k-minimal bipartite graph G ≠ Kn,n , 1 ≤ k ≤ n - 3, we show that δ(G) < ½(n + k).Chapter 1 provides the notation, terminology, general concepts and the problems concerning extendability graphs and (k,t)-critical graphs.