Some Properties Of Defect K-extendable Graphs

Let G be a connected graph of order n > 2k + d + 2 and ?, d be non-negative integers such that n-d = 0 (mod 2). A defect-d matching is a matching saturating all but d vertices in a graph. If any set of k independent edges in G is contained in a defect-d matching, then G is called a (0, ?, d)-graph and particularly, G is said to be ?-extendable when d = 0, G is said to be defect ?-extendable when d = 1.This paper first considers the relationship between ?-extendable graphs and defect?-extendable graphs, and classifies all defect ?-extendable graphs and shows that a defect ?-extendable graph is bipartite or factor-critical or its connectivity is one where k > 2. Next, we discusses the problem of surface embedding of defect?-extendable graphs. It shows that there are planar defect ?-extendable graphs for any non-negative integer k. More generally, we give the bounds of surface embedding about defect ?-extendable graphs with minimum degree ? ? k+1 and girth g > 4:(?)+1??'(0, ?, 1)?(?)+1 where ?(?)is the Euler characteristic of surface ? and ?'(0, ?,1) is the minimum positive integer k such that any defect ?-extendable graph cannot be embedded in surface?. Moreover, we characterize minimal defect 1-extendable bipartite graphs. For practical application, a class of spanning trees of defect ?-extendable bipartite graphs are presented. Finally, we show that G?K2 is a (0,3,2)-graph when G is a defect 1-extendable and G?K2 is a (0,4,2)-graph when G is a defect ?-extendable with ? ? 2, the results are best possible.