Minimizing the number of edges in (Pk ∪ K3)-saturated connected graphs

Open Access

Issue		RAIRO-Oper. Res. Volume 57, Number 2, March-April 2023


Page(s)		447 - 458
DOI		https://doi.org/10.1051/ro/2023018
Published online		15 March 2023

C.A. Barefoot, L.H. Clark, R.C. Entringer, T.D. Porter, L.A. Székely and Z. Tuza, Cycle-saturated graphs of minimum size. Discrete Math. 150 (1996) 31–48. [CrossRef] [MathSciNet] [Google Scholar]
T. Bohman, M. Fonoberova and O. Pikhurko, The saturation function of complete partite graphs. J. Comb. 1 (2010) 149–170. [MathSciNet] [Google Scholar]
A. Bondy and M.R. Murty, Graph Theory, Springer-Verlag, London (2008). [CrossRef] [Google Scholar]
F. Buckley, Self-centered graphs. Ann. N. Y. Acad. Sci. 576 (1989) 71–78. [CrossRef] [Google Scholar]
Y. Chen, Minimum C₅-saturated graphs. J. Graph Theory 61 (2009) 111–126. [CrossRef] [MathSciNet] [Google Scholar]
Y. Chen, Minimum K_2,3-saturated graphs. J. Graph Theory 76 (2014) 309–322. [CrossRef] [MathSciNet] [Google Scholar]
G. Chen, R.J. Gould, F. Pfender and B. Wei, Extremal graphs for intersecting cliques. J. Comb. Theory Ser. B 89 (2003) 159–171. [CrossRef] [Google Scholar]
G. Chen, J.R. Faudree, R.J. Faudree, R.J. Gould, M.S. Jacobson and C. Magnant, Results and problems on saturation numbers for linear forests. Bull. Inst. Comb. Appl. 75 (2015) 29–46. [Google Scholar]
B.L. Currie, J.R. Faudree, R.J. Faudree and J.R. Schmitt, A survey of minimum saturation graphs. Electron. J. Comb. 18 (2021) #DS19. [Google Scholar]
P. Erdös, A. Hajnal and J. Moon, A problem in graph theory. Amer. Math. Monthly 71 (1964) 1107–1110. [CrossRef] [MathSciNet] [Google Scholar]
P. Erdös, Z. Füredi, R.J. Gould and D.S. Gunderson, Extremal graphs for intersecting triangles. J. Comb. Theory Ser. B 64 (1995) 89–100. [CrossRef] [Google Scholar]
Q. Fan and C. Wang, Saturation numbers for linear forests P₅ ∪ tP₂. Graphs Comb. 31 (2015) 2193–2200. [CrossRef] [Google Scholar]
J.R. Faudree and R.J. Gould, Saturation numbers for nearly complete graphs. Graphs Comb. 29 (2013) 429–448. [CrossRef] [Google Scholar]
J. Faudree, R.J. Faudree, R.J. Gould and M.S. Jacobson, Saturation numbers for trees. Electron. J. Comb. 16 (2009) 91–109. [CrossRef] [Google Scholar]
R.J. Faudree, M. Ferrara, R.J. Gould and M.S. Jacobson, tK_p-saturated graphs of minimum size. Discrete Math. 309 (2009) 5870–5876. [CrossRef] [MathSciNet] [Google Scholar]
M. Frick and J. Singleton, Lower bound for the size of maximal nontraceable graphs. Electron. J. Comb. 12 (2005) 32–40. [CrossRef] [Google Scholar]
Z. Furedi and Y. Kim, Cycle-saturated graphs with minimum number of edges. J. Graph Theory 73 (2013) 203–215. [CrossRef] [MathSciNet] [Google Scholar]
R. Gould, T. Luczak and J. Schmitt, Constructive upper bounds for cycle-saturated graphs of minimum size. Electron. J. Comb. 13 (2006) 29–47. [CrossRef] [Google Scholar]
S. Jiang, H. Li and J. Yan, Vertex-disjoint stars in K_1,r-free graphs. Discrete Appl. Math. 302 (2021) 189–197. [CrossRef] [MathSciNet] [Google Scholar]
L. Kászonyi and Z. Tuza, Saturated graphs with minimal number of edges. J. Graph Theory 10 (1986) 203–210. [CrossRef] [MathSciNet] [Google Scholar]
Y. Lan, Y. Shi, Y. Wang and J. Zhang, The saturation number of C₆. Preprint arXiv:2108.03910v2 (2000). [Google Scholar]
X. Lin, W. Jiang, C. Zhang and Y. Yang, On smallest maximally non-Hamiltonian graphs. Ars Combin. 45 (1997) 263–270. [MathSciNet] [Google Scholar]
Z. Tuza, C₄-saturated graphs of minimum size. Acta Univ. Carolin. Math. Phys. 30 (1989) 161–167. [MathSciNet] [Google Scholar]
J. Wang and W. Yang, The Turán number for spanning linear forests. Discrete Appl. Math. 254 (2019) 291–294. [CrossRef] [MathSciNet] [Google Scholar]
J. Yan, Saturation numbers for linear forests P₆ + tP₂. Preprint arXiv:2106.06466v2 (2021). [Google Scholar]
M. Zhang, S. Luo and M. Shigeno, On the number of edges in a minimum C₆-saturated graph. Graphs Comb. 31 (2015) 1085–1106. [CrossRef] [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.