×

zbMATH — the first resource for mathematics

Research on fractional critical covered graphs. (English. Russian original) Zbl 1458.05221
Probl. Inf. Transm. 56, No. 3, 270-277 (2020); translation from Probl. Peredachi Inf. 56, No. 5, 77-85 (2020).
Summary: A graph \(G\) is called a fractional \((g, f)\)-covered graph if for any \(e \in E(G), G\) admits a fractional \((g, f)\)-factor covering \(e\). A graph \(G\) is called a fractional \((g, f, n)\)-critical covered graph if for any \(S \subseteq V(G)\) with \(\vert S \vert = n\), \(G - S\) is a fractional \((g, f)\)-covered graph. A fractional \((g, f, n)\)-critical covered graph is said to be a fractional \((a, b, n)\)-critical covered graph if \(g(x) = a\) and \(f(x) = b\) for every \(x \in V(G)\). A fractional \((a, b, n)\)-critical covered graph was first defined and studied in [S. Zhou et al., Inf. Process. Lett. 152, Article ID 105838, 5 p. (2019; Zbl 07115185)]. In this article, we investigate fractional \((g, f, n)\)-critical covered graphs and present a binding number condition for the existence of fractional \((g, f, n)\)-critical covered graphs, which is an improvement and generalization of a previous result obtained in [Y. Yuan and R.-X. Hao, Bull. Malays. Math. Sci. Soc. (2) 43, No. 1, 157–167 (2020; Zbl 1433.05264)].

