Relating the independence number and the dissociation number

DOI10.1002/JGT.22965zbMATH Open1522.05352arXiv2205.03404MaRDI QIDQ6094030FDOQ6094030

Authors: Felix Bock, Johannes Pardey, Lucia Draque Penso, Dieter Rautenbach 

Publication date: 9 October 2023

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: The independence number $alpha(G)$ and the dissociation number $mdiss(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 $2alpha(G)geqmdiss(G)$. For connected cubic graphs $G$ distinct from $K_4$, we show $5alpha(G)geq3mdiss(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.

Full work available at URL: https://arxiv.org/abs/2205.03404

Recommendations

• A bound on the dissociation number
• Independent sets and matchings in subcubic graphs
• Relating dissociation, independence, and matchings
• Maximal and maximum dissociation sets in general and triangle-free graphs
• scientific article; zbMATH DE number 2192124

zbMATH Keywords

cubic graphindependent settriangle-free graphdissociation set

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Minimum \(k\)-path vertex cover
• On the vertex \(k\)-path cover
• Title not available (Why is that?)
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• On \({\mathcal F}\)-independence in graphs
• Node-Deletion Problems on Bipartite Graphs
• Title not available (Why is that?)
• Independent sets in triangle-free cubic planar graphs
• 11/30 (Finding large independent sets in connected triangle-free 3- regular graphs)
• Some Ramsey-Type Numbers and the Independence Ratio
• A new proof of the independence ratio of triangle-free cubic graphs
• The complexity of dissociation set problems in graphs
• Parameterized algorithm for 3-path vertex cover
• Large independent sets in triangle-free cubic graphs: beyond planarity
• An improved approximation for maximum \(k\)-dependent set on bipartite graphs
• Relating dissociation, independence, and matchings
• Maximal and maximum dissociation sets in general and triangle-free graphs
• A bound on the dissociation number

Cited In (6)

• On a variant of Flory model
• Enumerating maximal dissociation sets in three classes of grid graphs
• A bound on the dissociation number
• On the \(A_\alpha\)-index of graphs with given order and dissociation number
• On the minimum spectral radius of graphs with given order and dissociation number
• Relating dissociation, independence, and matchings

This page was built for publication: Relating the independence number and the dissociation number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6094030)