Saturation Numbers for Linear Forests P₆ + tP₂

2021/06/11 by Yan, Jingru · 1 citation
#05C35 #05C38 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2106.06466

Abstract

A graph G is H-saturated if it contains no H as a subgraph, but does contain H after the addition of any edge in the complement of G. The saturation number, sat (n, H), is the minimum number of edges of a graph in the set of all H-saturated graphs with order n. In this paper, we determine the saturation number sat (n, P₆ + tP₂) for n ≥ 10t/3 + 10 and characterize the extremal graphs for n >10t/3 + 20.

Cited by

• Some results on minimum saturated graphs

Related

• Saturation Numbers for Linear Forests P₇+tP₂
• Some results on minimum saturated graphs
• A lower bound on the saturation number, and graphs for which it is sharp
• Saturation numbers of K₂\vee P_k
• The saturation number of W 4