A degree condition for a graph to have (a, b)-parity factors

被引:14
作者
Liu, Haodong [1 ]
Lu, Hongliang [1 ]
机构
[1] Xi An Jiao Tong Univ, Dept Math, Xian 710049, Shaanxi, Peoples R China
基金
中国国家自然科学基金;
关键词
Degree condition; Parity factor; ODD;
D O I
10.1016/j.disc.2017.08.035
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let a and b be two positive integers such that a <= b and a equivalent to b (mod 2). A graph F is an (a, b)-parity factor of a graph G if F is a spanning subgraph of G and for all vertices v is an element of V(F), d(F)(v) equivalent to b (mod 2) and a <= d(p)(v) <= b. In this paper we prove that every connected graph G with n >= b(a + b)(a + b + 2)/(2a) vertices has an (a, b)-parity factor if na is even, delta(G) >= (b a)/a + a, and for any two nonadjacent vertices u, v is an element of V(G), max{dG(u), delta G(v)} >= an/a+b This extends an earlier result of Nishimura (1992) and strengthens a result of Cai and Li (1998). (C) 2017 Elsevier B.V. All rights reserved.
引用
收藏
页码:244 / 252
页数:9
相关论文
共 7 条
[1]   ON FACTORS WITH ALL DEGREES ODD [J].
AMAHASHI, A .
GRAPHS AND COMBINATORICS, 1985, 1 (02) :111-114
[2]  
CUI YT, 1988, J GRAPH THEOR, V12, P327
[3]   NEW SUFFICIENT CONDITIONS FOR CYCLES IN GRAPHS [J].
FAN, GH .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1984, 37 (03) :221-227
[4]  
Li YJ, 1998, J GRAPH THEOR, V27, P1, DOI 10.1002/(SICI)1097-0118(199801)27:1<1::AID-JGT1>3.0.CO
[5]  
2-U
[6]   FACTORIZATION OF GRAPHS .2. [J].
LOVASZ, L .
ACTA MATHEMATICA ACADEMIAE SCIENTIARUM HUNGARICAE, 1972, 23 (1-2) :223-246
[7]   A DEGREE CONDITION FOR THE EXISTENCE OF K-FACTORS [J].
NISHIMURA, T .
JOURNAL OF GRAPH THEORY, 1992, 16 (02) :141-151