[a, b]-Factors Excluding Some Specified Edges In Graphs

Authors: Sizhong Zhou, Bingyuan Pu

Abstract:

Let G be a graph of order n, and let a, b and m be positive integers with 1 ≤ a<b. An [a, b]-factor of G is defined as a spanning subgraph F of G such that a ≤ dF (x) ≤ b for each x ∈ V (G). In this paper, it is proved that if n ≥ (a+b−1+√(a+b+1)m−2)2−1 b and δ(G) > n + a + b − 2 √bn+ 1, then for any subgraph H of G with m edges, G has an [a, b]-factor F such that E(H)∩ E(F) = ∅. This result is an extension of thatof Egawa [2].

Keywords: graph, minimum degree, [a, b]-factor.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1330351

References:

[1] B. Alspach, K. Heinrich, G. Liu, Contemporary design theory-A collection of surveys, Wiley, New York, 1992, 13-37.
[2] Y. Egawa, H. Enomoto, Sufficient conditions for the existence of kfactors, Recent Studies in Graph Theory, Vishwa International Publication, India, 1989, 96-105.
[3] M. Kano, H. Matsuda, A neighborhood condition for graphs to have
[a, b]-factors, LNCS, 4381(2007), 70-78.
[4] P. B. C. Lam, G. Liu, G. Li, W. C. Shiu, Orthogonal (g, f)-factorizations in networks, Networks, 35(2000), 274-278.
[5] Sizhong Zhou, Some sufficient conditions for graphs to have (g, f)- factors, Bulletin of the Australian Mathematical Society, 75(2007), 447- 452.
[6] Sizhong Zhou, Binding numbers of graphs and the existence of
[a, b]- factors, Journal of Systems Science and Mathematical Sciences (in Chinese), 29(4)(2009), 484-489.