Graphs that are critical with respect to matching extension and diameter
Access Status
Authors
Date
1994Supervisor
Collection
Type
Education Level
Metadata
Show full item recordAbstract
Let G be a simple connected graph on 2n vertices with a perfect matching. For 1 ≤ k ≤ n  1, G is said to be kextendable if for every matching M of size k in G there is a perfect matching in G containing all the edges of M. A kextendable graph G is said to be kcritical (kminimal) if G+uv (Guv) is not kextendable for every nonadjacent (adjacent) pair of vertices u and v of G. The problem that arises is that of characterizing kextendable, kcritical and kminimal 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 kextendable. 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 kextendable is that its independence number is at most n  k. We also establish that a kextendable 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 kextendable 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 kextendable 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 kcritical graphs. These results include sufficient conditions for kextendable graphs to be kcritical. More specifically, we prove that for a kextendable graph G ≠ K2n on 2n vertices, 2 ≤ k ≤ n  1, if for every pair of nonadjacent 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 Guv such that o(G(S u {u,v})) = S, then G is kcritical. Moreover, for k = 2 this sufficient condition is also a necessary condition for nonbipartite graphs. We also establish a necessary condition, in terms of the minimum degree, for kcritical graphs.We conclude Chapter 3 by completely characterizing kcritical graphs on 2n vertices for k = 1, n  1 and n  2.Chapter 4 contains results on kminimal graphs. These results include necessary and sufficient conditions for kextendable graphs to be kminimal. More specifically, we prove that for a kextendable 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 Ge 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 Guv such that: M(S) ≥ k; o(GeS) = S  2k + 2; and u and v belong to different odd components of GeS, where M(S) denotes a maximum matching in G[S].We also establish a necessary condition, in terms of minimum degree, for kminimal and kminimal bipartite graphs. In fact, we prove that a kminimal graph G ≠ K2n on 2n vertices, 1 ≤ k ≤ n  1, has minimum degree at most n + k  1. For a kminimal 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.
Department
Related items
Showing items related by title, author, creator and subject.

Ananchuen, Watcharaphong (1993)A graph G is said to have property P(m,n,k) if for any set of m + n distinct vertices there are at least k other vertices, each of which is adjacent to the first m vertices but not adjacent to any of the latter n vertices. ...

Lee, Wei R. (1999)In this thesis we shall investigate the numerical solutions to several important practical static and dynamic optimization problems in engineering and physics. The thesis is organized as follows.In Chapter 1 a general ...

Ananchuen, Watcharaphong; Caccetta, Louis (2006)A graph G is nexistentially closed or ne.c. if for any two disjoint subsets A and B of vertices of G with A ∪ B = n, there is a vertex u /∈A ∪ B that is adjacent to every vertex of A but not adjacent to any vertex of ...