کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648951 1342437 2009 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Minimum degree of minimal defect nn-extendable bipartite graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Minimum degree of minimal defect nn-extendable bipartite graphs
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 21, 6 November 2009, Pages 6255–6264
نویسندگان
, ,