In this paper
AbstractIntroductionThe proof of the sufficiency of Theorem 1.3The proof of the necessity of Theorem 1.3ConclusionReferencesWorksMathematics
A characterization of graphs attaining a lower bound on the dissociation number
Abstract
The dissociation number of a graph is defined as the maximum cardinality of a vertex subset such that the induced subgraph has maximum degree at most . In 2023, Bock, Pardey, Penso and Rautenbach [J. Graph Theory 103 (2023), 661–673] showed that where denote the numbers of vertices, edges, components and induced cycles of length modulo in and they also established a complete characterization of extremal graphs under the vertex-disjoint cycle constraint. Although this partial characterization offers very valuable structural insights, it excludes many simple extremal graphs. So they posed a natural question: How can all extremal graphs be comprehensively characterized without restrictions? In this paper, we give a recursive characterization of all graphs attaining equality in this bound.
Introduction
In this paper, we focus on simple, finite, and undirected graphs. A vertex-set of a graph is a dissociation set if the induced subgraph has maximum degree at most 1. A dissociation set is called maximum if it has maximum cardinality. The dissociation number of is the cardinality of a maximum dissociation set in . The problem of computing was introduced by Yannakakis and was shown to be NP-hard for the class of bipartite graphs [7]. Moreover, the problem remains NP-hard for planar line graphs of planar bipartite graphs with maximum degree 4 [6]. This complexity motivates the study of bounds for the dissociation number, and several tight lower bounds. have been proposed to estimate its minimum possible value in different graph classes: if is a graph with vertices and edges, then
Notably, Bock, Pardey, Penso and Rautenbach generalized the lower bound for trees of order (as stated in (1)), and simultaneously strengthened the general lower bound for a broad class of graphs. Their result is formalized as follows:
Theorem 1.1 [1] If is a graph with vertices, edges, components, and induced cycles of length modulo , then
As a crucial contribution of their paper, they established a characterization of the extremal graphs for Theorem 1.1 under the constraint that every two cycles are vertex-disjoint (see Theorem 1.2(1)). To elaborate on the structure of these extremal graphs, we begin by introducing several foundational concepts.
The set is denoted as . Let and . A spiked cycle is the graph obtained from the cycle by adding new vertices and edges for . The spiked cycle is called very good (see Figure 1 for illustration) if
Figure 1. Two very good spiked cycles ,
, ,
for every , and
.
The operations and (see Figure 2) are bridge-adding operations between a given graph and one of the following: a path , a cycle with or a very good spiked cycle. The resulting graphs are denoted as , , and respectively. Let be the set of all graphs that arise from the graphs in
Figure 2. Operations constructing an extremal graph from a smaller extremal graph
by repeated applications of for .
Theorem 1.2 [1] (1) A connected cycle-disjoint graph satisfies (2) with equality if and only if it belongs to .
(2) For every vertex of a graph in , has a maximum dissociation set not containing .
Note that the restriction that every two induced cycles must be vertex-disjoint is so restrictive that many simple extremal graphs of Theorem 1.1 (as illustrated in Figure 3) are excluded. Bock et al. posed a natural question: How can all extremal graphs of Theorem 1.1 be comprehensively characterized without restrictions? This paper establishes a complete characterization of these extremal graphs (Theorem 1.3). As preparatory groundwork, we also introduce two operations.
Figure 3. Two extremal graphs in Theorem 1.1 violate the vertex-disjoint cycle condition.
The operation adds a new vertex and the three edges to a connected graph , where are distinct vertices of . Put . The operation is permitted if
for every maximum dissociation set of , either , or and ;
there is no induced path in of length modulo whose endpoints belong to and for which .
Here and throughout the paper, the length of a path is its number of edges.
The operation adds a new vertex and the four edges to the disjoint union of two connected graphs , where are distinct vertices of and are distinct vertices of . Put . The operation is permitted if
for every maximum dissociation set of , either , or and ;
there is no induced – path in or induced – path in of length 2 modulo 3.
The resulting graphs are denoted by and , respectively; see Figure 4.
Figure 4. Operations constructing an extremal graph from smaller extremal graphs
Let be two disjoint connected graphs. We use to denote a graph obtained by adding an edge between an arbitrary vertex of and an arbitrary vertex of . Let be the smallest class of connected graphs containing and closed under the operations for and under this bridge-joining operation.
Theorem 1.3 A connected graph satisfies (2) with equality if and only if .
For convenience, we always use and to denote , and the number of induced cycles with length 1 modulo 3 in , respectively. By Theorem 1.3, if , then
Thus, we have the following corollary.
Corollary 1.4 A graph satisfies (2) with equality if and only if every component of belongs to .
The proof of the sufficiency of Theorem 1.3
We prove the sufficiency of Theorem 1.3 by proving a bit stronger result.
Lemma 2.1 All graphs in satisfy (2) with equality. Furthermore, for every vertex of a graph in , has a maximum dissociation set not containing .
Proof: We prove both assertions by induction on the number of operations used in a construction from . By Theorem 1.2(1)–(2), the result holds for . Suppose the assertions hold for all constructions using fewer than operations. We distinguish the following cases according to the final operation.
Case 1: The final operation joins two graphs by a bridge.
Write , where both have constructions using fewer than operations. This case includes the operations for . Restricting a dissociation set of to the two input graphs gives
By induction, for . By Theorem 1.1,
By combining the two inequalities above, we can obtain . Suppose is the edge between and where . For an arbitrary vertex , there exists a maximum dissociation set of that avoids by induction. Let be a maximum dissociation set of that does not contain . Then, is a maximum dissociation set of that does not contain . Similarly, there exists a maximum dissociation set of avoiding any specified vertex of .
Case 2: The final operation is .
In this case, let , and let be an arbitrary maximum dissociation set of . Clearly, is a dissociation set of . It follows that . Suppose that . Since only one vertex is added, . Every maximum dissociation set of then contains , and is a maximum dissociation set of . Put . Since is a dissociation set of , either , or and is isolated in . Both alternatives contradict condition (1) of . Hence . Thus, every maximum dissociation set of is also a maximum dissociation set of . This means that there exists a maximum dissociation set of avoiding . By induction, there exists a maximum dissociation set of avoiding any specified vertex of . It follows that there exists a maximum dissociation set of avoiding any specified vertex of . To complete the proof of this case, we just need to show that . Every new induced cycle contains . Deleting from such a cycle leaves an induced path whose endpoints belong to and whose internal vertices avoid . By condition (2) of , this path cannot have length 2 modulo 3. Thus no new induced cycle has length 1 modulo 3, and the old induced cycles are unchanged. Consequently, . By induction,
Recall that . The result holds.
Case 3: The final operation is .
Let be the graph before the last operation, and let be an arbitrary maximum dissociation set of for . Clearly, is a dissociation set of . It follows that . Arguing as in Case 2, we obtain that
Thus, every maximum dissociation set of is also a maximum dissociation set of . This means there is a maximum dissociation set of avoiding the added vertex of operation . Note that there exists a maximum dissociation set of avoiding any specified vertex of by induction. Taking the union of suitably chosen maximum dissociation sets of and yields a maximum dissociation set of avoiding any prescribed vertex of . To complete the proof of this case, we just need to show that .
Operation reduces the number of components by 1. Every new induced cycle consists of the added vertex together with an induced – path in or an induced – path in . Condition (2) excludes new induced cycles of length 1 modulo 3. Thus, . By induction,
Recall that . The result holds. □
The proof of the necessity of Theorem 1.3
Let be a connected graph satisfying (2) with equality. By induction on its order , we show that . If is cycle-disjoint, then the result holds by Theorem 1.2(1). Thus, we may assume that is not cycle-disjoint.
Choose a vertex such that has at most components. Such a vertex exists: if a block with at least three vertices is not a cycle, choose with . Since $B-u is connected, at least three neighbors of belong to the same component of . Otherwise, all blocks with at least three vertices are cycles, and two cycle blocks share a vertex ; each of their two disjoint pairs of neighbors remains connected after deleting . In either case, every component of contains a neighbor of , giving the required bound.
Let be the components of , and let be the number of induced cycles of length 1 modulo 3 in . Thus and .
Claim 1. , , and . Moreover, every satisfies (2) with equality.
Proof of Claim 1: By Theorem 1.1,
All inequalities are equalities. Since both and are nonnegative, they both vanish. Hence , , and . The bound in Theorem 1.1 is additive over components, and each component satisfies it. Equality for therefore implies equality for every . □
By induction, for every . In particular, Lemma 2.1 provides a maximum dissociation set of each avoiding any prescribed vertex. Put . Since is connected, , and Claim 1 gives
Thus, after reordering the components, either two of the are 2 and all others are 1, or one of the is 3 and all others are 1. These are the following two cases. Empty sums and empty collections of additional bridge joins are omitted.
Case 1: and for .
Let and be the neighbors of in these components, and let
For every , let be the unique neighbor of in , and choose a maximum dissociation set of avoiding . Any dissociation set of can be combined with these to form a dissociation set of . By Claim 1,
Since is an induced subgraph of , we obtain
Consequently, for every maximum dissociation set of , either , or and . Otherwise, would be a dissociation set of with more than vertices. This proves condition (1) of .
Claim 1 also shows that no induced cycle of length 1 modulo 3 contains . An induced – path in or an induced – path in of length 2 modulo 3, together with , would yield such a cycle. Hence condition (2) of holds. We may therefore construct and then recover
by adding the bridges . Thus .
Case 2: and for .
Let be the three neighbors of in , put , and let . For every , choose a maximum dissociation set of avoiding the unique neighbor of in . As in Case 1, any dissociation set of can be combined with these sets, so
The reverse inequality is immediate, and hence . It follows that, for every maximum dissociation set of , either , or and ; otherwise would be a larger dissociation set of . Thus condition (1) of holds.
If an induced path of length 2 modulo 3 had endpoints and satisfied , then together with would be an induced cycle of length 1 modulo 3 in . This contradicts Claim 1. Therefore condition (2) of also holds, and . Joining the remaining components by their bridges gives
This completes the induction.
Conclusion
In this paper, we characterize all extremal graphs achieving equality in Theorem 1.1. Since the dissociation number is integer-valued, the lower bound can be strengthened to . Therefore, it is also interesting to characterize all extremal graphs that satisfy . The corresponding equality case for trees has been characterized by Li et al. [5].
References
- [1]F. Bock, J. Pardey, L.D. Penso, D. Rautenbach, A bound on the dissociation number, J. Graph Theory, 103 (4) (2023) 661–673.arxiv.org/abs/2202.09190
- [5]P. Li, J. Wu, W. Jin, M. Xu, The characterization of the lower bound on the dissociation number of trees, Discrete Math., 349 (2026) 114854.DOI
- [6]Y. Orlovich, A. Dolgui, G. Finke, V. Gordon, F. Werner, The complexity of dissociation set problems in graphs, Discrete Appl. Math., 159 (13) (2011) 1352-1366.DOI
- [7]M. Yannakakis, Node-deletion problems on bipartite graphs, SIAM J. Comput., 10 (1981) 310-327.DOI