Article in volume
Authors:
Title:
Two sufficient conditions for component factors in graphs
PDFSource:
Discussiones Mathematicae Graph Theory 43(3) (2023) 761-766
Received: 2020-10-09 , Revised: 2021-02-20 , Accepted: 2021-02-21 , Available online: 2021-03-17 , https://doi.org/10.7151/dmgt.2401
Abstract:
Let $G$ be a graph. For a set $\mathcal{H}$ of connected graphs, a spanning
subgraph $H$ of a graph $G$ is called an $\mathcal{H}$-factor of $G$ if each
component of $H$ is isomorphic to a member of $\mathcal{H}$. An
$\mathcal{H}$-factor is also referred as a component factor. If $G-e$ admits
an $\mathcal{H}$-factor for any $e\in E(G)$, then we say that $G$ is an
$\mathcal{H}$-factor deleted graph. Let $k\geq2$ be an integer. In this article,
we verify that (\romannumeral1) a graph $G$ admits a $\{K_{1,1},K_{1,2},\dots,
K_{1,k},\mathcal{T}(2k+1)\}$-factor if and only if its binding number
$bind(G)\geq\frac{2}{2k+1}$; (\romannumeral2) a graph $G$ with $\delta(G)\geq2$
is a $\{K_{1,1},K_{1,2},\dots,K_{1,k},\mathcal{T}(2k+1)\}$-factor deleted graph
if its binding number $bind(G)\geq\frac{2}{2k-1}$.
Keywords:
graph, minimum degree, binding number, $\mathcal{H}$-factor, $\mathcal{H}$-factor deleted graph
References:
- J. Akiyama and M. Kano, Factors and Factorizations of Graphs, Lect. Note Math. 2031 (Springer, Berlin, Heidelberg, 2011).
https://doi.org/10.1007/978-3-642-21919-1_1 - A. Amahashi and M. Kano, On factors with given components, Discrete Math. 42 (1982) 1–6.
https://doi.org/10.1016/0012-365X(82)90048-6 - W. Gao, W. Wang and Y. Chen, Tight bounds for the existence of path factors in network vulnerability parameter settings, International Journal of Intelligent Systems 36 (2021) 1133–1158.
https://doi.org/10.1002/int.22335 - M. Kano, H. Lu and Q. Yu, Component factors with large components in graphs, Appl. Math. Lett. 23 (2010) 385–389.
https://doi.org/10.1016/j.aml.2009.11.003 - M. Kano, H. Lu and Q. Yu, Fractional factors, component factors and isolated vertex conditions in graphs, Electron. J. Combin. 26(4) (2019) #P4.33.
https://doi.org/10.37236/8498 - M. Kano and A. Saito, Star-factors with large components, Discrete Math. 312 (2012) 2005–2008.
https://doi.org/10.1016/j.disc.2012.03.017 - M. Plummer and A. Saito, Toughness, binding number and restricted matching extension in a graph, Discrete Math. 340 (2017) 2665–2672.
https://doi.org/10.1016/j.disc.2016.10.003 - W.T. Tutte, The $1$-factors of oriented graphs, Proc. Amer. Math. Soc. 4 (1953) 922–931.
https://doi.org/10.2307/2031831 - S. Wang and W. Zhang, Research on fractional critical covered graphs, Probl. Inf. Transm. 56 (2020) 270–277.
https://doi.org/10.1134/S0032946020030047 - J. Yu and G. Liu, Binding number and minimum degree conditions for graphs to have fractional factors, J. Shandong Univ. 39 (2004) 1–5.
- Y. Zhang, G. Yan and M. Kano, Star-like factors with large components, J. Oper. Res. Soc. China 3 (2015) 81–88.
https://doi.org/10.1007/s40305-014-0066-7 - S. Zhou, Binding numbers and restricted fractional $(g,f)$-factors in graphs, Discrete Appl. Math. 305 (2021) 350–356.
https://doi.org/10.1016/j.dam.2020.10.017 - S. Zhou, Remarks on path factors in graphs, RAIRO Oper. Res. 54 (2020) 1827–1834.
https://doi.org/10.1051/ro/2019111 - S. Zhou, Some results on path-factor critical avoidable graphs, Discuss. Math. Graph Theory 43 (2023) 233–244.
https://doi.org/10.7151/dmgt.2364 - S. Zhou, H. Liu and Y. Xu, Binding numbers for fractional $(a,b,k)$-critical covered graphs, Proc. Rom. Acad. Ser. A Math. Phys. Tech. Sci. Inf. Sci. 21 (2020) 115–121.
- S. Zhou and Z. Sun, Binding number conditions for $P_{\geq2}$-factor and $P_{\geq3}$-factor uniform graphs, Discrete Math. 343(3) (2020) 111715.
https://doi.org/10.1016/j.disc.2019.111715 - S. Zhou and Z. Sun, Some existence theorems on path factors with given properties in graphs, Acta Math. Sin. (Engl. Ser.) 36 (2020) 917–928.
https://doi.org/10.1007/s10114-020-9224-5
Close