Sizhong Zhou ; Jiancheng Wu - Two sufficient conditions for graphs to admit path factors

fi:12212 - Fundamenta Informaticae, March 30, 2024, Volume 191, Issue 1
Two sufficient conditions for graphs to admit path factorsArticle

Authors: Sizhong Zhou ; Jiancheng Wu

    Let $\mathcal{A}$ be a set of connected graphs. Then a spanning subgraph $A$ of $G$ is called an $\mathcal{A}$-factor if each component of $A$ is isomorphic to some member of $\mathcal{A}$. Especially, when every graph in $\mathcal{A}$ is a path, $A$ is a path factor. For a positive integer $d\geq2$, we write $\mathcal{P}_{\geq d}=\{P_i|i\geq d\}$. Then a $\mathcal{P}_{\geq d}$-factor means a path factor in which every component admits at least $d$ vertices. A graph $G$ is called a $(\mathcal{P}_{\geq d},m)$-factor deleted graph if $G-E'$ admits a $\mathcal{P}_{\geq d}$-factor for any $E'\subseteq E(G)$ with $|E'|=m$. A graph $G$ is called a $(\mathcal{P}_{\geq d},k)$-factor critical graph if $G-Q$ has a $\mathcal{P}_{\geq d}$-factor for any $Q\subseteq V(G)$ with $|Q|=k$. In this paper, we present two degree conditions for graphs to be $(\mathcal{P}_{\geq3},m)$-factor deleted graphs and $(\mathcal{P}_{\geq3},k)$-factor critical graphs. Furthermore, we show that the two results are best possible in some sense.

    Volume: Volume 191, Issue 1
    Published on: March 30, 2024
    Accepted on: January 14, 2024
    Submitted on: August 31, 2023
    Keywords: Mathematics - Combinatorics,05C70, 05C38

    Consultation statistics

    This page has been seen 202 times.
    This article's PDF has been downloaded 165 times.