Article ID Journal Published Year Pages File Type
4648951 Discrete Mathematics 2009 10 Pages PDF
Abstract

A near perfect matching is a matching saturating all but one vertex in a graph. If GG is a connected graph and any nn independent edges in GG are contained in a near perfect matching, then GG is said to be defect nn-extendable. If for any edge ee in a defect nn-extendable graph GG, G−eG−e is not defect nn-extendable, then GG is minimal defect nn-extendable. The minimum degree and the connectivity of a graph GG are denoted by δ(G)δ(G) and κ(G)κ(G) respectively. In this paper, we study the minimum degree of minimal defect nn-extendable bipartite graphs. We prove that a minimal defect 1-extendable bipartite graph GG has δ(G)=1δ(G)=1. Consider a minimal defect nn-extendable bipartite graph GG with n≥2n≥2, we show that if κ(G)=1κ(G)=1, then δ(G)≤n+1δ(G)≤n+1 and if κ(G)≥2κ(G)≥2, then 2≤δ(G)=κ(G)≤n+12≤δ(G)=κ(G)≤n+1. In addition, graphs are also constructed showing that, in all cases but one, there exist graphs with minimum degree that satisfies the established bounds.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,