Relating the independence number and the dissociation number

2022/05/06 by Felix Bock, Johannes Pardey, Bock, Felix +5 · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.2205.03404

openalex publication_date 2022/05/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The independence number α(G) and the dissociation number \rm diss(G) of a graph G are the largest orders of induced subgraphs of G of maximum degree at most 0 and at most 1, respectively. We consider possible improvements of the obvious inequality 2α(G)≥ \rm diss(G). For connected cubic graphs G distinct from K₄, we show 5α(G)≥ 3\rm diss(G), and describe the rich and interesting structure of the extremal graphs in detail. For bipartite graphs, and, more generally, triangle-free graphs, we also obtain improvements. For subcubic graphs though, the inequality cannot be improved in general, and we characterize all extremal subcubic graphs.

Cited by

• Laplacian Bounds for the Dissociation Number of Regular Graphs of Matrix Rings
• Sharp lower bounds and extremal graphs for the generalized k-independence number
• A sharp lower bound on the generalized 4-independence number

Related

• A bound on the dissociation number
• Relating dissociation, independence, and matchings
• Cubic graphs with equal independence number and matching number
• Maximal and Maximum Dissociation Sets in General and Triangle-Free Graphs
• Sharp upper bounds on the k-independence number in graphs with given minimum and maximum degree