An existence theorem on Hamiltonian \((g,f)\)-factors in networks

Volume 11, Issue 1, pp 1--7

Publication Date: 2017-12-22


Sizhong Zhou - School of Science, Jiangsu University of Science and Technology, Mengxi Road 2, Zhenjiang, Jiangsu 212003, P. R. China


Let \(a,b\), and \(r\) be nonnegative integers with \(\max\{3,r+1\}\leq a<b-r\), let \(G\) be a graph of order \(n\), and let \(g\) and \(f\) be two integer-valued functions defined on \(V(G)\) with \(\max\{3,r+1\}\leq a\leq g(x)<f(x)-r\leq b-r\) for any \(x\in V(G)\). In this article, it is proved that if \(n\geq\frac{(a+b-3)(a+b-5)+1}{a-1+r}\) and \({\rm bind}(G)\geq\frac{(a+b-3)(n-1)}{(a-1+r)n-(a+b-3)}\), then \(G\) admits a Hamiltonian \((g,f)\)-factor.


Network, graph, binding number


[1] B. Alspach, K. Heinrich, G. Z. Liu, Orthogonal factorizations of graphs, Contemporary design theory, Wiley-Intersci. Ser. Discrete Math. Optim., Wiley-Intersci. Publ., Wiley, New York, (1992), 13–40.
[2] J.-S. Cai, G.-Z. Liu, Binding number and Hamiltonian (g, f)-factors in graphs, J. Appl. Math. Comput., 25 (2007), 383–388.
[3] W. Gao, A sufficient condition for a graph to be a fractional (a, b, n)-critical deleted graph, Ars Combin., 119 (2015), 377–390.
[4] W. Gao, W.-F. Wang, Toughness and fractional critical deleted graph, Util. Math., 98 (2015), 295–310.
[5] K. Kimura, f-factors, complete-factors, and component-deleted subgraphs, Discrete Math., 313 (2013), 1452–1463.
[6] M. Kouider, S. Ouatiki, Sufficient condition for the existence of an even [a, b]-factor in graph, Graphs Combin., 29 (2013), 1051–1057.
[7] G.-Z. Liu, B.-H. Zhu, Some problems on factorizations with constraints in bipartite graphs, Discrete Appl. Math., 128 (2003), 421–434.
[8] L. Lov´asz, Subgraphs with prescribed valencies, J. Combinatorial Theory, 8 (1970), 391–416.
[9] H.-L. Lu, D. G. L. Wang, On Cui-Kano’s characterization problem on graph factors, J. Graph Theory, 74 (2013), 335–343.
[10] H. Matsuda, Degree conditions for Hamiltonian graphs to have [a, b]-factors containing a given Hamiltonian cycle, Discrete Math., 280 (2004), 241–250.
[11] Y.-S. Nam, Ore-type condition for the existence of connected factors, J. Graph Theory, 56 (2007), 241–248.
[12] D. R. Woodall, The binding number of a graph and its Anderson number, J. Combinatorial Theory Ser. B, 15 (1973), 225–255.
[13] S.-Z. Zhou, Some new sufficient conditions for graphs to have fractional k-factors, Int. J. Comput. Math., 88 (2011), 484–490.
[14] S.-Z. Zhou, A new neighborhood condition for graphs to be fractional (k,m)-deleted graphs, Appl. Math. Lett., 25 (2012), 509–513.
[15] S.-Z. Zhou, Toughness and the existence of Hamiltonian [a, b]-factors of graphs, Util. Math., 90 (2013), 187–197.
[16] S.-Z. Zhou, Remarks on orthogonal factorizations of digraphs, Int. J. Comput. Math., 91 (2014), 2109–2117.
[17] S.-Z. Zhou, Some results about component factors in graphs, RAIRO-Oper. Res., (2017), accepted.
[18] S.-Z. Zhou, Q.-J. Bian, ubdigraphs with orthogonal factorizations of digraphs (II), European J. Combin., 36 (2014), 198–205.


XML export