Saturation numbers for linear forests P 6 + t P 2

Jingru Yan

Czechoslovak Mathematical Journal (2023)

  • Volume: 73, Issue: 4, page 1007-1016
  • ISSN: 0011-4642

Abstract

top
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, 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 sat ( n , P 6 + t P 2 ) for n ≥ 10 3 t + 10 and characterize the extremal graphs for n > 10 3 t + 20 .

How to cite

top

Yan, 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
  1. Berge, C., Sur le couplage maximum d'un graphe, C. R. Acad. Sci., Paris 247 (1958), 258-259 French. (1958) Zbl0086.16301MR0100850
  2. 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
  3. Bollobás, B., 10.2307/2315614, Am. Math. Mon. 74 (1967), 178-179. (1967) Zbl0144.45304MR0205871DOI10.2307/2315614
  4. 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
  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
  6. 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
  7. Chen, Y.-C., 10.1002/jgt.20508, J. Graph Theory 67 (2011), 9-26. (2011) Zbl1223.05130MR2809558DOI10.1002/jgt.20508
  8. Chen, Y.-C., 10.1002/jgt.21767, J. Graph Theory 76 (2014), 309-322. (2014) Zbl1296.05097MR3218275DOI10.1002/jgt.21767
  9. Erdős, P., Hajnal, A., Moon, J. W., 10.2307/2311408, Am. Math. Mon. 71 (1964), 1107-1110. (1964) Zbl0126.39401MR0170339DOI10.2307/2311408
  10. Fan, Q., Wang, C., 10.1007/s00373-014-1514-1, Graphs Comb. 31 (2015), 2193-2200. (2015) Zbl1328.05099MR3417226DOI10.1007/s00373-014-1514-1
  11. 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
  12. 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
  13. 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
  14. Kászonyi, L., Tuza, Z., 10.1002/jgt.3190100209, J. Graph Theory 10 (1986), 203-210. (1986) Zbl0593.05041MR0890226DOI10.1002/jgt.3190100209
  15. Sullivan, E., Wenger, P. S., 10.1002/jgt.22033, J. Graph Theory 84 (2017), 428-442. (2017) Zbl1359.05055MR3623386DOI10.1002/jgt.22033
  16. Turán, P., Eine Extremalaufgabe aus der Graphentheorie, Mat. Fiz. Lapok 48 (1941), 436-452 Hungarian. (1941) Zbl0026.26903MR0018405
  17. Tuza, Z., C 4 -saturated graphs of minimum size, Acta Univ. Carol., Math. Phys. 30 (1989), 161-167. (1989) Zbl0719.05040MR1046463
  18. West, D. B., Introduction to Graph Theory, Prentice Hall, Upper Saddle River (1996). (1996) Zbl0845.05001MR1367739

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.