On the number of Fk,4-saturating edges

Yuying Li and Kexiang Xu

Applied Mathematics and Computation, 2025, vol. 489, issue C

Abstract: For a graph F, let G be an F-free graph, a non-edge e of G is an F-saturating edge if G+e contains a copy of F. Graph Fk,r consists of k cliques Kr intersecting in exactly one common vertex. Denote by fF(n,m) the minimum number of F-saturating edges of F-free graphs on n vertices with m edges and fF⁎(n,m), where m≤ex(n,F), the minimum number of F-saturating edges of F-free graphs on n vertices with m edges obtained by deleting edges from the extremal graph attaining ex(n,F). In this paper, we study the number of Fk,4-saturating edges in Fk,4-free graphs on n vertices with ex(n,Fk−1,4)+1 edges. We give the upper bounds on fFk,4(n,ex(n,Fk−1,4)+1) and get the value of fF2,4(n,ex(n,F1,4)+1). Moreover, we characterize the extremal graphs attaining ex(n,Fk,4) with odd k≥3 and prove fFk,4⁎(n,ex(n,Fk−1,4)+1)=⌊n3⌋−k for odd k≥3.

Keywords: Graph saturation; Saturating edges; Extremal graph (search for similar items in EconPapers)
Date: 2025
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300324006234
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:489:y:2025:i:c:s0096300324006234

DOI: 10.1016/j.amc.2024.129162

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().