奇图的匹配可扩性

数学物理学报 ›› 2009, Vol. 29 ›› Issue (2): 365-372.

奇图的匹配可扩性

(1. 厦门大学数学科学学院 |福建厦门 |361005|2. 厦门理工学院数理系 |福建厦门 361024)

收稿日期:2007-12-30 修回日期:2008-11-30 出版日期:2009-04-25 发布日期:2009-04-25
作者简介:国家自然科学基金(10831001)和福建省教育厅科技项目(JA08223)资助

Extending Matchings in Odd Graphs

(1. School of Mathematical Sciences, Xiamen University, |Fujian Xiamen 361005|2. Department of Mathematics and Physics, Xiamen University of Technology, Fujian |Xiamen 361024)

Received:2007-12-30 Revised:2008-11-30 Online:2009-04-25 Published:2009-04-25
Supported by:
国家自然科学基金(10831001)和福建省教育厅科技项目(JA08223)资助

摘要/Abstract

摘要：

设G是一个图, n, k和d是三个非负整数, 满足n+2k+d ≤ |V(G)|-2, |V(G)|和n+d有相同的奇偶性. 如果删去G中任意n个点后所得的图有k -匹配, 并且任一k -匹配都可以扩充为一个亏d -匹配,那么称G是一个(n, k, d) -图. Liu和Yu^[1]首先引入了(n, k, d) -图的概念,并且给出了(n, k, d) -图的一个刻划和若干性质. (0, k, 1) -图也称为几乎 k -可扩图.在本文中, 作者改进了(n, k, d) -图的刻划, 并给出了几乎k -可扩图和几乎k -可扩二部图的刻划, 进而研究了几乎 k -可扩图与n -因子临界图之间的关系.

关键词: (n, k, d) -图, k -可扩图, 几乎k -可扩图, n -因子临界图

Abstract:

Let G be a graph, and let n, k and d be three nonnegative integers such that n+2k+d≤ |V(G)|-2 and, |V(G)| and n+d have the same parity. If after deleting any n vertices from G the remaining subgraph of G contains an k-matching and each k-matching of the subgraph can be extended to a defect-d-matching of the subgraph, then G is called an (n, k, d)-graph. Liu and Yu^[1] first introduced (n, k, d)-graphs, and gave some properties and characterization of (n, k, d)-graphs. A (0, k, 1)-graph may be also called a near k-extendable graph. In the present paper, the authors improve the characterization of (n, k, d)-graphs, and consequently obtain a characterization of near k-extendable graphs. Furthermore, a characterization of near k-extendable bipartite graphs and the relations between near k-extendable graphs and n-factor critical graphs are investigated.

Key words: (n, k, d)-graphs, k-extendable graphs, Near k-extendable graphs, n-factor-critical graphs

中图分类号:

05C38

翟绍辉, 郭晓峰. 奇图的匹配可扩性[J]. 数学物理学报, 2009, 29(2): 365-372.

DI Chao-Hui, GUO Xiao-Feng. Extending Matchings in Odd Graphs[J]. Acta mathematica scientia,Series A, 2009, 29(2): 365-372.

参考文献

[1]   Liu G, Yu Q. Generalization of matching extensions in graphs. Discrete Math, 2001, 231: 311--320

[2] Bondy J A, Murty U S R. Graph Theory with  Applications. New York: American Elsevier, 1976

[3] Lovász L,  Plummer M D. Matching Theory. New York: North-Holland, 1986

[4] Berge C. Sur le couplage maximum d'un graphe. C R Acad Sci Paris, 1958, 247: 258--259

[5] Favaron O. On n-factor-critical graphs. Discuss Math Graph Theory, 1996, 16: 41--51

[6] Yu Q. Characterizations of various matchings in graphs. Australsa J Combin, 1993, 7: 55--64

[7] Plummer M D. On $n$-extendable graphs. Discrete Math, 1980, 31: 201--210

[8] Lou D. Some conditions for $k$-extendable graph. Australas J Combin, 1994, 9: 123--136

[9] Lou D, Holton D A. Lower bounds of cyclic edge connectivity for n-extendability of regular graphs. Discrete Math, 1993, 112: 139--150

[10] Plummer M D. Extending matchings in planar graphs IV. Discrete Math, 1992, 109: 207--219

[11] Plummer M D. Extending matchings in graphs: a survey. Discrete Math, 1994, 127: 277--292

[12] Plummer M D. Extending matchings in graphs: an update. Congr Numer, 1996, 116: 3--32

[13] Györi E, Plummer M D. The Cartesian product of a k-extendable and an m-extendable graph is (k+m+1)-extendable. Discrete Math, 1992, 101: 87--96

[14] Yu Q. A note on n-extendable graphs. J Graph Theory, 1992, 16: 349--353

[15] de Carvalho M H, Lucchesi C L, Murty U S R. Ear decompositions of matching covered graphs. Combinatorica, 1999, 19: 151--174

[16] de Carvalho M H, Lucchesi C L, Murty U S R. Optimal ear decompositions of 1-extendable graphs and bases for the matching lattice. J Combin Theory Ser B, 2002, 85: 59--93

[17] de Carvalho M H, Lucchesi C L, Murty U S R. On a conjecture of Lov\'{a}sz concerning bricks, I. The characteristic of 1-extendable graph. J Combin Theory Ser B, 2002, 85: 94--136

[18] de Carvalho M H, Lucchesi C L, Murty U S R. On a conjecture of Lov\'{a}sz concerning bricks, II. Bricks of finite characteristic. J Combin Theory Ser B, 2002, 85: 137--180

[19] Lov\'{a}sz L. Matching structure and the matching lattice. J Combin Theory Ser B, 1987, 43: 187--222

[20] Murty U S R. The Matching Lattice and Related Topics, Preliminary Report. Waterloo (Canada): University of Waterloo, 1994

[21] Jin Z, Yan H, Yu Q. Generalization of matching extension in graphs (II). Submitted

[22] Chen C. Binging number and toughness for matching extension. Discrete Math, 1995, 146: 303--306