EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Minimizing the number of edges in ( P k ∪ K 3 )-saturated connected graphs

Yuying Li, Kexiang Xu

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →