MINIMIZING THE NUMBER OF EDGES IN (Pk∪Sℓ)-SATURATED GRAPHS
Rocky Mountain Journal of Mathematics · 30.10.2026 · 56 (5) · 1383-1396
DOI: 10.1216/rmj.2026.56.1383 ↗Kurz gefasst
Fachartikel in der Zeitschrift Rocky Mountain Journal of Mathematics, erschienen am 30.10.2026. Verfasst von Yuying Li und 1 weiteren Autor:innen. Die Arbeit nennt 21 Literaturangaben.
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 saturation number sat(n,H) is defined as the minimum number of edges in H-saturated graphs on n vertices. Let Pk and Sk be path and star on k vertices, respectively. We consider the (Pk∪Sℓ)-saturated graphs on n vertices and focus on the determination of sat(n,Pk∪Sℓ). We prove the upper bounds of sat(n,Pk∪Sℓ) for k≥6 and ℓ≥4. Moreover, we get sat(n,Pk∪Sℓ)=n−⌊n−3(ℓ−4)ak⌋ on certain conditions and sat(n,Pk∪S4)=n−⌊nak⌋ for k≥6, where ak is the order of the minimum Pk-saturated tree. We also give a conjecture about the exact value of sat(n,Pk∪Sℓ) if ℓ is not less than some positive integer.
Zitieren
APA
Li, Y., & Xu, K. (2026). MINIMIZING THE NUMBER OF EDGES IN (Pk∪Sℓ)-SATURATED GRAPHS. Rocky Mountain Journal of Mathematics, 56(5), 1383-1396. https://doi.org/10.1216/rmj.2026.56.1383
Vancouver
Li Y, Xu K. MINIMIZING THE NUMBER OF EDGES IN (Pk∪Sℓ)-SATURATED GRAPHS. Rocky Mountain Journal of Mathematics. 2026;56(5):1383-1396. doi:10.1216/rmj.2026.56.1383
BibTeX
@article{Li2026,
author = {Li, Yuying and Xu, Kexiang},
title = {MINIMIZING THE NUMBER OF EDGES IN (Pk∪Sℓ)-SATURATED GRAPHS},
journal = {Rocky Mountain Journal of Mathematics},
year = {2026},
volume = {56},
number = {5},
pages = {1383--1396},
doi = {10.1216/rmj.2026.56.1383}
}
EUVIMED