|Table of Contents|

[1] Yang Hongchen, Xue Xiuqian,. Two conditions for a bipartite graph to be a k-deleted graph [J]. Journal of Southeast University (English Edition), 2003, 19 (2): 197-199. [doi:10.3969/j.issn.1003-7985.2003.02.021]
Copy

Two conditions for a bipartite graph to be a k-deleted graph()
二分图为k-消去图的2个条件
Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:
19
Issue:
2003 2
Page:
197-199
Research Field:
Mathematics, Physics, Mechanics
Publishing date:
2003-06-30

Info

Title:
Two conditions for a bipartite graph to be a k-deleted graph
二分图为k-消去图的2个条件
Author(s):
Yang Hongchen, Xue Xiuqian
College of Sciences, China University of Mining and Technology, Xuzhou 221008, China
杨宏晨, 薛秀谦
中国矿业大学理学院, 徐州 221008
Keywords:
bipartite graph;  k-factor;  k-deleted graph
二分图;  k-因子;  k-消去图
PACS:
O157.5
DOI:
10.3969/j.issn.1003-7985.2003.02.021
Abstract:
A k-regular spanning subgraph of graph G is called a k-factor of G. Graph G is called a k-deleted graph if G-e has a k-factor for each edge e. A graph G=(X, Y) with bipartition (X, Y) is called a bipartite graph if every edge of G has one endpoint in X and the other in Y.It is proved that a bipartite graph G=(X, Y) with |X|=|Y| is a k-deleted graph if and only if k|S|≤r1+2r2+…+k(rk+…+rΔ)-ε(S) for all S⊆X. Using this result we give a sufficient neighborhood condition for a bipartite to be a k-deleted graph.
图G的一个k-正则支撑子图称为G的k-因子.若对G的任一边e, 图G总存在一个k-因子不含e, 则称G是k-消去图.若图G存在一个划分(X, Y)使得G的每条边的端点分别在X和Y中, 则称G=(X, Y)为二分图.证明了二分图G=(X, Y)且|X|=|Y|是k-消去图的充分必要条件是k|S|≤r1+2r2+…+k(rk+…+rΔ)-ε(S)对所有S⊆X成立.并由此给出二分图是k-消去图的一个邻集充分条件

References:

[1] Bondy J A, Murty U S R. Graph theory with application [M].London:Macmillan Press, 1976.
[2] Liu Guizhen.(g, f)-factors and factorizations of graphs [J]. Acta Math Sinica, 1994, 37(2):230-237.
[3] Wang Changping. Several new results for k-deleted graphs [J]. Acta Mathematics Scientia, 1998, 18(3):302-309.(in Chinese)
[4] Qian Jianbo. Degree conditions and the existence of k-factors in a bipartite graph [J]. Mathematics Applicata, 2000, 13(1):66-69.(in Chinese)
[5] Chen Ciping. Neighborhood conditions for factors in graphs [J]. Mathematics Applicata, 1992, 5(3):47-52.
[6] Ore O. Theory of graphs [M].American Mathematics Society College Publishers, 1962.

Memo

Memo:
Biography: Yang Hongchen(1964—), male, lecturer, yanghongc@sina.com.
Last Update: 2003-06-20