betaFeedback

WorksMathematics

A characterization of graphs attaining a lower bound on the dissociation number

Abstract

The dissociation number diss(G){\rm diss}(G) of a graph GG is defined as the maximum cardinality of a vertex subset D⊆V(G)D\subseteq V(G) such that the induced subgraph G[D]G[D] has maximum degree at most 11. In 2023, Bock, Pardey, Penso and Rautenbach [J. Graph Theory 103 (2023), 661–673] showed that diss(G)≥n−13(m+k+c1){\rm diss}(G)\ge n-\frac{1}{3}(m+k+c_1) where n,m,k,c1n, m, k, c_1 denote the numbers of vertices, edges, components and induced cycles of length 11 modulo 33 in GG 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 DD of a graph GG is a dissociation set if the induced subgraph G[D]G[D] has maximum degree at most 1. A dissociation set is called maximum if it has maximum cardinality. The dissociation number diss⁡(G)\operatorname{diss}(G) of GG is the cardinality of a maximum dissociation set in GG. The problem of computing diss⁡(G)\operatorname{diss}(G) 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 GG is a graph with nn vertices and mm edges, then

diss⁡(G)≥{2n3−m6,citep‘[2]‘,2n3,if G is a tree citep‘[2]‘,43∑u∈V(G)1dG(u)+1,if G has no isolated vertex citep‘[2]‘,n⌈Δ+12⌉,if G has maximum degree Δcitep‘[2]‘,n2,if G is outerplanar citep‘[2]‘,2nr+2−m(r+1)(r+2),if m>0, r=⌊mn⌋−1citep‘[3]‘,∑u∈V(G)1dG(u)+1+∑uv∈E(G)(∣NG[u]∪NG[v]∣2)−1,citep‘[4]‘.(1)\operatorname{diss}(G) \ge \begin{cases} \frac{2n}{3}-\frac{m}{6}, & {citep}`[2]`,\\ \frac{2n}{3}, & \text{if }G\text{ is a tree }{citep}`[2]`,\\ \frac{4}{3}\sum_{u\in V(G)}\frac{1}{d_G(u)+1}, & \text{if }G\text{ has no isolated vertex }{citep}`[2]`,\\ \frac{n}{\left\lceil\frac{\Delta+1}{2}\right\rceil}, & \text{if }G\text{ has maximum degree }\Delta{citep}`[2]`,\\ \frac{n}{2}, & \text{if }G\text{ is outerplanar }{citep}`[2]`,\\ \frac{2n}{r+2}-\frac{m}{(r+1)(r+2)}, & \text{if }m>0,\ r=\left\lfloor\frac{m}{n}\right\rfloor-1 {citep}`[3]`,\\ \sum_{u\in V(G)}\frac{1}{d_G(u)+1}+\sum_{uv\in E(G)}\left(\lvert N_G[u]\cup N_G[v]\rvert_{2}\right)^{-1}, & {citep}`[4]`. \end{cases} \tag*{(1)}

Notably, Bock, Pardey, Penso and Rautenbach generalized the lower bound 23n\frac{2}{3}n for trees of order nn (as stated in (1)), and simultaneously strengthened the general lower bound 23n−m6\frac{2}{3}n-\frac{m}{6} for a broad class of graphs. Their result is formalized as follows:

Theorem 1.1 [1] If GG is a graph with nn vertices, mm edges, kk components, and c1c_1 induced cycles of length 11 modulo 33, then

diss⁡(G)≥n−13(m+k+c1).(2)\operatorname{diss}(G)\ge n-\frac{1}{3}(m+k+c_1). \tag*{(2)}

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 {1,2,…,m}\{1,2,\ldots,m\} is denoted as [n][n]. Let ℓ≥3\ell\ge3 and 1≤i1<i2<⋯<ik≤ℓ1\le i_1<i_2<\cdots<i_k\le\ell. A spiked cycle Cℓi1,i2,…,ikC_{\ell}^{i_1,i_2,\ldots,i_k} is the graph obtained from the cycle C=u1u2⋯uℓu1C=u_1u_2\cdots u_{\ell}u_1 by adding kk new vertices vijv_{i_j} and kk edges uijviju_{i_j}v_{i_j} for j∈[k]j\in[k]. The spiked cycle Cℓi1,i2,…,ikC_{\ell}^{i_1,i_2,\ldots,i_k} is called very good (see Figure 1 for illustration) if

Image not extracted

Figure 1. Two very good spiked cycles Cℓ1,3,5C_{\ell}^{1,3,5}, C112,4,9C_{11}^{2,4,9}

  • k≥2k\ge2, ℓ≢1(mod3)\ell\not\equiv1\pmod{3},

  • ij+1−ij≡2(mod3)i_{j+1}-i_j\equiv2\pmod{3} for every j∈[k−1]j\in[k-1], and

  • ℓ+i1−ik≡1(mod3)\ell+i_1-i_k\equiv1\pmod{3}.

The operations ⊕1,⊕2,⊕3\oplus_1,\oplus_2,\oplus_3 and ⊕4\oplus_4 (see Figure 2) are bridge-adding operations between a given graph G′G' and one of the following: a path P3P_3, a cycle CℓC_\ell with ℓ≢0(mod3)\ell\not\equiv0\pmod{3} or a very good spiked cycle. The resulting graphs are denoted as G′⊕1P3G'\oplus_1P_3, G′⊕2P3G'\oplus_2P_3, G′⊕3CℓG'\oplus_3C_\ell and G′⊕4C∗G'\oplus_4C^* respectively. Let C\mathcal{C} be the set of all graphs that arise from the graphs in

Image not extracted

Figure 2. Operations constructing an extremal graph from a smaller extremal graph G′G'

C0={P3}∪{Cℓ:ℓ≥3 is an integer and ℓ≢0(mod3)}∪{C∗:C∗ is a very good spiked cycle}\mathcal{C}_0=\{P_3\}\cup\{C_\ell:\ell\geq3\text{ is an integer and }\ell\not\equiv0\pmod{3}\}\cup\{C^*:C^*\text{ is a very good spiked cycle}\}

by repeated applications of ⊕i\oplus_i for i∈[4]i\in[4].

Theorem 1.2 [1] (1) A connected cycle-disjoint graph satisfies (2) with equality if and only if it belongs to C\mathcal{C}.

(2) For every vertex uu of a graph GG in C\mathcal{C}, GG has a maximum dissociation set not containing uu.

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.

Image not extracted

Figure 3. Two extremal graphs in Theorem 1.1 violate the vertex-disjoint cycle condition.

The operation ⊕5\oplus_5 adds a new vertex xx and the three edges xu,xv,xwxu,xv,xw to a connected graph G1G_1, where u,v,wu,v,w are distinct vertices of G1G_1. Put S={u,v,w}S=\{u,v,w\}. The operation is permitted if

  1. for every maximum dissociation set DD of G1G_1, either ∣D∩S∣≥2|D\cap S|\geq2, or D∩S={z}D\cap S=\{z\} and dG1[D](z)=1d_{G_1[D]}(z)=1;

  1. there is no induced path PP in G1G_1 of length 22 modulo 33 whose endpoints s,ts,t belong to SS and for which V(P)∩S={s,t}V(P)\cap S=\{s,t\}.

Here and throughout the paper, the length of a path is its number of edges.

The operation ⊕6\oplus_{6} adds a new vertex yy and the four edges ya,yb,yc,ydya,yb,yc,yd to the disjoint union of two connected graphs G1,G2G_1,G_2, where a,ba,b are distinct vertices of G1G_1 and c,dc,d are distinct vertices of G2G_2. Put S={a,b,c,d}S=\{a,b,c,d\}. The operation is permitted if

  1. for every maximum dissociation set DD of G1∪G2G_1\cup G_2, either ∣D∩S∣≥2|D\cap S|\ge2, or D∩S={z}D\cap S=\{z\} and d(G1∪G2)[D](z)=1d_{(G_1\cup G_2)[D]}(z)=1;

  1. there is no induced aa–bb path in G1G_1 or induced cc–dd path in G2G_2 of length 2 modulo 3.

The resulting graphs are denoted by G1⊕5{x}G_1\oplus_5\{x\} and G1⊕6G2G_1\oplus_6G_2, respectively; see Figure 4.

Image not extracted

Figure 4. Operations constructing an extremal graph from smaller extremal graphs

Let G1,G2G_1,G_2 be two disjoint connected graphs. We use G1∪˙G2G_1\dot\cup G_2 to denote a graph obtained by adding an edge between an arbitrary vertex of G1G_1 and an arbitrary vertex of G2G_2. Let G\mathcal{G} be the smallest class of connected graphs containing C0C_0 and closed under the operations ⊕i\oplus_i for i∈[6]i\in[6] and under this bridge-joining operation.

Theorem 1.3 A connected graph GG satisfies (2) with equality if and only if G∈GG\in\mathcal{G}.

For convenience, we always use ni,min_i,m_i and c1ic_{1i} to denote ∣V(Gi)∣|V(G_i)|, ∣E(Gi)∣|E(G_i)| and the number of induced cycles with length 1 modulo 3 in GiG_i, respectively. By Theorem 1.3, if G1,G2∈GG_1,G_2\in\mathcal{G}, then

diss⁡(G1∪G2)=diss⁡(G1)+diss⁡(G2)=(n1−13(m1+1+c11))+(n2−13(m2+1+c12))=(n1+n2)−13((m1+m2+1)+1+(c11+c12))=diss⁡(G1∪˙G2).\begin{aligned} \operatorname{diss}(G_1\cup G_2)&=\operatorname{diss}(G_1)+\operatorname{diss}(G_2)\\ &=\left(n_1-\frac{1}{3}(m_1+1+c_{11})\right)+\left(n_2-\frac{1}{3}(m_2+1+c_{12})\right)\\ &=(n_1+n_2)-\frac{1}{3}\left((m_1+m_2+1)+1+(c_{11}+c_{12})\right)\\ &=\operatorname{diss}(G_1\dot\cup G_2). \end{aligned}

Thus, we have the following corollary.

Corollary 1.4 A graph GG satisfies (2) with equality if and only if every component of GG belongs to G\mathcal{G}.

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 G\mathcal{G} satisfy (2) with equality. Furthermore, for every vertex uu of a graph GG in G\mathcal{G}, GG has a maximum dissociation set not containing uu.

Proof: We prove both assertions by induction on the number jj of operations used in a construction from C0C_0. By Theorem 1.2(1)–(2), the result holds for j=0j=0. Suppose the assertions hold for all constructions using fewer than jj operations. We distinguish the following cases according to the final operation.

Case 1: The final operation joins two graphs by a bridge.

Write G=G1⊕G2G=G_1\oplus G_2, where G1,G2∈GG_1,G_2\in\mathcal{G} both have constructions using fewer than jj operations. This case includes the operations ⊕i\oplus_i for i∈[4]i\in[4]. Restricting a dissociation set of GG to the two input graphs gives

diss⁡(G)=diss⁡(G1⊕G2)≤diss⁡(G1)+diss⁡(G2).\operatorname{diss}(G)=\operatorname{diss}(G_1\oplus G_2)\leq\operatorname{diss}(G_1)+\operatorname{diss}(G_2).

By induction, diss⁡(Gi)=ni−13(mi+1+c1i)\operatorname{diss}(G_i)=n_i-\frac{1}{3}(m_i+1+c_{1i}) for i∈[2]i\in[2]. By Theorem 1.1,

diss⁡(G1)+diss⁡(G2)=(n1−13(m1+1+c11))+(n2−13(m2+1+c12))=(n1+n2)−13((m1+m2+1)+1+(c11+c12))=n−13(m+1+c1)≤diss⁡(G1⊕G2)=diss⁡(G).\begin{aligned} \operatorname{diss}(G_1)+\operatorname{diss}(G_2) &=(n_1-\tfrac{1}{3}(m_1+1+c_{11}))+(n_2-\tfrac{1}{3}(m_2+1+c_{12}))\\ &=(n_1+n_2)-\tfrac{1}{3}((m_1+m_2+1)+1+(c_{11}+c_{12}))\\ &=n-\tfrac{1}{3}(m+1+c_1)\\ &\leq\operatorname{diss}(G_1\oplus G_2)\\ &=\operatorname{diss}(G). \end{aligned}

By combining the two inequalities above, we can obtain diss⁡(G)=n−13(m+1+c1)\operatorname{diss}(G)=n-\frac{1}{3}(m+1+c_1). Suppose u1u2u_1u_2 is the edge between G1G_1 and G2G_2 where ui∈V(Gi)u_i\in V(G_i). For an arbitrary vertex x1∈V(G1)x_1\in V(G_1), there exists a maximum dissociation set D1D_1 of G1G_1 that avoids x1x_1 by induction. Let D2D_2 be a maximum dissociation set of G2G_2 that does not contain u2u_2. Then, D1∪D2D_1\cup D_2 is a maximum dissociation set of GG that does not contain x1x_1. Similarly, there exists a maximum dissociation set of GG avoiding any specified vertex of G2G_2.

Case 2: The final operation is ⊕5\oplus_5.

In this case, let G=G1⊕5{x}G=G_1\oplus_5\{x\}, and let D1D_1 be an arbitrary maximum dissociation set of G1G_1. Clearly, D1D_1 is a dissociation set of GG. It follows that diss⁡(G)≥diss⁡(G1)\operatorname{diss}(G)\geq\operatorname{diss}(G_1). Suppose that diss⁡(G)>diss⁡(G1)\operatorname{diss}(G)>\operatorname{diss}(G_1). Since only one vertex is added, diss⁡(G)=diss⁡(G1)+1\operatorname{diss}(G)=\operatorname{diss}(G_1)+1. Every maximum dissociation set DD of GG then contains xx, and D0=D∖{x}D_0=D\setminus\{x\} is a maximum dissociation set of G1G_1. Put S=NG(x)S=N_G(x). Since DD is a dissociation set of GG, either D0∩S=∅D_0\cap S=\varnothing, or D0∩S={z}D_0\cap S=\{z\} and zz is isolated in G1[D0]G_1[D_0]. Both alternatives contradict condition (1) of ⊕5\oplus_5. Hence diss⁡(G)=diss⁡(G1)\operatorname{diss}(G)=\operatorname{diss}(G_1). Thus, every maximum dissociation set of G1G_1 is also a maximum dissociation set of GG. This means that there exists a maximum dissociation set of GG avoiding xx. By induction, there exists a maximum dissociation set of G1G_1 avoiding any specified vertex of G1G_1. It follows that there exists a maximum dissociation set of GG avoiding any specified vertex of G1G_1. To complete the proof of this case, we just need to show that diss⁡(G)=n−13(m+1+c1)\operatorname{diss}(G)=n-\frac{1}{3}(m+1+c_1). Every new induced cycle contains xx. Deleting xx from such a cycle leaves an induced path whose endpoints belong to NG(x)N_G(x) and whose internal vertices avoid NG(x)N_G(x). By condition (2) of ⊕5\oplus_5, 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, c11=c1c_{11}=c_1. By induction,

diss⁡(G1)=n1−13(m1+1+c11)=(n−1)−13((m−3)+1+c11)=n−13(m+1+c1).\begin{aligned} \operatorname{diss}(G_1) &= n_1-\frac{1}{3}(m_1+1+c_{11})\\ &=(n-1)-\frac{1}{3}((m-3)+1+c_{11})\\ &=n-\frac{1}{3}(m+1+c_1). \end{aligned}

Recall that diss⁡(G1)=diss⁡(G)\operatorname{diss}(G_1)=\operatorname{diss}(G). The result holds.

Case 3: The final operation is ⊕6\oplus_6.

Let G1∪G2G_1\cup G_2 be the graph before the last operation, and let DiD_i be an arbitrary maximum dissociation set of GiG_i for i∈[2]i\in[2]. Clearly, D1∪D2D_1\cup D_2 is a dissociation set of GG. It follows that diss⁡(G)≥diss⁡(G1)+diss⁡(G2)\operatorname{diss}(G)\geq\operatorname{diss}(G_1)+\operatorname{diss}(G_2). Arguing as in Case 2, we obtain that

diss⁡(G)=diss⁡(G1)+diss⁡(G2).\operatorname{diss}(G)=\operatorname{diss}(G_1)+\operatorname{diss}(G_2).

Thus, every maximum dissociation set of G1∪G2G_1\cup G_2 is also a maximum dissociation set of GG. This means there is a maximum dissociation set of GG avoiding the added vertex of operation ⊕6\oplus_6. Note that there exists a maximum dissociation set of GiG_i avoiding any specified vertex of GiG_i by induction. Taking the union of suitably chosen maximum dissociation sets of G1G_1 and G2G_2 yields a maximum dissociation set of GG avoiding any prescribed vertex of G1∪G2G_1\cup G_2. To complete the proof of this case, we just need to show that diss⁡(G)=n−13(m+1+c1)\operatorname{diss}(G)=n-\frac{1}{3}(m+1+c_1).

Operation ⊕6\oplus_6 reduces the number of components by 1. Every new induced cycle consists of the added vertex together with an induced aa–bb path in G1G_1 or an induced cc–dd path in G2G_2. Condition (2) excludes new induced cycles of length 1 modulo 3. Thus, c11+c12=c1c_{11}+c_{12}=c_1. By induction,

diss⁡(G1)+diss⁡(G2)=(n1−13(m1+1+c11))+(n2−13(m2+1+c12))=(n1+n2)−13(m1+1+c11+m2+1+c12)=(n1+n2+1)−13((m1+m2+4)+1+(c11+c12))=n−13(m+1+c1).\begin{aligned} \operatorname{diss}(G_1)+\operatorname{diss}(G_2) &=\left(n_1-\frac{1}{3}(m_1+1+c_{11})\right)+\left(n_2-\frac{1}{3}(m_2+1+c_{12})\right)\\ &=(n_1+n_2)-\frac{1}{3}(m_1+1+c_{11}+m_2+1+c_{12})\\ &=(n_1+n_2+1)-\frac{1}{3}((m_1+m_2+4)+1+(c_{11}+c_{12}))\\ &=n-\frac{1}{3}(m+1+c_1). \end{aligned}

Recall that diss⁡(G)=diss⁡(G1)+diss⁡(G2)\operatorname{diss}(G)=\operatorname{diss}(G_1)+\operatorname{diss}(G_2). The result holds. □

The proof of the necessity of Theorem 1.3

Let GG be a connected graph satisfying (2) with equality. By induction on its order nn, we show that G∈GG\in\mathcal{G}. If GG is cycle-disjoint, then the result holds by Theorem 1.2(1). Thus, we may assume that GG is not cycle-disjoint.

Choose a vertex uu such that G−uG-u has at most dG(u)−2d_G(u)-2 components. Such a vertex exists: if a block BB with at least three vertices is not a cycle, choose u∈V(B)u\in V(B) with dB(u)≥3d_B(u)\geq3. Since $B-u is connected, at least three neighbors of uu belong to the same component of G−uG-u. Otherwise, all blocks with at least three vertices are cycles, and two cycle blocks share a vertex uu; each of their two disjoint pairs of neighbors remains connected after deleting uu. In either case, every component of G−uG-u contains a neighbor of uu, giving the required bound.

Let C1,…,CtC_1,\ldots,C_t be the components of G−uG-u, and let c1′c'_1 be the number of induced cycles of length 1 modulo 3 in G−uG-u. Thus t≤dG(u)−2t\le d_G(u)-2 and c1′≤c1c'_1\le c_1.

Claim 1. t=dG(u)−2t=d_G(u)-2, c1′=c1c'_1=c_1, and diss⁡(G−u)=diss⁡(G)\operatorname{diss}(G-u)=\operatorname{diss}(G). Moreover, every CiC_i satisfies (2) with equality.

Proof of Claim 1: By Theorem 1.1,

n−m+1+c13=diss⁡(G)≥diss⁡(G−u)≥(n−1)−(m−dG(u))+t+c1′3=n−m+1+c13+dG(u)−t−2+c1−c1′3≥n−m+1+c13.\begin{aligned} n-\frac{m+1+c_1}{3}=\operatorname{diss}(G)\ge\operatorname{diss}(G-u) \\ &\ge(n-1)-\frac{(m-d_G(u))+t+c'_1}{3} \\ &=n-\frac{m+1+c_1}{3}+\frac{d_G(u)-t-2+c_1-c'_1}{3} \\ &\ge n-\frac{m+1+c_1}{3}. \end{aligned}

All inequalities are equalities. Since both dG(u)−t−2d_G(u)-t-2 and c1−c1′c_1-c'_1 are nonnegative, they both vanish. Hence t=dG(u)−2t=d_G(u)-2, c1′=c1c'_1=c_1, and diss⁡(G−u)=diss⁡(G)\operatorname{diss}(G-u)=\operatorname{diss}(G). The bound in Theorem 1.1 is additive over components, and each component satisfies it. Equality for G−uG-u therefore implies equality for every CiC_i. □

By induction, Ci∈GC_i\in\mathcal{G} for every i∈[t]i\in[t]. In particular, Lemma 2.1 provides a maximum dissociation set of each CiC_i avoiding any prescribed vertex. Put ri=∣NG(u)∩V(Ci)∣r_i=|N_G(u)\cap V(C_i)|. Since GG is connected, ri≥1r_i\ge1, and Claim 1 gives

∑i=1t(ri−1)=dG(u)−t=2.\sum_{i=1}^{t}(r_i-1)=d_G(u)-t=2.

Thus, after reordering the components, either two of the rir_i are 2 and all others are 1, or one of the rir_i 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: rt−1=rt=2r_{t-1}=r_t=2 and ri=1r_i=1 for i∈[t−2]i\in[t-2].

Let a,b∈V(Ct−1)a,b\in V(C_{t-1}) and c,d∈V(Ct)c,d\in V(C_t) be the neighbors of uu in these components, and let

H=G[V(Ct−1)∪V(Ct)∪{u}].H=G[V(C_{t-1})\cup V(C_t)\cup\{u\}].

For every i∈[t−2]i\in[t-2], let wiw_i be the unique neighbor of uu in CiC_i, and choose a maximum dissociation set DiD_i of CiC_i avoiding wiw_i. Any dissociation set of HH can be combined with these DiD_i to form a dissociation set of GG. By Claim 1,

diss⁡(H)+∑i=1t−2diss⁡(Ci)≤diss⁡(G)=diss⁡(G−u)=∑i=1tdiss⁡(Ci).\begin{aligned} \operatorname{diss}(H) + \sum_{i=1}^{t-2} \operatorname{diss}(C_i) \le\operatorname{diss}(G) \\ &= \operatorname{diss}(G-u) = \sum_{i=1}^{t} \operatorname{diss}(C_i). \end{aligned}

Since Ct−1∪Ct=H−uC_{t-1} \cup C_t = H-u is an induced subgraph of HH, we obtain

diss⁡(H)=diss⁡(Ct−1)+diss⁡(Ct).\operatorname{diss}(H) = \operatorname{diss}(C_{t-1}) + \operatorname{diss}(C_t).

Consequently, for every maximum dissociation set D′D' of Ct−1∪CtC_{t-1} \cup C_t, either ∣D′∩{a,b,c,d}∣≥2|D' \cap\{a,b,c,d\}| \ge2, or D′∩{a,b,c,d}={z}D' \cap\{a,b,c,d\} = \{z\} and d(Ct−1∪Ct)[D′](z)=1d_{(C_{t-1}\cup C_t)[D']}(z) = 1. Otherwise, D′∪{u}D' \cup\{u\} would be a dissociation set of HH with more than diss⁡(H)\operatorname{diss}(H) vertices. This proves condition (1) of ⊕6\oplus_6.

