偶匹配可扩图的度和连通度条件(英文)

张文勇; 李晓玲; 赵飚

您当前的位置：

首页 >

文章列表页 >

偶匹配可扩图的度和连通度条件(英文)

更新时间：2026-01-21

- 偶匹配可扩图的度和连通度条件(英文)
- Journal of Xinjiang University (Natural Science Edition in Chinese and English) Vol. 27, Issue 4, Pages: 408-412(2010)
- 作者机构：
  
  新疆大学数学与系统科学学院
- 作者简介：
- 基金信息：
- DOI：
  CLC： O157.5
- Published：2010
- 稿件说明：
移动端阅览
[1]张文勇,李晓玲,赵飚.偶匹配可扩图的度和连通度条件(英文)[J].新疆大学学报(自然科学版),2010,27(04):408-412.

张文勇, 李晓玲, 赵飚. 偶匹配可扩图的度和连通度条件(英文)[J]. Journal of Xinjiang University (Natural Science Edition in Chinese and English), 2010, 27(4): 408-412.
[1]张文勇,李晓玲,赵飚.偶匹配可扩图的度和连通度条件(英文)[J].新疆大学学报(自然科学版),2010,27(04):408-412. DOI：

张文勇, 李晓玲, 赵飚. 偶匹配可扩图的度和连通度条件(英文)[J]. Journal of Xinjiang University (Natural Science Edition in Chinese and English), 2010, 27(4): 408-412. DOI：

摘要

称图G是偶匹配可扩的

是指G的每一个导出二部偶子图的任意完美匹配都可以扩充为G的一个完美匹配.记δk(G)为一个k元独立集的最小度和

κ(G)为图G的连通度.在本文章中

给出了2n个顶点的图G满足κ(G)≥2(n/2)+1

和δ3(G) ≥ 3(3n/2)-2.那么G是偶匹配可扩的.并给出例子说明两个条件都是紧的.

Abstract

A graph G is said to be bipartite matching extendable if every matching M which is a perfect matching of an induced bipartite subgraph can be extended to a perfect matching of G.For a graph G

let δ k (G) be the minimum degree sum of an independent set of k vertices

let κ(G) be the connectivity of a graph G.In this paper

we prove that if G is a graph of order 2n with κ(G) ≥ 2 (n/2)+1 and δ 3 (G) ≥ 3 (3n/2)-2

then G is bipartite matching extendable graph.We also show that the bound for the conditions are almost the best possible.

关键词

Keywords

references

Plummer M D. On n-extendablegraphs[J]. Discrete Mathematics,1980,31:201-210.

Xu R,Yu Q L. Degree sum conditions for k-extendable graphs[J]. Congr Number,2003,63:189-195.

Lovasz L,Plummer M D. Matching Theory[M]. Elsevier Science Publishers,B V North Holland,1985.

Plummer M D. Extending matching in graphs: a survey[J]. Discrete Mathematics,1994,127:277-292.

YU Q L. A note on n-extendable graphs[J]. Journal of Graph Theory,1992,16:349-353.

Caneron K. Induced matchings[J]. Discrete Apple Math,1989,24:97-102.

Yuan J J. Induced matching extendable graph[J]. Journal of Graph Theory,1998,28:203-313.

Liu Y,Yuan J J,Wang S Y. Degree conditions of induced matching extendable graphs[J]. Appl Math JCU,2000,15B 1:1-6.

Wang Q,Yuan J J. Degree sum conditions of induced matching extendable graphs[J],Zhengzhou Univ,2000,32(1):19-21.

Bondy J A,Murty U S R. Graph Theory with Applications[M]. American Elsevier,New York,1796.

Wang X M,Zhang Z K,Lin Y X. Bipartite matching extendable graphs[J]. Discrete Mathematics,2008,1-8.

Wang X M,Zhang Z K,Lin Y X. Degree-type conditions for bipartite matching extendability[J],accepted by Ars Combinatoria.

Ore O. Note on Hamiltoncircuits[J]. Amero Math Monthly,1960,67:55.

Denise Amar,Evelyne Flandrin,Grzegorz Gancarzewicz. A degree condition implying that every matching is contained in a hamiltonian cycle[J]. Discrete Mathematics,2008,1-11.

Sun Z,Tian F,Wei B. Degree sums connectivity and dominating cycles in graphs[J]. Graphs Combin. 2001,17:555-564.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

具有强互反性的双圈图的刻画(英文)

关于全图补图的完美匹配(英文)

六角系统中完美匹配的覆盖与对应(英文)

一类苯系统的克拉公式

凸六角系统(Ⅱ)

Related Author

陈琳

黄琼湘

王晓芳

马国燕

陈荣斯

张福基

张和平

张云浒

Related Institution

新疆医科大学医学工程技术学院

新疆大学 ,福州大学

新疆大学数学系

新疆大学 ,厦门大学 ,新疆大学

新疆大学,兰州大学,

⁰