betaFeedback

WorksMathematics

On the Kőnig-Egerváry theorem for kk-trees

Abstract

The famous Kőnig-Egerváry theorem is equivalent to the statement that a graph is bipartite if and only if the matching number equals the vertex cover number for every induced subgraph. Bessy, Ochem, and Rautenbach (J. Graph Theory 91 (2019) 73-87) generalized this theorem to kk-paths by introducing the class Gk\mathcal{G}_k of graphs where, for every induced subgraph, the maximum number of disjoint paths of order kk equals the minimum number of vertices intersecting all such paths. They provided complete structural characterizations of graphs in Gk\mathcal{G}_k for k∈{3,4}k \in \{3, 4\}, and for odd kk when no cycle of order less than kk is present. Inspired by this nice work, we extend the Kőnig-Egerváry theorem to kk-trees (i.e., trees with exactly kk vertices). We define the class Jk\mathcal{J}_k of graphs where, for every induced subgraph, the maximum number of disjoint trees of order kk equals the minimum number of vertices intersecting all such trees, and provide complete structural descriptions of graphs in Jk\mathcal{J}_k for all k≥3k \ge 3.

Introduction

An independent edge set in a graph is referred to as a matching. The dual concept of a matching is a vertex cover: a vertex subset U⊆V(G)U \subseteq V(G) such that every edge in GG is incident to at least one vertex in UU. For any graph GG, let ν(G)\nu(G) denote its matching number (the size of a maximum matching) and τ(G)\tau(G) its vertex cover number (the size of a minimum vertex cover). A fundamental observation in graph theory is that ν(G)≤τ(G)\nu(G) \le\tau(G) holds for all graphs. The famous König-Egerváry theorem [6, 11] refines this inequality for bipartite graphs, stating that ν(G)=τ(G)\nu(G) = \tau(G) when GG is bipartite. Equivalently, this theorem characterizes bipartite graphs as those where every induced subgraph HH satisfies ν(H)=τ(H)\nu(H) = \tau(H). This equivalence follows from the fact that odd cycles C2k+1C_{2k+1} violate the equality: for such cycles, ν(C2k+1)=k<τ(C2k+1)=k+1\nu(C_{2k+1}) = k < \tau(C_{2k+1}) = k + 1.

Matching theory can be naturally extended beyond edges to more general subgraph structures through the well-studied packing and covering problems. Given a specified graph class H\mathcal{H}, the packing problem seeks the maximum number of vertex-disjoint subgraphs of GG that are isomorphic to members of H\mathcal{H}. The dual covering problem aims to find the smallest vertex subset U⊆V(G)U \subseteq V(G) such that every subgraph of GG isomorphic to a member of H\mathcal{H} intersects UU.

Note that the classic matching and vertex cover correspond to the special case where H={K2}\mathcal{H} = \{K_2\}, the graph consisting of a single edge. A common generalization focuses on H={Pk}\mathcal{H} = \{P_k\}, where PkP_k is a path with exactly kk vertices. In this setting: A kk-matching is a collection of vertex-disjoint kk-paths in GG, with the maximum size denoted νk′(G)\nu'_k(G). A kk-vertex cover is a vertex set that intersects every kk-path in GG, with the minimum size denoted τk′(G)\tau'_k(G).

Between the two parameters νk′(G)\nu'_k(G) and τk′(G)\tau'_k(G), only the latter seems to have received considerable attention in the literature [4, 5, 8]. For all integers k≥3k \ge3, the computational hardness of the kk-vertex cover problem was established by Brešar et al. [4], and the 3-vertex cover number has been studied extensively [9, 10, 13, 14, 16, 18]. Notably, a vertex set XX of a graph GG forms a 3-vertex cover if and only if its complement V(G)∖XV(G) \setminus X is a so-called dissociation set, a set of vertices inducing a subgraph with maximum degree at most 1. Related problems involving dissociation sets have recently gained significant attention, as demonstrated in [2, 3, 12, 15].

Notably, Tu, Zhang and Shi [15] showed that for every forest FF and every integer k≥2k \ge2, νk′(F)=τk′(F)\nu'_k(F) = \tau'_k(F). Bessy, Ochem and Rautenbach [1] generalized the König-Egerváry theorem to long paths by introducing the graph class Gk\mathcal{G}_k, consisting of all graphs GG such that νk′(H)=τk′(H)\nu'_k(H) = \tau'_k(H) for every induced subgraph HH of GG. They provided complete structural characterizations of graphs in Gk\mathcal{G}_k for k∈{3,4}k \in\{3, 4\}, and for odd kk when no cycle of order less than kk is present.

Since the path PkP_k is a tree on kk vertices, the setting can be further generalized to cases where H\mathcal{H} contains all kk-trees (i.e., trees with exactly kk vertices for a fixed integer kk). Correspondingly, classic graph-theoretic notions of matching and vertex cover extend naturally to their kk-tree analogs: the generalized kk-matching and generalized kk-vertex cover.

  • A collection of vertex-disjoint kk-trees in GG is referred to as a generalized kk-matching, with the size of a maximum such collection denoted the generalized kk-matching number νk(G)\nu_k(G).

  • A generalized kk-vertex cover is a vertex set that intersects every kk-tree in GG, with the

