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

张文勇; 李晓玲; 赵飚

您当前的位置：

首页 >

文章列表页 >

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

数理科学 | 更新时间：2026-01-21

- 偶匹配可扩图的度和连通度条件(英文)
- 偶匹配可扩图的度和连通度条件(英文)
- 新疆大学学报（自然科学版中英文） 2010年27卷第4期页码：408-412
- 作者机构：
  
  新疆大学数学与系统科学学院
- 作者简介：
- 基金信息：
  
  supported by NSFC(No.10671165)
- DOI：
  中图分类号： O157.5
- 纸质出版：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.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

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

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

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

一类苯系统的克拉公式

凸六角系统(Ⅱ)