Abstract
Let G be a graph, and k a positive integer. A graph G is fractional independent-set-deletable k-factor-critical (in short, fractional ID-k-factor-critical) if G - I has a fractional k-factor for every independent set I of G. In this paper, we present a sufficient condition for a graph to be fractional ID-k-factor-critical, depending on the minimum degree and the neighborhoods of independent sets. Furthermore, it is shown that this result in this paper is best possible in some sense.
Similar content being viewed by others
References
Chang, R., Liu, G., Zhu, Y. Degree conditions of fractional ID-k-factor-critical graphs. Bulletin of the Malaysian Mathematical Sciences Society, 33(3): 355–360 (2010)
Fourtounelli, O., Katerinis, P. The existence of k-factors in squares of graphs. Discrete Mathematics, 310(23): 3351–3358 (2010)
Liu, G., Yu, Q., Zhang, L. Maximum fractional factors in graphs. Applied Mathematics Letters, 20(12): 1237–1243 (2007)
Liu, G., Zhang, L. Fractional (g, f)-factors of graphs. Acta Mathematica Scientia, 21B(4): 541–545 (2001)
Liu, G., Zhang, L. Toughness and the existence of fractional k-factors of graphs. Discrete Mathematics}, 308: 1741–1748 (2008)
Liu, H., Liu, G. Binding number and minimum degree for the existence of (g, f, n)-critical graphs. Journal of Applied Mathematics and Computing, 29(1–2): 207–216 (2009)
Scheinerman, E. R., Ullman, D. H. Fractional Graph Theory. New York, John Wiley and Sons, Inc. (1997)
Woodall, D. R. k-factors and neighbourhoods of independent sets in graphs. J. London Math. Soc., 41(2): 385–392 (1990)
Zhou, S. A new neighborhood condition for graphs to be fractional (k, m)-deleted graphs. Applied Mathematics Letters, 25(3): 509–513 (2012)
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)
Zhou, S. Remarks on orthogonal factorizations of digraphs. International Journal of Computer Mathematics, 91(10): 2109–2117 (2014)
Zhou, S. Some results about component factors in graphs. RAIRO-Operations Research, DOI: 10.1051/ro/2017045.
Zhou, S. Some results on fractional k-factors. Indian Journal of Pure and Applied Mathematics, 40(2): 113–121 (2009)
Zhou, S., Sun, Z., Ye, H. A toughness condition for fractional (k, m)-deleted graphs. Information Processing Letters, 113(8): 255–259 (2013)
Zhou, S., Xu, L., Sun, Z. Independence number and minimum degree for fractional ID-k-factor-critical graphs. Aequationes Mathematicae, 84(1–2): 71–76 (2012)
Zhou, S., Yang, F., Xu, L. Two sufficient conditions for the existence of path factors in graphs. Scientia Iranica, DOI: 10.24200/SCI.2018.5151.1122.
Author information
Authors and Affiliations
Corresponding author
Additional information
This work is supported by the National Natural Science Foundation of China (Grant No. 11371009, 11501256, 61503160), Six Big Talent Peak of Jiangsu Province (Grant No. JY-022) and 333 Project of Jiangsu Province, the National Social Science Foundation of China (Grant No. 14AGL001), the Natural Science Foundation of Xinjiang Province of China (Grant No. 2015211A003) and the Natural Science Foundation of the Higher Education Institutions of Jiangsu Province (Grant No. 14KJD110002).
Rights and permissions
About this article
Cite this article
Zhou, Sz., Xu, L. & Xu, Zr. Remarks on Fractional ID-k-factor-critical Graphs. Acta Math. Appl. Sin. Engl. Ser. 35, 458–464 (2019). https://doi.org/10.1007/s10255-019-0818-6
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10255-019-0818-6