minimum size of such a set termed the generalized kk-vertex cover number τk(G)\tau_k(G).

It follows directly that νk(G)≤τk(G)\nu_k(G) \le\tau_k(G) holds for any graph GG. Notably, when k=3k = 3, the 3-vertex cover coincides with the generalized 3-vertex cover, and the 3-matching coincides with the generalized 3-matching.

Let Jk\mathcal{J}_k denote the class of all graphs GG such that νk(H)=τk(H)\nu_k(H) = \tau_k(H) holds for every induced subgraph HH of GG. Then, a natural question arises: how can the König-Egerváry theorem be extended to kk-trees? In other words, how do we characterize the graphs in Jk\mathcal{J}_k?

In 2024, Li and Xu [7] established that if FF is a forest, then νk(F)=τk(F)\nu_k(F) = \tau_k(F). This result can be restated as follows:

Theorem 1.1 [7] Every forest belongs to Jk\mathcal{J}_k for every integer k≥2k \ge2.

When k=3k = 3, we have J3=G3\mathcal{J}_3 = \mathcal{G}_3, so the characterization in [1] applies. In this paper, we provide complete structural characterizations of graphs in Jk\mathcal{J}_k for all integers k≥3k \ge3.

Preliminaries

Throughout this paper, graphs are finite, simple and undirected; the auxiliary multigraphs may contain loops and parallel edges. In a multigraph, a loop and a pair of parallel edges count as cycles of lengths one and two, respectively. A kk-tree means a tree of order kk, not necessarily an induced subgraph. Let V(G)V(G) and E(G)E(G) represent the vertex set and edge set of a graph GG, respectively. For any graph GG or vertex set XX, let n(⋅)n(\cdot) denote the cardinality of the underlying vertex set: specifically, n(G)=∣V(G)∣n(G) = |V(G)| and n(X)=∣X∣n(X) = |X|. A connected graph of order at least kk contains a tree of order kk. Consequently, a vertex set XX is a generalized kk-vertex cover if and only if every component of G−XG - X has fewer than kk vertices. We use this observation throughout. To provide a comprehensive structural characterization of graphs in Jk\mathcal{J}_k for k≥3k \ge3, we first introduce a new concept: the kk-tree insertion operation.

Let GG be a graph and let uv∈E(G)uv \in E(G) be an edge of GG. The kk-tree insertion operation on edge uvuv is defined through the following sequential steps:

  • Remove the edge uvuv from GG.

  • Introduce a new connected graph GuvG_{uv} with n(Guv)=k−1n(G_{uv}) = k - 1 that is disjoint from GG.

  • Select two vertices x,y∈V(Guv)x, y \in V(G_{uv}) (allowing x=yx = y when u≠vu \ne v; for a loop, require x≠yx \ne y).

  • Connect GuvG_{uv} to G−uvG - uv by adding edges uxux and vyvy.

For an integer k≥3k \ge3, the kk-tree insertion operation applied to a multigraph HH, denoted Tiok(H)\mathrm{Tio}_k(H), is obtained by performing the kk-tree insertion operation on every edge of HH, using mutually disjoint new graphs. For parallel edges, each subscript uvuv refers to the particular edge under consideration. Specifically, when each added graph GuvG_{uv} is a path and the chosen vertices x,yx,y are the two endpoints of this path, the resulting graph is called the kk-subdivision of HH, denoted Subk(H)\mathrm{Sub}_k(H).

The following lemma demonstrates that constructing a graph satisfying νk(G)=τk(G)\nu_k(G)=\tau_k(G) can be achieved through straightforward means, a result analogous to the analysis in [1] for graphs containing a block B=Subk(H)B=\mathrm{Sub}_k(H) for some multigraph HH when H={Pk}\mathcal{H}=\{P_k\}. Specifically, if G=Tiok(H)G=\mathrm{Tio}_k(H) where HH is a connected multigraph containing at least one cycle, then νk(G)=τk(G)=n(H)\nu_k(G)=\tau_k(G)=n(H) for all k≥3k\ge3. This equality for GG alone does not assert that G∈JkG\in\mathcal{J}_k.

To formalize the proof of this lemma, we first introduce a standard graph-theoretic concept: A rooted tree is formed by designating a distinguished vertex in a tree as the root. For a rooted tree TT, the level of a vertex uu, denoted by ℓ(u)\ell(u), is defined as the distance between uu and the root of TT.

Lemma 2.1 Let k≥3k\ge3. Suppose the graph GG contains an induced subgraph BB such that B=Tiok(H)B=\mathrm{Tio}_k(H) for some connected multigraph HH that contains a cycle. Suppose also that every component KK of G−V(H)G-V(H) meeting V(B)∖V(H)V(B)\setminus V(H) satisfies νk(K)=0\nu_k(K)=0. Then

(i) νk(G)=νk(G−V(H))+n(H)\nu_k(G)=\nu_k(G-V(H))+n(H);

(ii) τk(G)=τk(G−V(H))+n(H)\tau_k(G)=\tau_k(G-V(H))+n(H).

Proof. (i) Since HH is connected and contains a cycle, there exists an edge ee incident to some vertex rr such that H−eH-e contains a spanning tree TT of HH. Root TT at rr. For each uv∈E(T)uv\in E(T) with ℓ(u)<ℓ(v)\ell(u)<\ell(v), let TuvT_{uv} be a spanning tree of B[V(Guv)∪{v}]B[V(G_{uv})\cup\{v\}]. Similarly, let TeT_e be a spanning tree of B[V(Ge)∪{r}]B[V(G_e)\cup\{r\}]. Define:

