Factor Criticality and Complete Closure of Graphs
by
N. Ananchuen
Department of Mathematics, Silpakorn University, Nakorn Pathom 73000, Thailand
Coauthors: Akira Saito (Department of Applied Mathematics, Nihon University, Sakurajosui 32540,Setagaya-Ku, Tokyo 1568550, Japan)

A graph G is said to be n-factor-critical if G-T has a perfect matching for every T subset V(G) with |T|=n. For a vertex x of a graph G, local completion of G at x is the operation of joining every pair of nonadjacent vertices in N_G(x). For a property P of graphs, a vertex x in a graph G is said to be P-eligible if the subgraph of G induced by N_G(x) satisfies P but it is not complete. For a graph G, a graph H is said to be a P-closure of G if there exists a series of graphs G=G₀, G₁, ..., G_r=H such that G_i is obtained from G_i-1 by local completion at some P-eligible vertex in G_i-1 and H=G_r has no P-eligible vertex. In this paper, we investigate the relation between factor-criticality and a P-closure, where P is a bounded independence number or a bounded domination number.

Date received: March 9, 2001