Article ID Journal Published Year Pages File Type
8903167 Discrete Mathematics 2018 9 Pages PDF
Abstract
Let a and b be two positive integers such that a≤b and a≡b(mod2). 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∈V(F), dF(v)≡b(mod2) and a≤dF(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, δ(G)≥(b−a)∕a+a, and for any two nonadjacent vertices u,v∈V(G), max{dG(u),dG(v)}≥ana+b. This extends an earlier result of Nishimura (1992) and strengthens a result of Cai and Li (1998).
Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,