A0={Tuv∣uv∈E(T),ℓ(u)<ℓ(v)}∪{Te}.\mathcal{A}_0=\{T_{uv}\mid uv\in E(T),\ell(u)<\ell(v)\}\cup\{T_e\}.

The collection A0\mathcal{A}_0 consists of n(H)n(H) vertex-disjoint kk-trees. By the additional hypothesis, every component KK of G−V(H)G-V(H) that contains a vertex from V(B)∖V(H)V(B)\setminus V(H) satisfies νk(K)=0\nu_k(K)=0. Therefore, adding A0\mathcal{A}_0 to any generalized kk-matching of G−V(H)G-V(H) yields a generalized kk-matching of GG. It follows that νk(G)≥νk(G−V(H))+n(H)\nu_k(G)\ge\nu_k(G-V(H))+n(H).

Conversely, if M\mathcal{M} is a generalized kk-matching in GG, then since every kk-tree in GG intersecting V(B)V(B) contains a vertex of HH, the set M\mathcal{M} contains at most n(H)n(H) kk-trees intersecting V(B)V(B). Removing all such kk-trees from M\mathcal{M} yields a generalized kk-matching of G−V(H)G - V(H), which implies that νk(G)≤νk(G−V(H))+n(H)\nu_k(G) \le\nu_k(G - V(H)) + n(H).

By combining the upper and lower bounds established above, we conclude that νk(G)=νk(G−V(H))+n(H)\nu_k(G) = \nu_k(G - V(H)) + n(H).

(ii) If XX is a generalized kk-vertex cover in G−V(H)G - V(H), then X∪V(H)X \cup V(H) forms a generalized kk-vertex cover in GG. This directly yields the inequality τk(G)≤τk(G−V(H))+n(H)\tau_k(G) \le\tau_k(G - V(H)) + n(H).

For the converse direction, let XX denote a generalized kk-vertex cover of GG. Set X′=X∩V(B)X' = X \cap V(B). Since X′X' meets every tree in A0\mathcal{A}_0, we have ∣X′∣≥n(H)|X'| \ge n(H). By the component hypothesis, every kk-tree in G−V(H)G - V(H) is disjoint from V(B)V(B). Thus X∖X′X \setminus X' is a generalized kk-vertex cover of G−V(H)G - V(H), and

τk(G)≥τk(G−V(H))+n(H).\tau_k(G) \ge\tau_k(G - V(H)) + n(H).

By combining the upper and lower bounds established above, we conclude that τk(G)=τk(G−V(H))+n(H)\tau_k(G) = \tau_k(G - V(H)) + n(H).

We next establish a straightforward property of the graph family Jk\mathcal{J}_k, which is formalized in the lemma below:

Lemma 2.2 Let k≥3k \ge3 and let pp be a positive integer. Then

(i) Every cycle of length at least kk in every graph in Jk\mathcal{J}_k has length congruent to 00 modulo kk.

(ii) Let Cpk=u1u2⋯upku1C_{pk} = u_1u_2 \cdots u_{pk}u_1 be a cycle of length pkpk. A vertex subset X⊆V(Cpk)X \subseteq V(C_{pk}) is a minimum generalized kk-vertex cover of CpkC_{pk} if and only if X={ui+(j−1)k:j∈[p]}X = \{u_{i+(j-1)k}: j \in[p]\} for some i∈[k]i \in[k].

(iii) Suppose G∈JkG \in\mathcal{J}_k, CC is a cycle in GG with n(C)≥kn(C) \ge k, and u,vu, v are distinct vertices of CC each having at least one neighbor outside V(C)V(C). Then dist⁡C(u,v)≡0(modk)\operatorname{dist}_C(u,v) \equiv0 \pmod{k}.

Proof. Let CnC_n be a cycle of length n≥kn \ge k in G∈JkG \in\mathcal{J}_k, and let F=G[V(Cn)]F = G[V(C_n)]. Then

⌈nk⌉=νk(Cn)≤νk(F)≤⌈nk⌉.\left\lceil\frac{n}{k} \right\rceil= \nu_k(C_n) \le\nu_k(F) \le\left\lceil\frac{n}{k} \right\rceil.

Every generalized kk-vertex cover of a cycle must meet every set of kk consecutive vertices, and selecting vertices with gaps of at most k−1k - 1 gives a cover of cardinality ⌈n/k⌉\left\lceil n/k \right\rceil. Thus

νk(F)=⌊nk⌋≤⌈nk⌉=τk(Cn)≤τk(F).\nu_k(F) = \left\lfloor\frac{n}{k} \right\rfloor\le\left\lceil\frac{n}{k} \right\rceil= \tau_k(C_n) \le\tau_k(F).

Since FF is an induced subgraph of G∈JkG \in\mathcal{J}_k, we have νk(F)=τk(F)\nu_k(F) = \tau_k(F), from which part (i) follows.

