Some results about component factors in graphs

Zhou, Sizhong

RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 3, pp. 723-730.

Suite au passage du modèle économique de la revue en S20, le texte intégral des articles des années 2019 et 2020 est accessible uniquement sur le site de l'éditeur et est réservé aux abonnés.

For a set $\mathscr{H}$ of connected graphs, a spanning subgraph $H$ of a graph $G$ is called an $\mathscr{H}$-factor of $G$ if every component of $H$ is isomorphic to a member of $\mathscr{H}$. An $\mathscr{H}$-factor is also referred as a component factor. If each component of $H$ is a star (resp. path), $H$ is called a star (resp. path) factor. By a $P_{\ge k}$-factor ($k$ positive integer) we mean a path factor in which each component path has at least $k$ vertices (i.e. it has length at least $k-1$). A graph $G$ is called a $P_{\ge k}$-efactor covered graph, if for each edge $e$ of $G$, there is a $P_{\ge k}$-factor covering $e$. In this paper, we prove that (i) a graph $G$ has a $K_{1,1},K_{1,2},...,K_{1,k}$-factor if and only if bind $\left(G\right)\ge \frac{1}{k}$, … ,K-factor if and only if bind $(G) geq \frac{1}{k}$, where $k \geq 2$ is an integer; (ii) a connected graph $G$ is a _{, where $k \geq 2$ is an integer; (ii) a connected graph $G$ is a $P_{\geq3}$}-factor covered graph if bind $\left(G\right)>\frac{2}{3}$; (iii) a connected graph $G$ is a _{$P_{\geq 3}$}-factor covered graph if bind $\left(G\right)\ge \frac{3}{2}$. Furthermore, it is shown that the results in this paper are best possible in some sense.

I. Anderson, Binding numbers of graphs: a survey. In Advances in graph theory, Vishwa, Gulbarga (1991) 1–10. | MR

J. Akiyama, D. Avis and H. Era, On a {1,2}-factor of a graph. TRU Math. 16 (1980) 97–102. | MR | Zbl

A. Amahashi and M. Kano, On factors with given components. Discrete Math. 42 (1982) 1–6. | DOI | MR | Zbl

J. Akiyama and M. Kano, Factors and factorizations of graphs – a survey. J. Graph Theory 9 (1985) 1–42. | DOI | MR | Zbl

C. Bazgan, A.H. Benhamdine, H. Li and M. Wozniak, Partitioning vertices of 1-tough graph into paths. Theoretical Comput. Sci. 263 (2001) 255–261. | DOI | MR | Zbl

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. | DOI | MR | Zbl

M. Kano, H. Lu and Q. Yu, Component factors with large components in graphs. Appl. Math. Lett. 23 (2010) 385–389. | DOI | MR | Zbl

M. Kano and A. Saito, Star-factors with large component. Discrete Math. 312 (2012) 2005–2008. | DOI | MR | Zbl

M. Kano and N. Tokushige, Binding numbers and f-factors of graphs. J. Combin. Theory Ser. B 54 (1992) 213–221. | DOI | MR | Zbl

P. Katerinis and D.R. Woodall, Binding numbers of graphs and the existence of k-factors. Quart. J. Math. Oxford 38 (1987) 221–228. | DOI | MR | Zbl

X. Li and Z. Zhang, Path factors in the square of a tree. Graphs Combin. 24 (2008) 107–111. | DOI | MR | Zbl

M. Plummer, Graph factors and factorization: 1985–2003: a survey. Discrete Math. 307 (2007) 791–821. | DOI | MR | Zbl

D. Woodall, The binding number of a graph and its Anderson number. J. Combin. Theory Ser. B 15 (1973) 225–255. | DOI | MR | Zbl

J. Yu and G. Liu, Binding number and minimum degree conditions for graphs to have fractional factors. J. Shandong University 39 (2004) 1–5.

Q. Yu and G. Liu, Graph factors and matching extensions. Higher Education Press, Beijing, Springer-Verlag, Berlin (2009). | DOI | MR | Zbl

S. Zhou, Binding numbers for fractional ID-k-factor-critical graphs. Acta Mathematica Sinica, English Series 30 (2014) 181–186. | DOI | MR | Zbl

S. Zhou, Binding numbers and [a, b]-factors excluding a given k-factor. C. R. Math. 349 (2011) 1021–1024. | DOI | MR | Zbl

S. Zhou, Remarks on orthogonal factorizations of digraphs. Int. J. Comput. Math. 91 (2014) 2109–2117. | DOI | MR | Zbl

S. Zhou, Some new sufficient conditions for graphs to have fractional k-factors. Int. J. Comput. Math. 88 (2011) 484–490. | DOI | MR | Zbl

S. Zhou, Q. Bian and Z. Sun, Binding numbers for all fractional (a, b, k)-critical graphs. Filomat 28 (2014) 709–713. | DOI | MR | Zbl

H. Zhang and S. Zhou, Characterizations for P_≥ 2-factor and P_≥ 3-factor covered graphs. Discrete Math. 309 (2009) 2067–2076. | DOI | MR | Zbl