Relating the independence number and the dissociation number

DOI10.1002/JGT.22965MaRDI QIDQ6094030zbMATH OpenFDO

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)

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

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)

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.

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

Cites work

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

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)