Maximal and Maximum Dissociation Sets in General and Triangle-Free Graphs

2021/03/02 by Jianhua Tu, Yuxin Li, Tu, Jianhua +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2103.01402

openalex publication_date 2021/03/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A subset of vertices F in a graph G is called a dissociation set if the induced subgraph G[F] of G has maximum degree at most 1. A maximal dissociation set of G is a dissociation set which is not a proper subset of any other dissociation sets. A maximum dissociation set is a dissociation set of maximum size. We show that every graph of order n has at most 10^(n)/(5) maximal dissociation sets, and that every triangle-free graph of order n has at most 6^(n)/(4) maximal dissociation sets. We also characterize the extremal graphs on which these upper bounds are attained. The tight upper bounds on the number of maximum dissociation sets in general and triangle-free graphs are also obtained.

Cited by

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

Related

• A note on the second-largest number of dissociation sets in connected graphs
• Upper bound for the number of maximal dissociation sets in trees
• The minimum number of maximal dissociation sets in unicyclic graphs
• The maximum number of maximum dissociation sets in potted graphs
• On the maximum number of maximum dissociation sets in trees with given dissociation number