On a Minimum Cutset of Strongly k-Extandable Graphs
by
Nawarat Ananchuen
Department of Mathematics, Silpakorn University, Nakorn Pathom 73000 Thailand

Let G be a simple connected graph on 2n vertices with a perfect matching. For a positive integer k, 1 <= k <= n-1, G is 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. For an integer k, 0 <= k <= n-2, G is strongly k-extendable if G-{u, v} is k-extendable for every pair of vertices u and v of G. The problem that arises is that of characterizing k-extendable graphs and strongly k-extendable graphs. The first of these problems has been considered by several authors while the latter has been recently investigated. In this paper, we focus on a minimum cutset of strongly k-extendable graphs. We establish the independence number of G[S] when S is a minimum cutset of a strongly k-extendable graph G. Further, we present an upper bound on a number of components of G-S.

Date received: August 9, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cafn-02.