Claim 1 also shows that no induced cycle of length 1 modulo 3 contains uu. An induced aa–bb path in Ct−1C_{t-1} or an induced cc–dd path in CtC_t of length 2 modulo 3, together with uu, would yield such a cycle. Hence condition (2) of ⊕6\oplus_6 holds. We may therefore construct H=Ct−1⊕6CtH = C_{t-1} \oplus_6 C_t and then recover

G=H⊎C1⊎⋯⊎Ct−2G = H \mathbin{\uplus} C_1 \mathbin{\uplus} \cdots\mathbin{\uplus} C_{t-2}

by adding the bridges uwiuw_i. Thus G∈GG \in\mathcal{G}.

Case 2: rt=3r_t = 3 and ri=1r_i = 1 for i∈[t−1]i \in[t-1].

Let x,y,zx,y,z be the three neighbors of uu in CtC_t, put S={x,y,z}S = \{x,y,z\}, and let H=G[V(Ct)∪{u}]H = G[V(C_t) \cup\{u\}]. For every i∈[t−1]i \in[t-1], choose a maximum dissociation set DiD_i of CiC_i avoiding the unique neighbor wiw_i of uu in CiC_i. As in Case 1, any dissociation set of HH can be combined with these sets, so

diss⁡(H)+∑i=1t−1diss⁡(Ci)≤diss⁡(G)=∑i=1tdiss⁡(Ci).\operatorname{diss}(H) + \sum_{i=1}^{t-1} \operatorname{diss}(C_i) \le\operatorname{diss}(G) = \sum_{i=1}^{t} \operatorname{diss}(C_i).

