| Title:
|
Saturation numbers for linear forests $P_6 + tP_2$ (English) |
| Author:
|
Yan, Jingru |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
73 |
| Issue:
|
4 |
| Year:
|
2023 |
| Pages:
|
1007-1016 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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$. (English) |
| Keyword:
|
saturation number |
| Keyword:
|
saturated graph |
| Keyword:
|
linear forest |
| MSC:
|
05C35 |
| MSC:
|
05C38 |
| idZBL:
|
Zbl 07790559 |
| DOI:
|
10.21136/CMJ.2023.0001-22 |
| . |
| Date available:
|
2023-11-23T12:19:48Z |
| Last updated:
|
2026-01-05 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/151945 |
| . |
| Reference:
|
[1] Berge, C.: Sur le couplage maximum d'un graphe.C. R. Acad. Sci., Paris 247 (1958), 258-259 French. Zbl 0086.16301, MR 0100850 |
| Reference:
|
[2] Bohman, T., Fonoberova, M., Pikhurko, O.: The saturation function of complete partite graphs.J. Comb. 1 (2010), 149-170. Zbl 1221.05208, MR 2732512, 10.4310/JOC.2010.v1.n2.a5 |
| Reference:
|
[3] Bollobás, B.: On a conjecture of Erdős, Hajnal and Moon.Am. Math. Mon. 74 (1967), 178-179. Zbl 0144.45304, MR 0205871, 10.2307/2315614 |
| Reference:
|
[4] Bondy, J. A., Murty, U. S. R.: Graph Theory.Graduate Texts in Mathematics 244. Springer, Berlin (2008). Zbl 1134.05001, MR 2368647, 10.1007/978-1-84628-970-5 |
| Reference:
|
[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. Zbl 1401.05155, MR 3444611 |
| Reference:
|
[6] Chen, G., Faudree, R. J., Gould, R. J.: Saturation numbers of books.Electron. J. Comb. 15 (2008), Article ID 118, 12 pages. Zbl 1158.05033, MR 2443133, 10.37236/842 |
| Reference:
|
[7] Chen, Y.-C.: All minimum $C_5$-saturated graphs.J. Graph Theory 67 (2011), 9-26. Zbl 1223.05130, MR 2809558, 10.1002/jgt.20508 |
| Reference:
|
[8] Chen, Y.-C.: Minimum $K_{2,3}$-saturated graphs.J. Graph Theory 76 (2014), 309-322. Zbl 1296.05097, MR 3218275, 10.1002/jgt.21767 |
| Reference:
|
[9] Erdős, P., Hajnal, A., Moon, J. W.: A problem in graph theory.Am. Math. Mon. 71 (1964), 1107-1110. Zbl 0126.39401, MR 0170339, 10.2307/2311408 |
| Reference:
|
[10] Fan, Q., Wang, C.: Saturation numbers for linear forests $P_5\cup tP_2$.Graphs Comb. 31 (2015), 2193-2200. Zbl 1328.05099, MR 3417226, 10.1007/s00373-014-1514-1 |
| Reference:
|
[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. Zbl 1186.05072, MR 2529800, 10.37236/180 |
| Reference:
|
[12] Faudree, J. R., Faudree, R. J., Schmitt, J. R.: A survey of minimum saturated graphs.Electron. J. Comb. DS19 (2011), 36 pages. Zbl 1222.05113, MR 4336221 |
| Reference:
|
[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. Zbl 1229.05141, MR 2551965, 10.1016/j.disc.2008.06.036 |
| Reference:
|
[14] Kászonyi, L., Tuza, Z.: Saturated graphs with minimal number of edges.J. Graph Theory 10 (1986), 203-210. Zbl 0593.05041, MR 0890226, 10.1002/jgt.3190100209 |
| Reference:
|
[15] Sullivan, E., Wenger, P. S.: Saturation numbers in tripartite graphs.J. Graph Theory 84 (2017), 428-442. Zbl 1359.05055, MR 3623386, 10.1002/jgt.22033 |
| Reference:
|
[16] Turán, P.: Eine Extremalaufgabe aus der Graphentheorie.Mat. Fiz. Lapok 48 (1941), 436-452 Hungarian. Zbl 0026.26903, MR 0018405 |
| Reference:
|
[17] Tuza, Z.: $C_4$-saturated graphs of minimum size.Acta Univ. Carol., Math. Phys. 30 (1989), 161-167. Zbl 0719.05040, MR 1046463 |
| Reference:
|
[18] West, D. B.: Introduction to Graph Theory.Prentice Hall, Upper Saddle River (1996). Zbl 0845.05001, MR 1367739 |
| . |
