no. 2
Remarks on component factors in graphs
RAIRO. Operations Research, Tome 56 (2022) no. 2, pp. 721-730

For a family of connected graphs ℱ, a spanning subgraph H of a graph G is called an ℱ-factor of G if its each component is isomorphic to an element of ℱ. In particular, H is called an 𝒮 k -factor of G if ℱ = {K1,1, K1,2,…,K$$}, where integer k ≥ 2; H is called a P≥3-factor of G if every component in ℱ is a path of order at least three. As an extension of 𝒮 k -factors, the induced star-factor (i.e., ℐ𝒮 k -factor) is a spanning subgraph each component of which is an induced subgraph isomorphic to some graph in ℱ = {K1,1, K1,2,…,K$$}. In this paper, we firstly prove that a graph G has an 𝒮 k -factor if and only if its isolated toughness I(G)≥1 k. Secondly, we prove that a planar graphs G has an 𝒮 2 -factors if its minimum degree δ(G) ≥ 3. Thirdly, we give two sufficient conditions for graphs with ℐ𝒮 k -factors by toughness and minimum degree, respectively. Additionally, we obtain three special classes of graphs admitting P≥3-factors.

Reçu le :
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2022033
Classification : 05C70, 05C38
Keywords: Star-factor, Induced star-factor, $$≥3-factor, Toughness, Minimum degree 
@article{RO_2022__56_2_721_0,
     author = {Dai, Guowei},
     title = {Remarks on component factors in graphs},
     journal = {RAIRO. Operations Research},
     pages = {721--730},
     year = {2022},
     publisher = {EDP-Sciences},
     volume = {56},
     number = {2},
     doi = {10.1051/ro/2022033},
     mrnumber = {4407591},
     zbl = {1487.05205},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2022033/}
}
TY  - JOUR
AU  - Dai, Guowei
TI  - Remarks on component factors in graphs
JO  - RAIRO. Operations Research
PY  - 2022
SP  - 721
EP  - 730
VL  - 56
IS  - 2
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2022033/
DO  - 10.1051/ro/2022033
LA  - en
ID  - RO_2022__56_2_721_0
ER  - 
%0 Journal Article
%A Dai, Guowei
%T Remarks on component factors in graphs
%J RAIRO. Operations Research
%D 2022
%P 721-730
%V 56
%N 2
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2022033/
%R 10.1051/ro/2022033
%G en
%F RO_2022__56_2_721_0
Dai, Guowei. Remarks on component factors in graphs. RAIRO. Operations Research, Tome 56 (2022) no. 2, pp. 721-730. doi: 10.1051/ro/2022033

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

[2] A. Amahashi and M. Kano, Factors with given components. Discrete Math. 42 (1982) 1–6. | MR | Zbl | DOI

[3] J. A. Bondy and U. S. R. Murty, Graph theory with applications. North-Holland, New York-Amsterdam-Oxford (1982). | Zbl

[4] V. Chvátal, Tough graphs and Hamiltonian Circuits. Discrete Math. 5 (1973) 215–228. | MR | Zbl | DOI

[5] G. Dai, The existence of path-factor covered graphs. . To appear in: Discuss. Math. Graph Theory (2020). | MR | Zbl

[6] Y. Egawa, M. Kano and A. K. Kelmans, Star partitions of graphs. J. Graph Theory 25 (1997) 185–190. | MR | Zbl | DOI

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

[8] M. Kano, G. Y. Katona and Z. Király, Packing paths of length at least two. Discrete Math. 283 (2004) 129–135. | MR | Zbl | DOI

[9] M. D. Plummer, Perspectives: Graph factors and factorization: 1985–2003: A survey. Discrete Math. 307 (2007) 791–821. | MR | Zbl | DOI

[10] W. T. Tutte, The factors of graphs. Canad. J. Math. 4 (1952) 314–328. | MR | Zbl | DOI

[11] M. Las Vergnas, An extension of Tutte’s 1-factor theorem. Discrete Math. 23 (1978) 241–255. | MR | Zbl | DOI

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

[13] Q. Yu and G. Liu, Graph Factors and Matching Extensions. Higher Education Press, Beijing (2009). | MR | Zbl | DOI

[14] S. Zhou, Some results about component factors in graphs. RAIRO-Oper. Res. 53 (2019) 723–730. | MR | Zbl | Numdam | DOI

[15] S. Zhou, Q. Bian andZ. Sun, Two sufficient conditions for component factors in graphs. To appear in: Discuss. Math. Graph Theory (2021). | MR

Cité par Sources :