Statement (ii) follows directly from two key observations: first, the generalized kk-vertex cover number of the cycle graph CpkC_{pk} satisfies τk(Cpk)=p\tau_k(C_{pk}) = p; second, every generalized kk-vertex cover of CpkC_{p k} must contain at least one vertex from every set of kk consecutive vertices on the cycle.

Suppose GG, cycle CC, and vertices u,vu,v satisfy the hypotheses of part (iii). By (i), we have n(C)≡0(modk)n(C) \equiv0 \pmod{k}. Let u′∈V(G)∖V(C)u' \in V(G) \setminus V(C) be a neighbor of uu, v′∈V(G)∖V(C)v' \in V(G) \setminus V(C) be a neighbor of vv, and define G′G' as the induced subgraph of GG with vertex set V(C)∪{u′,v′}V(C) \cup\{u',v'\}. Then the generalized kk-matching number of G′G' satisfies:

νk(G′)=⌊n(C)+∣{u′,v′}∣k⌋=n(C)k.\nu_k(G') = \left\lfloor\frac{n(C) + |\{u',v'\}|}{k} \right\rfloor= \frac{n(C)}{k}.

Since G∈JkG \in\mathcal{J}_k and G′G' is an induced subgraph of GG, we have τk(G′)=νk(G′)\tau_k(G') = \nu_k(G'). Thus,

τk(C)=νk(C)=n(C)k=νk(G′)=τk(G′).\tau_k(C) = \nu_k(C) = \frac{n(C)}{k} = \nu_k(G') = \tau_k(G').

It follows that every minimum generalized kk-vertex cover of G′G' is also a minimum generalized kk-vertex cover XX of CC. By part (ii), such a set XX must take the form

X={ui+(j−1)k:j∈[p]}={x1,x2,…,xp}X = \{u_{i+(j-1)k}: j \in[p]\} = \{x_1,x_2,\ldots,x_p\}

for some i∈[k]i \in[k].

Note that removing XX from CC yields pp disjoint paths each of order k−1k-1, and there is no kk-tree in G′−XG' - X. If u∉Xu \notin X, its component in C−XC-X, together with u′u', is a connected subgraph of order kk, a contradiction. Thus u∈Xu \in X, and similarly v∈Xv \in X. Thus, dist⁡C(u,v)≡0(modk)\operatorname{dist}_C(u,v) \equiv0 \pmod{k}. □\square

Finally, we introduce a classic result on 2-connected graphs: the Ear Decomposition Theorem. This theorem establishes a fundamental characterization of 2-connected graphs through a constructive decomposition, which we now define formally.

An open ear of a graph is a path whose distinct endpoints belong to the graph and whose internal vertices do not. An ear decomposition of GG is a sequence of edge-disjoint subgraphs P0,P1,…,PsP_0,P_1,\ldots,P_s whose union is GG, such that P0P_0 is a cycle and, for each i≥1i \ge1, PiP_i is an open ear of P0∪⋯∪Pi−1P_0 \cup\cdots\cup P_{i-1}. Ears of length one are allowed. This structural decomposition provides a powerful framework for characterizing 2-connected graphs, as formalized by the following fundamental theorem:

Theorem 2.3 [17] A graph with at least three vertices is 2-connected if and only if it has an ear decomposition. Furthermore, every cycle in a 2-connected graph can serve as the initial cycle in some ear decomposition of the graph.

The graphs in Jk\mathcal{J}_k

In this section, we provide a comprehensive structural characterization of graphs in the family Jk\mathcal{J}_k for k≥3k \ge3. Specifically, we explicitly characterize their block structures and formalize constraints governing their cut-vertices. We denote the cut-vertices of GG contained in BB by x1,…,xmx_1,\ldots,x_m. Let CBC_B be the component of GG containing BB, and let XiX_i be the union of the vertex sets of all components of CB−xiC_B-x_i disjoint from BB. Thus unrelated components of GG are not counted in XiX_i. The sets X1,…,XmX_1,\ldots,X_m are pairwise disjoint. An endblock of GG is defined as a block containing at most one cut-vertex of GG. A block is trivial if it is isomorphic to either K1K_1 or K2K_2.

To formalize our characterization, we first define a new family of graphs that captures these structural properties precisely. Let Hk\mathcal{H}_k denote the family of all graphs GG such that every nontrivial block BB of GG satisfies one of the following conditions:

  • (i) BB is an endblock on exactly kk vertices;

  • (ii) BB is a block on tt vertices where t<kt<k, containing mm cut-vertices of GG with m≤k−t+1m\le k-t+1. Moreover, when m≥2m\ge2, there exists a choice of m−1m-1 sets from X1,X2,…,XmX_1,X_2,\ldots,X_m whose union has fewer than k−t+1k-t+1 vertices;

  • (iii) B=Sub⁡k(H)B=\operatorname{Sub}_k(H) for some multigraph HH, and every cut-vertex of GG contained in BB is a vertex of HH.

For m≥2m\ge2, the additional requirement in (ii) is equivalently

there exists j∈[m] such that ∑i≠jn(Xi)≤k−t.(1)\text{there exists }j\in[m]\text{ such that }\sum_{i\ne j}n(X_i)\le k-t. \tag*{(1)}

If BB satisfies (i) or (ii), there is a vertex r∈V(B)r\in V(B) such that

U=V(B)∪⋃xi≠rXi satisfies n(U)≤k.(2)U=V(B)\cup\bigcup_{x_i\ne r}X_i\text{ satisfies }n(U)\le k. \tag*{(2)}

Here rr is the only cut-vertex when there is exactly one, and may be chosen arbitrarily when there is none. The graph G[U]G[U] is connected, and no edge joins U∖{r}U\setminus\{r\} to V(G)∖UV(G)\setminus U. Conversely, the existence of such a vertex rr for a nontrivial block of order at most kk implies (i) or (ii), since every nonempty XiX_i contains at least one vertex.

With this definition in place, we can now state our main structural characterization theorem:

Theorem 3.1 For every integer k≥3k\ge3, we have Jk=Hk\mathcal{J}_k=\mathcal{H}_k.

Proof. Both classes are closed under disjoint unions, since the parameters are additive over components and the attachment sets are defined within CBC_B. Thus it suffices to consider connected graphs. First, we show that Jk⊆Hk\mathcal{J}_k\subseteq\mathcal{H}_k.

Let GG be an arbitrary connected graph in Jk\mathcal{J}_k. If GG is a tree, then it follows immediately that G∈HkG \in\mathcal{H}_k. If GG is not a tree, let BB denote a nontrivial block of GG. Since every nontrivial block is 2-connected, we can establish the following general result about 2-connected induced subgraphs of GG, which will be applied to BB itself:

Claim 1: If NN is a 2-connected induced subgraph of GG, then either n(N)≤kn(N) \leq k or n(N)≥2kn(N) \geq2k.

Proof of Claim 1: Assume, for contradiction, that k<n(N)<2kk < n(N) < 2k. Since G∈JkG \in\mathcal{J}_k, it follows directly from the definition of Jk\mathcal{J}_k that N∈JkN \in\mathcal{J}_k. Given n(N)<2kn(N) < 2k, we derive νk(N)<2\nu_k(N) < 2. However, as NN is 2-connected, the subgraph N−xN-x remains connected for any vertex x∈V(N)x \in V(N), and n(N−x)≥kn(N-x) \geq k. This implies every generalized kk-vertex cover of NN must contain at least two vertices, so τk(N)≥2\tau_k(N) \geq2. But this contradicts the membership of NN in Jk\mathcal{J}_k, which requires νk(N)=τk(N)\nu_k(N) = \tau_k(N). Thus, our initial assumption is false, and we conclude that either n(N)≤kn(N) \leq k or n(N)≥2kn(N) \geq2k. □\square

Applying Claim 1 to the nontrivial block BB (which is a 2-connected induced subgraph of GG), we conclude that either n(B)≤kn(B) \leq k or n(B)≥2kn(B) \geq2k. We then have the following claim about the structure of BB:

Claim 2: If BB contains a cycle of length less than kk, then n(B)≤kn(B) \leq k.

Proof of Claim 2: Suppose, for contradiction, that BB contains a cycle of length less than kk and n(B)≥2kn(B) \geq2k. By Theorem 2.3, choose an ear decomposition P0∪⋯∪PsP_0 \cup\cdots\cup P_s of BB starting with such a cycle. Put Wi=V(P0∪⋯∪Pi)W_i = V(P_0 \cup\cdots\cup P_i). Each G[Wi]G[W_i] is 2-connected, since it contains the 2-connected ear prefix as a spanning subgraph. Choose the first jj with n(Wj)>kn(W_j) > k. Claim 1 gives

n(Wj−1)≤k,n(Wj)≥2k.n(W_{j-1}) \leq k,\qquad n(W_j) \geq2k.

Hence the ear PjP_j, with endpoints uj,vju_j,v_j, has length at least k+1k+1.

Choose a shortest uju_j–vjv_j path QQ in G[Wj−1]G[W_{j-1}]. Its length qq satisfies 1≤q≤k−11 \leq q \leq k-1, and Cj=Pj∪QC_j = P_j \cup Q is a cycle with dist⁡Cj(uj,vj)=q\operatorname{dist}_{C_j}(u_j,v_j) = q. Since QQ is induced and G[Wj−1]G[W_{j-1}] has minimum degree at least two, each endpoint of QQ has a neighbor in Wj−1∖V(Q)W_{j-1} \setminus V(Q), hence outside CjC_j. Lemma 2.2(iii) implies that qq is a multiple of kk, a contradiction. □\square

With the constraint on the size of such blocks established, we now characterize their structural properties relative to the family Hk\mathcal{H}_k:

Claim 3: Let BB be a nontrivial block of GG with n(B)≤kn(B) \leq k. Then

(a) If n(B)=kn(B) = k, then BB satisfies condition (i) in the definition of Hk\mathcal{H}_k.

(b) If n(B)=t<kn(B) = t < k, then BB satisfies condition (ii) in the definition of Hk\mathcal{H}_k.

Proof of Claim 3: (a) Suppose, for contradiction, that BB is not an endblock of GG. Then BB contains at least two cut-vertices of GG, denoted by uu and vv. Since n(B)=k≥3n(B)=k\ge3, there exists a vertex w∈V(B)∖{u,v}w\in V(B)\setminus\{u,v\}. As BB is 2-connected, both B−uB-u and B−vB-v are connected. Let u′u' and v′v' be neighbors of uu and vv outside BB, respectively, and consider the induced subgraph K=G[V(B)∪{u′,v′}]K=G[V(B)\cup\{u',v'\}]. Since G∈JkG\in\mathcal{J}_k and KK is an induced subgraph of GG, it follows that K∈JkK\in\mathcal{J}_k. Note that n(K)=k+2<2kn(K)=k+2<2k for all k≥3k\ge3, so νk(K)=1\nu_k(K)=1. However, removing any single vertex from KK leaves a connected subgraph of order at least kk, which implies τk(K)≥2\tau_k(K)\ge2. This contradicts the definition of Jk\mathcal{J}_k, which requires νk(K)=τk(K)\nu_k(K)=\tau_k(K). Therefore, our initial assumption is false, and BB must be an endblock of GG.

(b) Similarly, suppose, for contradiction, that BB contains at least k−t+2k-t+2 cut-vertices of GG. Let x1,x2,…,xk−t+2x_1,x_2,\ldots,x_{k-t+2} be cut-vertices of GG contained in BB, and let yiy_i be a neighbor of xix_i outside BB for each i∈{1,2,…,k−t+2}i\in\{1,2,\ldots,k-t+2\}. Let K′K' be the induced subgraph G[V(B)∪{y1,y2,…,yk−t+2}]G[V(B)\cup\{y_1,y_2,\ldots,y_{k-t+2}\}]. Then n(K′)=t+(k−t+2)=k+2n(K')=t+(k-t+2)=k+2, so n(K′)<2kn(K')<2k for all k≥3k\ge3. It follows that νk(K′)=1\nu_k(K')=1. However, removing any single vertex from K′K' leaves a connected subgraph of order at least kk, which implies τk(K′)≥2\tau_k(K')\ge2. Since K′K' is an induced subgraph of GG and G∈JkG\in\mathcal{J}_k, we have K′∈JkK'\in\mathcal{J}_k, which requires νk(K′)=τk(K′)\nu_k(K')=\tau_k(K'). This contradiction establishes that BB has at most k−t+1k-t+1 cut-vertices in $G.

