×

A sufficient condition for the existence of a \(k\)-factor excluding a given \(r\)-factor. (English) Zbl 1375.05222

Summary: Let \(G\) be a graph, and let \(k,r\) be nonnegative integers with \(k\geq2\). A \(k\)-factor of \(G\) is a spanning subgraph \(F\) of \(G\) such that \(d_F(x)=k\) for each \(x\in V(G)\), where \(d_F(x)\) denotes the degree of \(x\) in \(F\). For \(S\subseteq V(G)\), \(N_G(S)=\bigcup_{x\in S}N_G(x)\). The binding number of \(G\) is defined by \(\operatorname{bind}(G)=\min\left\{\frac{|N_G(S)|}{|S|}:\emptyset \neq S\subset V(G), N_G(S)\neq V(G)\right\}\). In this paper, we obtain a binding number and neighborhood condition for a graph to have a \(k\)-factor excluding a given \(r\)-factor. This result is an extension of the previous results.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: DOI

References:

[1] W. Gao, Y. Gao, T. Xu and L. Liang, (2014), Vulnerability of Networks and Existence of Fractional Factor Avoiding Certain Channels and Sites, Journal of Computers 9, No 7, 1712-1722. doi 10.4304/jcp.9.7.1712-1722; Gao, W.; Gao, Y.; Xu, T.; Liang, L., Vulnerability of Networks and Existence of Fractional Factor Avoiding Certain Channels and Sites, Journal of Computers, 9, 7, 1712-1722 (2014) · doi:10.4304/jcp.9.7.1712-1722
[2] W. Gao and W. Wang, (2015), Toughness and fractional critical deleted graph, Utilitas Mathematica 98, 295-310.; Gao, W.; Wang, W., Toughness and fractional critical deleted graph, Utilitas Mathematica, 98, 295-310 (2015) · Zbl 1343.05124
[3] W. Gao, L. Liang, T. Xu and J. Zhou, (2014), Tight Toughness Condition for Fractional (g, f ,n)-Critical Graphs, Journal of the Korean Mathematical Society 51, No 1, 55-65. doi 10.4134/JKMS.2014.51.1.055; Gao, W.; Liang, L.; Xu, T.; Zhou, J., Tight Toughness Condition for Fractional (g, f ,n)-Critical Graphs, Journal of the Korean Mathematical Society, 51, 1, 55-65 (2014) · Zbl 1285.05147 · doi:10.4134/JKMS.2014.51.1.055
[4] J. Cai, G. Liu and J. Hou, (2008), Binding number and Hamiltonian (g, f )-factors in graphs II, International Journal of Computer Mathematics 85, No 9, 1325-1331. doi 10.1080/00207160701524368; Cai, J.; Liu, G.; Hou, J., Binding number and Hamiltonian (g, f)-factors in graphs II, International Journal of Computer Mathematics, 85, 9, 1325-1331 (2008) · Zbl 1144.05327 · doi:10.1080/00207160701524368
[5] S. Zhou, (2009), Independence number, connectivity and (a,b,k)-critical graphs, Discrete Mathematics 309, No 12, 4144-4148. doi 10.1016/j.disc.2008.12.013; Zhou, S., Independence number, connectivity and (a,b,k)-critical graphs, Discrete Mathematics, 309, 12, 4144-4148 (2009) · Zbl 1211.05067 · doi:10.1016/j.disc.2008.12.013
[6] S. Zhou, (2011), A sufficient condition for graphs to be fractional (k,m)-deleted graphs, Applied Mathematics Letters 24, No 9, 1533-1538. doi 10.1016/j.aml.2011.03.041; Zhou, S., A sufficient condition for graphs to be fractional (k,m)-deleted graphs, Applied Mathematics Letters, 24, 9, 1533-1538 (2011) · Zbl 1218.05159 · doi:10.1016/j.aml.2011.03.041
[7] S. Zhou, (2010), A sufficient condition for a graph to be an (a,b,k)-critical graph, International Journal of Computer Mathematics 87, No 10, 2202-2211. doi 10.1080/00207160902777914; Zhou, S., A sufficient condition for a graph to be an (a,b,k)-critical graph, International Journal of Computer Mathematics, 87, 10, 2202-2211 (2010) · Zbl 1198.05129 · doi:10.1080/00207160902777914
[8] S. Zhou, (2009), A minimum degree condition of fractional (k,m)-deleted graphs, Comptes Rendus Mathematique 347, No 21-22, 1223-1226. doi 10.1016/j.crma.2009.09.022; Zhou, S., A minimum degree condition of fractional (k,m)-deleted graphs, Comptes Rendus Mathematique, 347, 21-22, 1223-1226 (2009) · Zbl 1223.05032 · doi:10.1016/j.crma.2009.09.022
[9] S. Zhou, (2011), Some new sufficient conditions for graphs to have fractional k-factors, International Journal of Computer Mathematics 88, No 3, 484-490. doi 10.1080/00207161003681286; Zhou, S., Some new sufficient conditions for graphs to have fractional k-factors, International Journal of Computer Mathematics, 88, 3, 484-490 (2011) · Zbl 1230.05243 · doi:10.1080/00207161003681286
[10] S. Zhou, (2014), Remarks on orthogonal factorizations of digraphs, International Journal of Computer Mathematics 91, No 10, 2109-2117. doi 10.1080/00207160.2014.881993; Zhou, S., Remarks on orthogonal factorizations of digraphs, International Journal of Computer Mathematics, 91, 10, 2109-2117 (2014) · Zbl 1303.05159 · doi:10.1080/00207160.2014.881993
[11] I. Anderson, (1971), Perfect matchings of a graph, Journal of Combinatorial Theory, Series B 10, No 3, 183-186. doi 10.1016/0095-8956(71)90041-4; Anderson, I., Perfect matchings of a graph, Journal of Combinatorial Theory, Series B, 10, 3, 183-186 (1971) · Zbl 0172.48904 · doi:10.1016/0095-8956(71)90041-4
[12] D.R Woodall, (1973), The binding number of a graph and its Anderson number, Journal of Combinatorial Theory Series B 15, No 3, 225-255. doi 10.1016/0095-8956(73)90038-5; Woodall, D. R., The binding number of a graph and its Anderson number, Journal of Combinatorial Theory Series B, 15, 3, 225-255 (1973) · Zbl 0253.05139 · doi:10.1016/0095-8956(73)90038-5
[13] P. Katerinis and D.R Woodall, (1987), Binding numbers of graphs and the existence of k-factors, The Quarterly Journal of Mathematics 38, No 2, 221-228. doi 10.1093/qmath/38.2.221; Katerinis, P.; Woodall, D. R., Binding numbers of graphs and the existence of k-factors, The Quarterly Journal of Mathematics, 38, 2, 221-228 (1987) · Zbl 0639.05050 · doi:10.1093/qmath/38.2.221
[14] H. Matsuda, (2005), Regular Factors Containing a Given Hamiltonian Cycle, in: Combinatorial Geometry and Graph Theory, Vol 3330 of the series Lecture Notes in Computer Science, 123-132. doi 10.1007/978-3-540-30540-8_14; Matsuda, H., Regular Factors Containing a Given Hamiltonian Cycle, Combinatorial Geometry and Graph Theory, Vol 3330 of the series Lecture Notes in Computer Science, 123-132 (2005) · Zbl 1117.05091 · doi:10.1007/978-3-540-30540-8_14
[15] Y. Gao, G. Li and X. Li, (2009), Degree condition for the existence of a k-factor containing a given Hamiltonian cycle, Discrete Mathematics 309, No 8, 2373-2381. doi 10.1016/j.disc.2008.05.014; Gao, Y.; Li, G.; Li, X., Degree condition for the existence of a k-factor containing a given Hamiltonian cycle, Discrete Mathematics, 309, 8, 2373-2381 (2009) · Zbl 1214.05119 · doi:10.1016/j.disc.2008.05.014
[16] W. T. Tutte, (1952), The factors of graphs, Canadian Journal of Mathematics 4, No 3, 314-328. doi 10.4153/CJM-1952-028-2; Tutte, W. T., The factors of graphs, Canadian Journal of Mathematics, 4, 3, 314-328 (1952) · Zbl 0049.24202 · doi:10.4153/CJM-1952-028-2
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.