Saturation numbers for linear forests
Czechoslovak Mathematical Journal (2023)
- Volume: 73, Issue: 4, page 1007-1016
- ISSN: 0011-4642
Access Full Article
topAbstract
topHow to cite
topYan, Jingru. "Saturation numbers for linear forests $P_6 + tP_2$." Czechoslovak Mathematical Journal 73.4 (2023): 1007-1016. <http://eudml.org/doc/299469>.
@article{Yan2023,
abstract = {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 \ge \frac\{10\}\{3\} t + 10$ and characterize the extremal graphs for $n > \frac\{10\}\{3\} t + 20$.},
author = {Yan, Jingru},
journal = {Czechoslovak Mathematical Journal},
keywords = {saturation number; saturated graph; linear forest},
language = {eng},
number = {4},
pages = {1007-1016},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Saturation numbers for linear forests $P_6 + tP_2$},
url = {http://eudml.org/doc/299469},
volume = {73},
year = {2023},
}
TY - JOUR
AU - Yan, Jingru
TI - Saturation numbers for linear forests $P_6 + tP_2$
JO - Czechoslovak Mathematical Journal
PY - 2023
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 73
IS - 4
SP - 1007
EP - 1016
AB - 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 \ge \frac{10}{3} t + 10$ and characterize the extremal graphs for $n > \frac{10}{3} t + 20$.
LA - eng
KW - saturation number; saturated graph; linear forest
UR - http://eudml.org/doc/299469
ER -
References
top- Berge, C., Sur le couplage maximum d'un graphe, C. R. Acad. Sci., Paris 247 (1958), 258-259 French. (1958) Zbl0086.16301MR0100850
- Bohman, T., Fonoberova, M., Pikhurko, O., 10.4310/JOC.2010.v1.n2.a5, J. Comb. 1 (2010), 149-170. (2010) Zbl1221.05208MR2732512DOI10.4310/JOC.2010.v1.n2.a5
- Bollobás, B., 10.2307/2315614, Am. Math. Mon. 74 (1967), 178-179. (1967) Zbl0144.45304MR0205871DOI10.2307/2315614
- Bondy, J. A., Murty, U. S. R., 10.1007/978-1-84628-970-5, Graduate Texts in Mathematics 244. Springer, Berlin (2008). (2008) Zbl1134.05001MR2368647DOI10.1007/978-1-84628-970-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. (2015) Zbl1401.05155MR3444611
- Chen, G., Faudree, R. J., Gould, R. J., 10.37236/842, Electron. J. Comb. 15 (2008), Article ID 118, 12 pages. (2008) Zbl1158.05033MR2443133DOI10.37236/842
- Chen, Y.-C., 10.1002/jgt.20508, J. Graph Theory 67 (2011), 9-26. (2011) Zbl1223.05130MR2809558DOI10.1002/jgt.20508
- Chen, Y.-C., 10.1002/jgt.21767, J. Graph Theory 76 (2014), 309-322. (2014) Zbl1296.05097MR3218275DOI10.1002/jgt.21767
- Erdős, P., Hajnal, A., Moon, J. W., 10.2307/2311408, Am. Math. Mon. 71 (1964), 1107-1110. (1964) Zbl0126.39401MR0170339DOI10.2307/2311408
- Fan, Q., Wang, C., 10.1007/s00373-014-1514-1, Graphs Comb. 31 (2015), 2193-2200. (2015) Zbl1328.05099MR3417226DOI10.1007/s00373-014-1514-1
- Faudree, J. R., Faudree, R. J., Gould, R. J., Jacobson, M. S., 10.37236/180, Electron. J. Comb. 16 (2009), Article ID R91, 19 pages. (2009) Zbl1186.05072MR2529800DOI10.37236/180
- Faudree, J. R., Faudree, R. J., Schmitt, J. R., A survey of minimum saturated graphs, Electron. J. Comb. DS19 (2011), 36 pages. (2011) Zbl1222.05113MR4336221
- Faudree, J. R., Ferrara, M., Gould, R. J., Jacobson, M. S., 10.1016/j.disc.2008.06.036, Discrete Math. 309 (2009), 5870-5876. (2009) Zbl1229.05141MR2551965DOI10.1016/j.disc.2008.06.036
- Kászonyi, L., Tuza, Z., 10.1002/jgt.3190100209, J. Graph Theory 10 (1986), 203-210. (1986) Zbl0593.05041MR0890226DOI10.1002/jgt.3190100209
- Sullivan, E., Wenger, P. S., 10.1002/jgt.22033, J. Graph Theory 84 (2017), 428-442. (2017) Zbl1359.05055MR3623386DOI10.1002/jgt.22033
- Turán, P., Eine Extremalaufgabe aus der Graphentheorie, Mat. Fiz. Lapok 48 (1941), 436-452 Hungarian. (1941) Zbl0026.26903MR0018405
- Tuza, Z., -saturated graphs of minimum size, Acta Univ. Carol., Math. Phys. 30 (1989), 161-167. (1989) Zbl0719.05040MR1046463
- West, D. B., Introduction to Graph Theory, Prentice Hall, Upper Saddle River (1996). (1996) Zbl0845.05001MR1367739
NotesEmbed ?
topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.