Characterizing defect n-extendable graphs and -critical graphs |
| |
Authors: | Xuelian Wen Dingjun Lou |
| |
Institution: | aFaculty of Computer, Guangdong University of Technology, Guangzhou 510006, PR China;bDepartment of Computer Science, Sun Yat-sen University, Guangzhou 510275, PR China |
| |
Abstract: | A near perfect matching is a matching saturating all but one vertex in a graph. Let G be a connected graph. If any n independent edges in G are contained in a near perfect matching where n is a positive integer and n(|V(G)|-2)/2, then G is said to be defect n-extendable. If deleting any k vertices in G where k|V(G)|-2, the remaining graph has a perfect matching, then G is a k-critical graph. This paper first shows that the connectivity of defect n-extendable graphs can be any integer. Then the characterizations of defect n-extendable graphs and (2k+1)-critical graphs using M-alternating paths are presented. |
| |
Keywords: | Near perfect matching Defect n-extendable graph (2n+1)-Critical graph M-alternating path |
本文献已被 ScienceDirect 等数据库收录! |
|