On the saturation number of graphs

2017/12/09 by ‎Saeid Alikhani, Alikhani, Saeid, Neda Soltani +1 · 1 citation
Computer Science · Mathematics · #05C30 #05C70 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.1712.03422

openalex publication_date 2017/12/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let G=(V,E) be a simple connected graph. A matching M in a graph G is a collection of edges of G such that no two edges from M share a vertex. A matching M is maximal if it cannot be extended to a larger matching in G. The cardinality of any smallest maximal matching in G is the saturation number of G and is denoted by s(G). In this paper we study the saturation number of the corona product of two specific graphs. We also consider some graphs with certain constructions that are of importance in chemistry and study their saturation number.

Citations

• Sandwiching saturation number of fullerene graphs

Cited by

• In Reverie Together: Ten Years of Mathematical Discovery with a Machine Collaborator

Related

• A lower bound on the saturation number, and graphs for which it is sharp
• Minimizing the number of matchings of fixed size in a K_s-saturated graph
• Characterization of saturated graphs related to pairs of disjoint matchings
• The saturation number of C₆
• The saturation number for unions of four cliques