Moreover, suppose BB contains mm cut-vertices where 2≤m≤k−t+12\le m\le k-t+1. Let ai=n(Xi)a_i=n(X_i) and L=k−t+1L=k-t+1. For contradiction, assume that condition (1) fails. Then

∑i≠jai≥L(j∈[m]).\sum_{i\ne j}a_i\ge L\qquad(j\in[m]).

Replacing each aia_i by ci=min⁡{ai,L}c_i=\min\{a_i,L\} preserves these inequalities. Choose integers 0≤bi≤ci0\le b_i\le c_i satisfying ∑i≠jbi≥L\sum_{i\ne j}b_i\ge L for every j∈[m]j\in[m], with s=∑ibis=\sum_i b_i as small as possible. If M=max⁡ibiM=\max_i b_i, the constraints are equivalent to s−M≥Ls-M\ge L. If s−M≥L+1s-M\ge L+1, decreasing any positive bib_i by one preserves the constraints, a contradiction. Consequently,

s−M=L,M≤L,s≤2L.s-M=L,\qquad M\le L,\qquad s\le2L.

For each ii, choose Yi⊆XiY_i\subseteq X_i with n(Yi)=bin(Y_i)=b_i such that G[Yi∪{xi}]G[Y_i\cup\{x_i\}] is connected. This is possible because G[Xi∪{xi}]G[X_i\cup\{x_i\}] is connected. Let