The reverse inequality diss⁡(H)≥diss⁡(Ct)\operatorname{diss}(H) \ge\operatorname{diss}(C_t) is immediate, and hence diss⁡(H)=diss⁡(Ct)\operatorname{diss}(H) = \operatorname{diss}(C_t). It follows that, for every maximum dissociation set D′D' of CtC_t, either ∣D′∩S∣≥2|D' \cap S| \ge2, or D′∩S={v}D' \cap S = \{v\} and dCt[D′](v)=1d_{C_t[D']}(v) = 1; otherwise D′∪{u}D' \cup\{u\} would be a larger dissociation set of HH. Thus condition (1) of ⊕5\oplus_5 holds.

If an induced path PP of length 2 modulo 3 had endpoints s1,s2∈Ss_1,s_2 \in S and satisfied V(P)∩S={s1,s2}V(P) \cap S = \{s_1,s_2\}, then PP together with uu would be an induced cycle of length 1 modulo 3 in GG. This contradicts Claim 1. Therefore condition (2) of ⊕5\oplus_5 also holds, and H=Ct⊕5{u}H = C_t \oplus_5 \{u\}. Joining the remaining components by their bridges gives

G=(Ct⊕5{u})⊎C1⊎⋯⊎Ct−1∈G.G = (C_t \oplus_5 \{u\}) \mathbin{\uplus} C_1 \mathbin{\uplus} \cdots\mathbin{\uplus} C_{t-1} \in\mathcal{G}.

This completes the induction. □\square

Conclusion

In this paper, we characterize all extremal graphs achieving equality in Theorem 1.1. Since the dissociation number diss⁡(G)\operatorname{diss}(G) is integer-valued, the lower bound n−13(m+k+c1)n-\frac{1}{3}(m+k+c_1) can be strengthened to ⌈n−13(m+k+c1)⌉\left\lceil n-\frac{1}{3}(m+k+c_1)\right\rceil. Therefore, it is also interesting to characterize all extremal graphs that satisfy diss⁡(G)=⌈n−13(m+k+c1)⌉\operatorname{diss}(G)=\left\lceil n-\frac{1}{3}(m+k+c_1)\right\rceil. The corresponding equality case for trees has been characterized by Li et al. [5].

References

  1. [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
  2. [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
  3. [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
  4. [7]M. Yannakakis, Node-deletion problems on bipartite graphs, SIAM J. Comput., 10 (1981) 310-327.DOI

Paper details

vlnc:W_9wuy72at
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 12

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents