Minimizing the number of edges in ( P k ∪ K 3 )-saturated connected graphs
RAIRO - Operations Research · 2023-03 · 57 (2) · 447-458
DOI: 10.1051/ro/2023018 ↗Kurz gefasst
Fachartikel in der Zeitschrift RAIRO - Operations Research, online erschienen am 15.03.2023. Verfasst von Yuying Li und 1 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 26 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Innovative Research Group Project of the National Natural Science Foundation of China.
Abstract (Originalsprache)
For a graph H , a graph G is H-saturated if it contains no copy of H as a (not necessarily induced) subgraph, but the addition of any edge missing from G creates a copy of H in the resultant graph. The connected saturation number sat′( n , H ) is defined as the minimum number of edges in H -saturated connected graphs on n vertices. In this paper we consider the ( P k ∪ K 3 )-saturated connected graphs on n vertices and focus on the determination of sat′( n , P k ∪ K 3 ). We prove that n + 2 ≤ sat′( n , P k ∪ K 3 ) ≤ n + 3 k -6/2 for n > 3 k +4/2 with k ≥ 4 and characterize the extremal graphs at which the upper bounds are attained. Moreover, the exact values of sat′( n , P k ∪ K 3 ) are determined with k ∈ {3, 4} and we get sat( n , P 2 ∪ K 3 ) = sat′( n , P 2 ∪ K 3 ) = n .
Förderung
- Innovative Research Group Project of the National Natural Science Foundation of China
Zitieren
APA
Li, Y., & Xu, K. (2023). Minimizing the number of edges in ( P k ∪ K 3 )-saturated connected graphs. RAIRO - Operations Research, 57(2), 447-458. https://doi.org/10.1051/ro/2023018
Vancouver
Li Y, Xu K. Minimizing the number of edges in ( P k ∪ K 3 )-saturated connected graphs. RAIRO - Operations Research. 2023;57(2):447-458. doi:10.1051/ro/2023018
BibTeX
@article{Li2023,
author = {Li, Yuying and Xu, Kexiang},
title = {Minimizing the number of edges in ( P k ∪ K 3 )-saturated connected graphs},
journal = {RAIRO - Operations Research},
year = {2023},
volume = {57},
number = {2},
pages = {447--458},
doi = {10.1051/ro/2023018}
}
EUVIMED