Geodesic
Saturation numbers for linear forests $P_6 + tP_2$
Czechoslovak Mathematical Journal, Tome 73 (2023) no. 4, pp. 1007-1016
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

A graph $G$ is $H$-saturated if it contains no $H$ as a subgraph, but does contain $H$ after the addition of any edge in the complement of $G$. The saturation number, ${\rm sat} (n, H)$, is the minimum number of edges of a graph in the set of all $H$-saturated graphs of order $n$. We determine the saturation number ${\rm sat} (n, P_6 + tP_2)$ for $n \geq \frac {10}{3} t + 10$ and characterize the extremal graphs for $n > \frac {10}{3} t + 20$.
A graph $G$ is $H$-saturated if it contains no $H$ as a subgraph, but does contain $H$ after the addition of any edge in the complement of $G$. The saturation number, ${\rm sat} (n, H)$, is the minimum number of edges of a graph in the set of all $H$-saturated graphs of order $n$. We determine the saturation number ${\rm sat} (n, P_6 + tP_2)$ for $n \geq \frac {10}{3} t + 10$ and characterize the extremal graphs for $n > \frac {10}{3} t + 20$.
DOI : 10.21136/CMJ.2023.0001-22
Classification : 05C35, 05C38
Keywords: saturation number; saturated graph; linear forest 
@article{10_21136_CMJ_2023_0001_22,
     author = {Yan, Jingru},
     title = {Saturation numbers for linear forests $P_6 + tP_2$},
     journal = {Czechoslovak Mathematical Journal},
     pages = {1007--1016},
     year = {2023},
     volume = {73},
     number = {4},
     doi = {10.21136/CMJ.2023.0001-22},
     zbl = {07790559},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2023.0001-22/}
}
TY  - JOUR
AU  - Yan, Jingru
TI  - Saturation numbers for linear forests $P_6 + tP_2$
JO  - Czechoslovak Mathematical Journal
PY  - 2023
SP  - 1007
EP  - 1016
VL  - 73
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2023.0001-22/
DO  - 10.21136/CMJ.2023.0001-22
LA  - en
ID  - 10_21136_CMJ_2023_0001_22
ER  - 
%0 Journal Article
%A Yan, Jingru
%T Saturation numbers for linear forests $P_6 + tP_2$
%J Czechoslovak Mathematical Journal
%D 2023
%P 1007-1016
%V 73
%N 4
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2023.0001-22/
%R 10.21136/CMJ.2023.0001-22
%G en
%F 10_21136_CMJ_2023_0001_22
Yan, Jingru. Saturation numbers for linear forests $P_6 + tP_2$. Czechoslovak Mathematical Journal, Tome 73 (2023) no. 4, pp. 1007-1016. doi: 10.21136/CMJ.2023.0001-22

[1] Berge, C.: Sur le couplage maximum d'un graphe. C. R. Acad. Sci., Paris 247 (1958), 258-259 French. | MR | JFM

[2] Bohman, T., Fonoberova, M., Pikhurko, O.: The saturation function of complete partite graphs. J. Comb. 1 (2010), 149-170. | DOI | MR | JFM

[3] Bollobás, B.: On a conjecture of Erdős, Hajnal and Moon. Am. Math. Mon. 74 (1967), 178-179. | DOI | MR | JFM

[4] Bondy, J. A., Murty, U. S. R.: Graph Theory. Graduate Texts in Mathematics 244. Springer, Berlin (2008). | DOI | MR | JFM

[5] Chen, G., Faudree, J. R., Faudree, R. J., Gould, R. J., Jacobson, M. S., Magnant, C.: Results and problems on saturation numbers for linear forests. Bull. Inst. Comb. Appl. 75 (2015), 29-46. | MR | JFM

[6] Chen, G., Faudree, R. J., Gould, R. J.: Saturation numbers of books. Electron. J. Comb. 15 (2008), Article ID 118, 12 pages. | DOI | MR | JFM

[7] Chen, Y.-C.: All minimum $C_5$-saturated graphs. J. Graph Theory 67 (2011), 9-26. | DOI | MR | JFM

[8] Chen, Y.-C.: Minimum $K_{2,3}$-saturated graphs. J. Graph Theory 76 (2014), 309-322. | DOI | MR | JFM

[9] Erdős, P., Hajnal, A., Moon, J. W.: A problem in graph theory. Am. Math. Mon. 71 (1964), 1107-1110. | DOI | MR | JFM

[10] Fan, Q., Wang, C.: Saturation numbers for linear forests $P_5\cup tP_2$. Graphs Comb. 31 (2015), 2193-2200. | DOI | MR | JFM

[11] Faudree, J. R., Faudree, R. J., Gould, R. J., Jacobson, M. S.: Saturation numbers for trees. Electron. J. Comb. 16 (2009), Article ID R91, 19 pages. | DOI | MR | JFM

[12] Faudree, J. R., Faudree, R. J., Schmitt, J. R.: A survey of minimum saturated graphs. Electron. J. Comb. DS19 (2011), 36 pages. | MR | JFM

[13] Faudree, J. R., Ferrara, M., Gould, R. J., Jacobson, M. S.: $tK_p$-saturated graphs of minimum size. Discrete Math. 309 (2009), 5870-5876. | DOI | MR | JFM

[14] Kászonyi, L., Tuza, Z.: Saturated graphs with minimal number of edges. J. Graph Theory 10 (1986), 203-210. | DOI | MR | JFM

[15] Sullivan, E., Wenger, P. S.: Saturation numbers in tripartite graphs. J. Graph Theory 84 (2017), 428-442. | DOI | MR | JFM

[16] Turán, P.: Eine Extremalaufgabe aus der Graphentheorie. Mat. Fiz. Lapok 48 (1941), 436-452 Hungarian. | MR | JFM

[17] Tuza, Z.: $C_4$-saturated graphs of minimum size. Acta Univ. Carol., Math. Phys. 30 (1989), 161-167. | MR | JFM

[18] West, D. B.: Introduction to Graph Theory. Prentice Hall, Upper Saddle River (1996). | MR | JFM

Cité par Sources :