关于几乎k-可扩图的若干结论

Some Results on Near k-extendable Graphs

设G是具有奇数个顶点的图,k是非负整数且满足V(G)≥2k+1,若G中任意一个k-匹配都可以扩充为G的一个几乎完美匹配,则称G是几乎k-可扩图.文中证明了连通的几乎1-可扩图与2-连通的几乎k-可扩二部图分别添加一个新边后仍保持原来的可扩性.

Let G be a graph with odd order and k a non-negative number satisfing ｜V（G）｜≥2k＋1. G is called near k-extendable graph if any k-matching of G can be extended to a near perfect matching of G. In this paper, we prove that if G is a connected near/-extendable graph （resp. 2-connected near k-extendable graph）, then there exists e ∈ E（G） such that G ＋ e is still connected near 1-extendable （resp. 2-connected near k-extendable）.