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.