کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648951 | 1342437 | 2009 | 10 صفحه PDF | دانلود رایگان |

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.
Journal: Discrete Mathematics - Volume 309, Issue 21, 6 November 2009, Pages 6255–6264