H′=G[V(B)∪⋃i=1mYi].H'=G\left[V(B)\cup\bigcup_{i=1}^{m}Y_i\right].

The graph H′H' is connected and

n(H′)=t+s≤t+2(k−t+1)=2k−t+2≤2k−1,n(H') = t + s \leq t + 2(k-t+1) = 2k-t+2 \leq2k-1,

since t≥3t \geq3 (see Figure 1). Removing xix_i leaves the connected graph formed by B−xiB-x_i and all YjY_j with j≠ij \ne i, whose order is at least t−1+s−bi≥t−1+L=kt-1+s-b_i \geq t-1+L=k. Removing a vertex of BB other than the xix_i leaves a connected graph of at least t−1+s≥kt-1+s \geq k vertices. Finally, if a vertex of YiY_i is removed, then BB together with all YjY_j for j≠ij \ne i remains connected and has at least t+s−bi≥k+1t+s-b_i \geq k+1 vertices. Thus τk(H′)≥2\tau_k(H') \geq2, whereas νk(H′)=1\nu_k(H')=1. This contradicts G∈JkG \in\mathcal{J}_k and proves condition (ii).

Cut-vertices of block B and the selected parts of their attachments

Figure 1. Cut-vertices of block BB and the selected parts of their attachments.

We now consider the remaining case n(B)>kn(B)>k. By Claim 2, every cycle in BB has length at least kk, and Lemma 2.2(i) implies that every such length is a multiple of kk. Every cycle in BB is chordless. Indeed, a chord would divide a cycle into two cycles whose lengths sum to the original length plus two; all three lengths would be divisible by kk, implying k∣2k \mid2, a contradiction.

If BB itself is a cycle, Lemma 2.2(iii) implies that all its vertices having neighbors outside BB occur in one residue class of positions modulo kk. Choosing every kkth vertex in this class as an original vertex (or choosing any class if there are no such vertices) gives B=Sub⁡k(H)B=\operatorname{Sub}_k(H) with all cut-vertices of GG in BB among the vertices of HH.

Otherwise, split the edges of BB into maximal paths P0:u0u1⋯ulP_0:u_0u_1\cdots u_l whose endpoints have degree at least 3 in GG and whose internal vertices have degree 2 in GG. Each such path lies on a cycle CC of BB. Since CC is chordless, both u0u_0 and ulu_l have neighbors outside V(C)V(C). By Lemma 2.2(iii), together with (i), the length ll of P0P_0 is a multiple of kk.

We now define a multigraph HH by replacing every such path u0u1⋯ukpu_0u_1\cdots u_{kp} by the path u0uk⋯ukpu_0u_k\cdots u_{kp} of length pp. It is clear that B=Sub⁡k(H)B=\operatorname{Sub}_k(H), and every cut-vertex of GG contained in BB is a vertex of HH. Thus G∈HkG \in\mathcal{H}_k, and we conclude that Jk⊆Hk\mathcal{J}_k \subseteq\mathcal{H}_k.

Next, we establish the inclusion Hk⊆Jk\mathcal{H}_k \subseteq\mathcal{J}_k.

First, we verify that Hk\mathcal{H}_k is hereditary. Let FF be an induced subgraph of G∈HkG \in\mathcal{H}_k, and let DD be a nontrivial block of FF. The block DD is contained in a unique block BB of GG. If BB satisfies (i) or (ii), choose rr and UU as in (2). If the component of FF containing DD does not contain rr, that component lies in U∖{r}U \setminus\{r\} and has fewer than kk vertices, so DD satisfies (ii). Otherwise, choose z=rz = r if r∈V(D)r \in V(D); if r∉V(D)r \notin V(D), let zz be the unique vertex of DD through which the component of F−V(D)F - V(D) containing rr attaches to DD. Uniqueness follows from the maximality of the block DD. Every vertex outside UU can be reached from DD only through rr, hence through zz. Thus DD together with all its attachments in FF away from zz is contained in UU and has order at most kk. By the equivalence described after (2), DD satisfies (i) or (ii).

If B=Sub⁡k(H)B = \operatorname{Sub}_k(H) satisfies (iii), every internal vertex of a subdivision path has degree 22 in GG. If DD contains one such vertex, its degree in the 22-connected graph DD is at least 22, so both neighbors and both incident edges lie in DD. Continuing along the path shows that the entire subdivision path belongs to DD. Consequently, DD is the kk-subdivision of a connected submultigraph of HH containing a cycle. A cut-vertex of FF in DD has degree at least 33 in FF, so it cannot be an internal subdivision vertex. Therefore DD satisfies (iii), proving the hereditary property.

It now suffices to show that νk(G)=τk(G)\nu_k(G) = \tau_k(G) for every connected graph G∈HkG \in\mathcal{H}_k, which we prove by induction on the sum of the order and size of GG. If GG is a tree, Theorem 1.1 immediately implies νk(G)=τk(G)\nu_k(G) = \tau_k(G). If GG is a cycle of length less than kk, both parameters are zero. If its length is a multiple of kk, then νk(G)=τk(G)\nu_k(G) = \tau_k(G) holds as well. These are the only cycle lengths permitted by the definition of Hk\mathcal{H}_k. We may therefore assume that GG is neither a tree nor a cycle.

Suppose that GG contains a block BB satisfying condition (i). Then νk(G)=νk(G−V(B))+1\nu_k(G) = \nu_k(G - V(B)) + 1 and τk(G)=τk(G−V(B))+1\tau_k(G) = \tau_k(G - V(B)) + 1. By the hereditary property established above, G−V(B)∈HkG - V(B) \in\mathcal{H}_k. Applying the induction hypothesis, we have νk(G−V(B))=τk(G−V(B))\nu_k(G - V(B)) = \tau_k(G - V(B)). Combining these equalities yields νk(G)=τk(G)\nu_k(G) = \tau_k(G).

Suppose GG contains a block BB satisfying condition (ii). Choose rr and UU as in (2), and let G′G' be obtained by replacing BB by a spanning tree on the same vertex set. The graph G′[U]G'[U] remains connected, and G′G' has fewer edges than GG. We show that νk(G′)=νk(G)\nu_k(G') = \nu_k(G) and τk(G′)=τk(G)\tau_k(G') = \tau_k(G).

In both graphs, every kk-tree meeting UU contains rr, since n(U∖{r})<kn(U \setminus\{r\}) < k and this set has no neighbors outside UU. Hence at most one member of a generalized kk-matching meets UU. If a kk-tree TT in such a matching meets UU, remove its vertices in U∖{r}U \setminus\{r\}. The remaining tree is connected and contains rr: no path in TT can enter and leave U∖{r}U \setminus\{r\} without passing through rr twice. In the other graph, grow a tree from rr inside UU using the same number of additional vertices, and join it to the remaining part of TT. This gives a kk-tree disjoint from all other members of the matching. Applying this argument in both directions proves νk(G′)=νk(G)\nu_k(G') = \nu_k(G).

If a generalized kk-vertex cover SS of GG meets UU, then (S∖U)∪{r}(S \setminus U) \cup\{r\} covers G′G' and has cardinality at most ∣S∣|S|. If SS is disjoint from UU, replacing the connected graph on UU by another connected graph on the same vertex set leaves the vertex sets of the components after deleting SS unchanged. Thus SS also covers G′G'. The same argument with GG and G′G' interchanged proves τk(G′)=τk(G)\tau_k(G') = \tau_k(G).

The nontrivial blocks of G′G' are precisely the nontrivial blocks of GG other than BB. Their attachment sets are unchanged, since the replacement preserves connectivity between all vertices of BB; at a cut-vertex shared with another block, the vertices on the BB side remain on that side. Thus G′∈HkG' \in\mathcal{H}_k. By induction, νk(G′)=τk(G′)\nu_k(G') = \tau_k(G'), and consequently νk(G)=τk(G)\nu_k(G) = \tau_k(G).

In all such cases, the induction hypothesis yields νk(G)=τk(G)\nu_k(G) = \tau_k(G). We may therefore assume that GG contains no such blocks. Let B=Sub⁡k(H)B = \operatorname{Sub}_k(H) for some multigraph HH, where every cut-vertex of GG contained in BB is a vertex of HH. The multigraph HH is connected and contains a cycle. Every internal subdivision vertex has degree 2 in GG, so each component of G−V(H)G - V(H) meeting V(B)∖V(H)V(B) \setminus V(H) is an internal subdivision path of order k−1k - 1. Thus the additional hypothesis of Lemma 2.1 holds. Applying that lemma to BB, we obtain νk(G)=νk(G−V(H))+n(H)\nu_k(G) = \nu_k(G - V(H)) + n(H) and τk(G)=τk(G−V(H))+n(H)\tau_k(G) = \tau_k(G - V(H)) + n(H). Since Hk\mathcal{H}_k is hereditary, the induction hypothesis gives νk(G−V(H))=τk(G−V(H))\nu_k(G - V(H)) = \tau_k(G - V(H)), which implies νk(G)=τk(G)\nu_k(G) = \tau_k(G). Since Hk\mathcal{H}_k is hereditary, the same equality holds for every induced subgraph of GG, proving G∈JkG \in\mathcal{J}_k and completing the proof. □\square

References

  1. [1]S. Bessy, P. Ochem, D. Rautenbach, On the König-Egerváry theorem for k-paths, J. Graph Theory, 91 (2019) 73-87.DOI
  2. [2]F. Bock, J. Pardey, L. Penso, D. Rautenbach, A bound on the dissociation number, J. Graph Theory, 103(4)(2023) 661-673.arxiv.org/abs/2202.09190
  3. [3]F. Bock, J. Pardey, L. Penso, D. Rautenbach, Relating the independence number and the dissociation number, J. Graph Theory, 104(2023) 320-340.arxiv.org/abs/2205.03404
  4. [4]B. Brešar, F. Kardoš, J. Katrenič, G. Semanišin, Minimum k-path vertex cover, Discrete Appl. Math., 159 (2011) 1189-1195.DOI
  5. [5]B. Brešar, M. Jakovac, J. Katrenič, G. Semanišin, A. Taranenko, On the vertex k-path cover, Discrete Appl. Math., 161 (2013)1943-1949.
  6. [6]E. Egerváry, Über kombinatorische Eigenschaften von Matrizen, Mat. Fiz. Lapok, 38 (1931) 16-28.
  7. [7]P. Li, M. Xu, The maximum number of maximum generalized 4-independent sets in trees, J. Graph Theory, 107 (2024) 359-380.DOI
  8. [8]X. Li, Z. Zhang and X. Huang, Approximation algorithms for minimum (weight) connected k-path vertex cover, Discrete Appl. Math., 205 (2016) 101-108.DOI
  9. [9]F. Kardoš, J. Katrenič and I. Schiermeyer, On computing the minimum 3-path vertex cover and dissociation number of graphs, Theoret. Comput. Sci., 412 (2011) 7009-7017.DOI
  10. [10]J. Katrenič, A faster FPT algorithm for 3-path vertex cover, Inform. Process. Lett., 116 (2016) 273-278.DOI
  11. [11]D. König, Graphen und Matrizen, Mat. Fiz. Lapok., 38 (1931) 116-119.
  12. [12]W. Sun, S. Li, On the maximal number of maximum dissociation sets in forests with fixed order and dissociation number, Taiwanese J. Math., 27 (4)(2023)647-683.DOI
  13. [13]J. Tu, L. Wu, J. Yuan, L. Cui, On the vertex cover P₃ problem parameterized by treewidth, J. Comb. Optim., 34 (2017) 414-425.DOI
  14. [14]J. Tu and W. Zhou, A primal-dual approximation algorithm for the vertex cover P₃ problem, Theor. Comput. Sci., 412 (2011)7044-7048.DOI
  15. [15]J. Tu, Z. Zhang, Y. Shi, The maximum number of maximum dissociation sets in trees, J. Graph Theory, 96(4) (2021) 472-489.
  16. [16]J. Tu, A survey on the k-path vertex cover problem, Axioms, 2022, 11, 191. https://doi.org/10.3390/axioms11050191.
  17. [17]H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math., 54 (1932) 150-168.
  18. [18]M. Xiao and S. Kou, Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems, Theor. Comput. Sci., 657 (2017) 86-97.DOI

Paper details

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

views · 3

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