{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T19:22:44Z","timestamp":1771528964522,"version":"3.50.1"},"reference-count":26,"publisher":"EDP Sciences","issue":"2","license":[{"start":{"date-parts":[[2023,3,15]],"date-time":"2023-03-15T00:00:00Z","timestamp":1678838400000},"content-version":"vor","delay-in-days":14,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100014718","name":"Innovative Research Group Project of the National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["Grant No. 12271251"],"award-info":[{"award-number":["Grant No. 12271251"]}],"id":[{"id":"10.13039\/100014718","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2023,2,12]]},"published-print":{"date-parts":[[2023,3]]},"abstract":"<jats:p>For a graph <jats:italic>H<\/jats:italic>, a graph <jats:italic>G<\/jats:italic> is <jats:italic>H-saturated<\/jats:italic> if it contains no copy of <jats:italic>H<\/jats:italic> as a (not necessarily induced) subgraph, but the addition of any edge missing from <jats:italic>G<\/jats:italic> creates a copy of <jats:italic>H<\/jats:italic> in the resultant graph. The connected saturation number sat\u2032(<jats:italic>n<\/jats:italic>, <jats:italic>H<\/jats:italic>) is defined as the minimum number of edges in <jats:italic>H<\/jats:italic>-saturated connected graphs on <jats:italic>n<\/jats:italic> vertices. In this paper we consider the (<jats:italic>P<\/jats:italic><jats:sub><jats:italic>k<\/jats:italic><\/jats:sub> \u222a <jats:italic>K<\/jats:italic><jats:sub>3<\/jats:sub>)-saturated connected graphs on <jats:italic>n<\/jats:italic> vertices and focus on the determination of sat\u2032(<jats:italic>n<\/jats:italic>, <jats:italic>P<\/jats:italic><jats:sub><jats:italic>k<\/jats:italic><\/jats:sub> \u222a <jats:italic>K<\/jats:italic><jats:sub>3<\/jats:sub>). We prove that <jats:italic>n<\/jats:italic> + 2 \u2264 sat\u2032(<jats:italic>n<\/jats:italic>, <jats:italic>P<jats:sub>k<\/jats:sub><\/jats:italic> \u222a <jats:italic>K<jats:sub>3<\/jats:sub><\/jats:italic>) \u2264 <jats:italic>n<\/jats:italic> + 3<jats:italic>k<\/jats:italic>-6\/2 for <jats:italic>n<\/jats:italic> &gt; 3<jats:italic>k<\/jats:italic>+4\/2 with <jats:italic>k<\/jats:italic> \u2265 4 and characterize the extremal graphs at which the upper bounds are attained. Moreover, the exact values of sat\u2032(<jats:italic>n<\/jats:italic>, <jats:italic>P<\/jats:italic><jats:sub><jats:italic>k<\/jats:italic><\/jats:sub> \u222a <jats:italic>K<\/jats:italic><jats:sub>3<\/jats:sub>) are determined with <jats:italic>k<\/jats:italic> \u2208 {3, 4} and we get sat(<jats:italic>n<\/jats:italic>, <jats:italic>P<\/jats:italic><jats:sub>2<\/jats:sub> \u222a <jats:italic>K<\/jats:italic><jats:sub>3<\/jats:sub>) = sat\u2032(<jats:italic>n<\/jats:italic>, <jats:italic>P<\/jats:italic><jats:sub>2<\/jats:sub> \u222a <jats:italic>K<\/jats:italic><jats:sub>3<\/jats:sub>) = <jats:italic>n<\/jats:italic>.<\/jats:p>","DOI":"10.1051\/ro\/2023018","type":"journal-article","created":{"date-parts":[[2023,2,14]],"date-time":"2023-02-14T09:03:23Z","timestamp":1676365403000},"page":"447-458","source":"Crossref","is-referenced-by-count":4,"title":["Minimizing the number of edges in (<i>P<\/i><sub><i>k<\/i><\/sub> \u222a <i>K<\/i><sub>3<\/sub>)-saturated connected graphs"],"prefix":"10.1051","volume":"57","author":[{"given":"Yuying","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kexiang","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2023,3,15]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/0012-365X(95)00173-T","volume":"150","author":"Barefoot","year":"1996","journal-title":"Discrete Math."},{"key":"R2","first-page":"149","volume":"1","author":"Bohman","year":"2010","journal-title":"J. Comb."},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Bondy A. and Murty M.R., Graph Theory, Springer-Verlag, London (2008).","DOI":"10.1007\/978-1-84628-970-5"},{"key":"R4","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1111\/j.1749-6632.1989.tb16384.x","volume":"576","author":"Buckley","year":"1989","journal-title":"Ann. N. Y. Acad. Sci."},{"key":"R5","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1002\/jgt.20372","volume":"61","author":"Chen","year":"2009","journal-title":"J. Graph Theory"},{"key":"R6","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1002\/jgt.21767","volume":"76","author":"Chen","year":"2014","journal-title":"J. Graph Theory"},{"key":"R7","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/S0095-8956(03)00044-3","volume":"89","author":"Chen","year":"2003","journal-title":"J. Comb. Theory Ser. B"},{"key":"R8","first-page":"29","volume":"75","author":"Chen","year":"2015","journal-title":"Bull. Inst. Comb. Appl."},{"key":"R9","first-page":"#DS19","volume":"18","author":"Currie","year":"2021","journal-title":"Electron. J. Comb."},{"key":"R10","doi-asserted-by":"crossref","first-page":"1107","DOI":"10.2307\/2311408","volume":"71","author":"Erd\u00f6s","year":"1964","journal-title":"Amer. Math. Monthly"},{"key":"R11","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1006\/jctb.1995.1026","volume":"64","author":"Erd\u00f6s","year":"1995","journal-title":"J. Comb. Theory Ser. B"},{"key":"R12","doi-asserted-by":"crossref","first-page":"2193","DOI":"10.1007\/s00373-014-1514-1","volume":"31","author":"Fan","year":"2015","journal-title":"Graphs Comb."},{"key":"R13","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1007\/s00373-011-1128-9","volume":"29","author":"Faudree","year":"2013","journal-title":"Graphs Comb."},{"key":"R14","doi-asserted-by":"crossref","first-page":"91","DOI":"10.37236\/180","volume":"16","author":"Faudree","year":"2009","journal-title":"Electron. J. Comb."},{"key":"R15","doi-asserted-by":"crossref","first-page":"5870","DOI":"10.1016\/j.disc.2008.06.036","volume":"309","author":"Faudree","year":"2009","journal-title":"Discrete Math."},{"key":"R16","doi-asserted-by":"crossref","first-page":"32","DOI":"10.37236\/1929","volume":"12","author":"Frick","year":"2005","journal-title":"Electron. J. Comb."},{"key":"R17","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1002\/jgt.21668","volume":"73","author":"Furedi","year":"2013","journal-title":"J. Graph Theory"},{"key":"R18","doi-asserted-by":"crossref","first-page":"29","DOI":"10.37236\/1055","volume":"13","author":"Gould","year":"2006","journal-title":"Electron. J. Comb."},{"key":"R19","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/j.dam.2021.07.012","volume":"302","author":"Jiang","year":"2021","journal-title":"Discrete Appl. Math."},{"key":"R20","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1002\/jgt.3190100209","volume":"10","author":"K\u00e1szonyi","year":"1986","journal-title":"J. Graph Theory"},{"key":"R21","unstructured":"Lan Y., Shi Y., Wang Y. and Zhang J., The saturation number of C6. Preprint arXiv:2108.03910v2 (2000)."},{"key":"R22","first-page":"263","volume":"45","author":"Lin","year":"1997","journal-title":"Ars Combin."},{"key":"R23","first-page":"161","volume":"30","author":"Tuza","year":"1989","journal-title":"Acta Univ. Carolin. Math. Phys."},{"key":"R24","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/j.dam.2018.07.014","volume":"254","author":"Wang","year":"2019","journal-title":"Discrete Appl. Math."},{"key":"R25","unstructured":"Yan J., Saturation numbers for linear forests P6 + tP2. Preprint arXiv:2106.06466v2 (2021)."},{"key":"R26","doi-asserted-by":"crossref","first-page":"1085","DOI":"10.1007\/s00373-014-1422-4","volume":"31","author":"Zhang","year":"2015","journal-title":"Graphs Comb."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2023018\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,15]],"date-time":"2023-03-15T09:13:02Z","timestamp":1678871582000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2023018"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3]]},"references-count":26,"journal-issue":{"issue":"2"},"alternative-id":["ro220573"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2023018","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"value":"0399-0559","type":"print"},{"value":"2804-7303","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3]]}}}