MSC:
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C72 Fractional graph theory, fuzzy graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Zhou, S., Xu, Y., and Sun, Z., Degree Conditions for Fractional (a,b,k)-Critical Covered Graphs, Inform. Process. Lett., 2019, vol. 152, Article 105838 (5 pp.). · Zbl 07115185
[2] Yuan, Y.; Hao, R-X, Neighborhood Union Conditions for Fractional [a, b]-Covered Graphs, Bull. Malays. Math. Sci. Soc., 43, 1, 157-167 (2020) · Zbl 1433.05264
[3] Liu, G.; Zhang, L., Characterizations of Maximum Fractional (g, f)-Factors of Graphs, Discrete Appl. Math., 156, 12, 2293-2299 (2008) · Zbl 1144.05051
[4] Belck, H-B, Reguläre Faktoren von Graphen, J. Reine Angew. Math., 188, 228-252 (1950) · Zbl 0040.26001
[5] Enomoto, H.; Jackson, B.; Katerinis, P.; Satio, A., Toughness and the Existence of k-Factors, J. Graph Theory, 9, 1, 87-95 (1957) · Zbl 0598.05054
[6] Katerinis, P.; Woodall, DR, Binding Numbers of Graphs and the Existence of k-Factors, Quart. J. Math. Oxford Ser. (2), 38, 150, 221-228 (1987) · Zbl 0639.05050
[7] Plummer, MD; Saito, A., Toughness, Binding Number and Restricted Matching Extension in a Graph, Discrete Math., 340, 11, 2665-2672 (2017) · Zbl 1369.05176
[8] Kano, M.; Tokushige, N., Binding Numbers and f-Factors of Graphs, J. Combin. Theory Ser. B, 54, 2, 213-221 (1992) · Zbl 0772.05080
[9] Cymer, R.; Kano, M., Generalizations of Marriage Theorem for Degree Factors, Graphs Combin., 32, 6, 2315-2322 (2016) · Zbl 1353.05096
[10] Lovász, L., Subgraphs with Prescribed Valencies, J. Combin. Theory, 8, 391-416 (1970) · Zbl 0198.29201
[11] Egawa, Y.; Kano, M., Sufficient Conditions for Graphs to Have (g, f)-Factors, Discrete Math., 151, 1-3, 87-90 (1996) · Zbl 0853.05061
[12] Matsuda, H., A Neighborhood Condition for Graphs to Have [a, b]-Factors, Discrete Math., 224, 1-3, 289-292 (2000) · Zbl 0966.05062
[13] Kouider, M.; Ouatiki, S., Sufficient Condition for the Existence of an Even [a, b]-Factor in Graph, Graphs Combin., 29, 4, 1051-1057 (2013) · Zbl 1268.05161
[14] Zhou, S.; Zhang, T.; Xu, Z., Subgraphs with Orthogonal Factorizations in Graphs, Discrete Appl. Math., 286, 29-34 (2020) · Zbl 1448.05166
[15] Zhou, S. and Sun, Z., Binding Number Conditions for P_≥2-Factor and P_≥3-Factor Uniform Graphs, Discrete Math., 2020, vol. 343, no. 3, Article 111715 (6 pp.).
[16] Zhou, SZ; Sun, ZR, Some Existence Theorems on Path Factors with Given Properties in Graphs, Acta Math. Sin. (Engl. Ser.), 36, 8, 917-928 (2020) · Zbl 1447.05177
[17] Liu, G.Z., On (g, f)-Covered Graphs, Acta Math. Sci. (English Ed.), 1988, vol. 8, no. 2, pp. 181-184. · Zbl 0682.05051
[18] Anstee, RP, An Algorithmic Proof of Tutte’s f-Factor Theorem, J. Algorithms, 6, 1, 112-131 (1985) · Zbl 0562.05038
[19] Liu, G.; Zhang, L., Toughness and the Existence of Fractional k-Factors of Graphs, Discrete Math., 308, 9, 1741-1748 (2008) · Zbl 1136.05059
[20] Katerinis, P., Fractional ℓ-Factors in Regular Graphs, Australas. J. Combin., 73, Part 3, 432-439 (2019) · Zbl 1411.05186
[21] Zhou, S.; Sun, Z.; Ye, H., A Toughness Condition for Fractional (k, m)-Deleted Graphs, Inform. Process. Lett., 113, 8, 255-259 (2013) · Zbl 1273.05128
[22] Gao, W.; Wang, WF; Guirao, JLG, The Extension Degree Conditions for Fractional Factor, Acta Math. Sin. (Engl. Ser.), 36, 3, 305-317 (2020) · Zbl 1442.05176
[23] Zhou, S.; Xu, L.; Xu, Z., Remarks on Fractional ID-k-Factor-Critical Graphs, Acta Math. Appl. Sin. Engl. Ser., 35, 2, 458-464 (2019) · Zbl 1416.05238
[24] Yuan, Y.; Hao, R-X, Toughness Condition for the Existence of All Fractional (a, b, k)-Critical Graphs, Discrete Math., 342, 8, 2308-2314 (2019) · Zbl 1418.05111
[25] Lu, H.; Yu, Q., General Fractional f-Factor Numbers of Graphs, Appl. Math. Lett., 24, 4, 519-523 (2011) · Zbl 1215.05133
[26] Li, Z.; Yan, G.; Zhang, X., On Fractional (g, f)-Covered Graphs, OR Trans. (in Chinese), 6, 4, 65-68 (2002)
[27] Zhou, S., Wu, J., and Liu, H., Independence Number and Connectivity for Fractional (a, b, k)-Critical Covered Graphs, arXiv:1909.01070[math.CO], 2019.
[28] Lv, X., A Degree Condition for Fractional (g, f, n)-Critical Covered Graphs, AIMS Math., 5, 2, 872-878 (2020)
[29] Zhou, S., Remarks on Orthogonal Factorizations of Digraphs, Int. J. Comput. Math., 91, 10, 2109-2117 (2014) · Zbl 1303.05159
[30] Zhou, S.; Sun, Z.; Xu, Z., A Result on r-Orthogonal Factorizations in Digraphs, European J. Combin., 65, 15-23 (2017) · Zbl 1369.05096
[31] Zhou, S.; Sun, Z.; Liu, H., Sun Toughness and P_≥3-Factors in Graphs, Contrib. Discrete Math., 14, 1, 167-174 (2019) · Zbl 1444.05115
[32] Zhou, S.; Yang, F.; Xu, L., Two Sufficient Conditions for the Existence of Path Factors in Graphs, Sci. Iran. D: Comput. Sci. Eng. Electr. Eng., 26, 6, 3510-3514 (2019)
[33] Zhou, S., Remarks on Path Factors in Graphs, RAIRO—Oper. Res., 54, 6, 1827-1834 (2020)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.