A note on the second-largest number of dissociation sets in connected graphs

2025/06/15 by Pingshan Li, Ke Yang, Li, Pingshan +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2506.12740

openalex publication_date 2025/06/15 · openalex created_date 2025/10/13 · openalex updated_date 2026/07/28

Abstract

A subset of vertices is called a dissociation set if it induces a subgraph with vertex degree at most one. Recently, Yuan et al. established the upper bound of the maximum number of dissociation sets among all connected graphs of order n and characterized the corresponding extremal graphs.They also proposed a question regarding the second-largest number of dissociation sets among all connected graphs of order n and the corresponding extremal graphs. In this paper, we give a positive answer to this question.

Citations

• The number of dissociation sets in connected graphs
• The minimum number of maximal dissociation sets in unicyclic graphs
• Upper bound for the number of maximal dissociation sets in trees
• On the maximum number of maximum dissociation sets in trees with given dissociation number
• Maximal and Maximum Dissociation Sets in General and Triangle-Free Graphs
• The maximum number of maximum dissociation sets in trees
• Maximal and Maximum Independent Sets In Graphs With At Most r Cycles
• On cliques in graphs

Related

• The number of dissociation sets in connected graphs
• Maximal and Maximum Dissociation Sets in General and Triangle-Free Graphs
• On the maximum number of maximum dissociation sets in trees with given dissociation number
• The maximum number of maximum dissociation sets in potted graphs
• Upper bound for the number of maximal dissociation sets in trees