Article in volume
Authors:
Title:
Some results on path-factor critical avoidable graphs
PDFSource:
Discussiones Mathematicae Graph Theory 43(1) (2023) 233-244
Received: 2020-06-09 , Revised: 2020-09-03 , Accepted: 2020-09-03 , Available online: 2020-10-02 , https://doi.org/10.7151/dmgt.2364
Abstract:
A path factor is a spanning subgraph $F$ of $G$ such that every component of
$F$ is a path with at least two vertices. We write $P_{\geq k}=\{P_i:i\geq k\}$.
Then a $P_{\geq k}$-factor of $G$ means a path factor in which every component
admits at least $k$ vertices, where $k\geq2$ is an integer. A graph $G$ is
called a $P_{\geq k}$-factor avoidable graph if for any $e\in E(G)$, $G$ admits
a $P_{\geq k}$-factor excluding $e$. A graph $G$ is called a
$(P_{\geq k},n)$-factor critical avoidable graph if for any $Q\subseteq V(G)$
with $|Q|=n,$ $G-Q$ is a $P_{\geq k}$-factor avoidable graph. Let $G$ be an
$(n+2)$-connected graph. In this paper, we demonstrate that (i)
$G$ is a $(P_{\geq2},n)$-factor critical avoidable graph if $tough(G)>
\frac{n+2}{4}$; (ii) $G$ is a $(P_{\geq3},n)$-factor critical
avoidable graph if $tough(G)>\frac{n+1}{2}$; (iii) $G$ is a
$(P_{\geq2},n)$-factor critical avoidable graph if $I(G)>\frac{n+2}{3}$;
(iv) $G$ is a $(P_{\geq3},n)$-factor critical avoidable graph if
$I(G)>\frac{n+3}{2}$. Furthermore, we claim that these conditions are sharp.
Keywords:
graph, toughness, isolated toughness, $P_{\geq k}$-factor, $(P_{\geq k},n)$-factor critical avoidable graph
References:
- S. Belcastro and M. Young, $1$-factor covers of regular graphs, Discrete Appl. Math. 159 (2011) 281–287.
https://doi.org/10.1016/j.dam.2010.12.003 - V. Chvátal, Tough graphs and Hamiltonian circuits, Discrete Math. 5 (1973) 215–228.
https://doi.org/10.1016/0012-365X(73)90138-6 - Y. Egawa, M. Furuya and K. Ozeki, Sufficient conditions for the existence of a path-factor which are related to odd components, J. Graph Theory 89 (2018) 327–340.
https://doi.org/10.1002/jgt.22253 - H. Enomoto, B. Jackson, P. Katerinis and A. Saito, Toughness and the existence of $k$-factors, J. Graph Theory 9 (1985) 87–95.
https://doi.org/10.1002/jgt.3190090106 - W. Gao, J.L.C. Guirao and Y.J. Chen, A toughness condition for fractional $(k,m)$-deleted graphs revisited, Acta Math. Sin. (Engl. Ser.) 35 (2019) 1227–1237.
https://doi.org/10.1007/s10114-019-8169-z - W. Gao, L. Liang and Y. Chen, An isolated toughness condition for graphs to be fractional $(k,m)$-deleted graphs, Util. Math. 105 (2017) 303–316.
- A. Kaneko, A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two, J. Combin. Theory Ser. B 88 (2003) 195–218.
https://doi.org/10.1016/S0095-8956(03)00027-3 - 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 - P. Katerinis, Toughness of graphs and the existence of factors, Discrete Math. 80 (1990) 81–92.
https://doi.org/10.1016/0012-365X(90)90297-U - A. Kelmans, Packing $3$-vertex paths in claw-free graphs and related topics, Discrete Appl. Math. 159 (2011) 112–127.
https://doi.org/10.1016/j.dam.2010.05.001 - M. Las Vergnas, An extension of Tutte's $1$-factor theorem, Discrete Math. 23 (1978) 241–255.
https://doi.org/10.1016/0012-365X(78)90006-7 - 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. Yang, Y. Ma and G. Liu, Fractional $(g,f)$-factors in graphs, Appl. Math. J. Chinese Univ. Ser. A 16 (2001) 385–390.
- S. Zhou, Remarks on orthogonal factorizations of digraphs, Int. J. Comput. Math. 91 (2014) 2109–2117.
https://doi.org/10.1080/00207160.2014.881993 - S. Zhou, Remarks on path factors in graphs, RAIRO Oper. Res. 54 (2020) 1827–1834.
https://doi.org/10.1051/ro/2019111 - 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 (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 - S. Zhou, Z. Sun and Q. Pan, A sufficient condition for the existence of restricted fractional $(g,f)$-factors in graphs, Probl. Inf. Transm. 56 (2020(4)) 35–49.
https://doi.org/10.31857/S055529232004004X - S. Zhou, Z. Sun and H. Ye, A toughness condition for fractional $(k,m)$-deleted graphs, Inform. Process. Lett. 113 (2013) 255–259.
https://doi.org/10.1016/j.ipl.2013.01.021 - S. Zhou, Y. Xu and Z. Sun, Degree conditions for fractional $(a,b,k)$-critical covered graphs, Inform. Process. Lett. 152 (2019) 105838.
https://doi.org/10.1016/j.ipl.2019.105838 - S. Zhou, F. Yang and L. Xu, Two sufficient conditions for the existence of path factors in graphs, Scientia Iranica 26 (2019) 3510–3514.
https://doi.org/10.24200/sci.2018.5151.1122 - S. Zhou, T. Zhang and Z. Xu, Subgraphs with orthogonal factorizations in graphs, Discrete Appl. Math. 286 (2020) 29–34.
https://doi.org/10.1016/j.dam.2019.12.011
Close