Domination number and feedback vertex number of complements of line graphs

Abstract

In general, determining the domination number $\gamma (G)$ and the feedback vertex number $\tau (G)$ of a claw-free graph (even a line graph) is NP-hard. In contrast, the situation becomes different for the complement of a line graph. In this paper, it is shown that $\gamma (\overline{G})\le 3$ for a claw-free G with $\alpha (G)\ge 3,$ and thus determining the domination number of the complement of a claw-free G with $\alpha (G)\ge 3$ is polynomial, where $\alpha (G)$ is the independence number of G. Furthermore, if a graph G is not a star, has no isolated vertex and isolated edge, then $2\le \gamma (J(G))\le 3,$ where J(G) is the complement of the line graph L(G) of G. If a graph G is not a star, and has no isolated vertex, $\tau (J(G))=n-\Delta (G)-1,$ provided $\Delta (G)\ge 6.$ For the case when $\Delta (G)\le 5,\tau (J(G))$ is also given. Thereby, we are able to show that determining $\tau (J(G))$ is polynomial.

Keywords:

• Line graph
• jump graph
• feedback vertex number
• decycling number
• domination number

1. Introduction

All graphs considered here are finite, undirected and simple. We refer to [6] for unexplained terminology and notation. Let $G=(V(G),E(G))$ be a graph. The order $|V(G)|$ and size $|E(G)|$ are denoted by n and m, respectively. The degree and the neighborhood of a vertex v are denoted by $d_G(v)$ and $N_G(v),$ respectively. The complement of G is denoted by $\overline{G}.$ The maximum degree of G is denoted by $\Delta (G).$

As usual, we use K_n, C_n, and P_n that denote the complete graph, the cycle, and the path of order n, respectively. For two positive integers, r, s, and $K_{r,s}$ denote the complete bipartite graph with r vertices in one part and s vertices in the other part. In particular, $K_{r,s}$ is called a star if $\min \{r,s\}=1.$

Let G and H be two graphs. Their union and intersection are denoted by $G\cup H$ and $G\cap H,$ respectively. If G and H are disjoint, then $G\cup H$ is denoted by G + H, and the join $G\vee H$ is the graph obtained from G + H by joining each vertex of G to all vertices of H. Furthermore, for an integer $k\ge 2,$ if $G_i\cong G$ and $V(G_i)\cap V(G_j)=\varnothing$ for any distinct $i,j\in \{1,\dots ,k\},G_1+\cdots +G_k$ is denoted by kG.

The line graph L(G) of a graph G, is the graph with $V(L(G))=E(G),$ in which two vertices are adjacent if and only if they are adjacent in G. We refer to [4] for some related result on line graphs. In [10], Chartrand et al. called the complement of line graph as the jump graph of a graph G, denoted by J(G). They presented some sufficient conditions for a jump graph to be hamiltonian. Wu and Meng [29] gave a simple characterization of hamiltonian jump graphs, and confirmed the validity of a conjecture and disproved a conjecture in [10]. We refer to [2, 11, 18, 28] for more works on complements of line graphs.

For a given graph F, a graph G is called F-free if no induced subgraph of G is isomorphic to F. In particular, a $K_{1,3}$-free graph is called a claw-free graph. It is well-known that a line graph is a claw-free graph, and thus the complement of a line graph is the complement of a claw-free graph. Note also that the complement of a triangle-free graph is claw-free. For simplicity, we use $H\subseteq G$ to denote that H is a subgraph of G or H is isomorphic to a subgraph G. Let $\mathit{G}$ be a set of graphs. We use $G\in \mathit{G}$ to denote that G is isomorphic to a member of $\mathit{G}.$

Let $S\subseteq V(G)$ and $M\subseteq E(G).$ The subgraph induced by S, denoted by $G[S],$ is the graph with S as its vertex set, in which two vertices are adjacent if and only if they are adjacent in G. The subgraph induced by M, denoted by $G[M],$ is the graph with M as its edge set, and with vertex set composed of all vertices incident with an edge of M in G. We call M a matching of G if no two elements of M is adjacent in G. The matching number of G, denoted by $\alpha \prime (G),$ is the cardinality of a maximum matching of G. A set S is called a clique (resp. independent set) of G if any two vertices of S are adjacent (resp. nonadjacent) in G. The clique number $\omega (G)$ (resp. independence number $\alpha (G))$ is the cardinality of a maximum clique (a maximum independent set) of G.

A set S is a dominating set of a graph G if every vertex in $V(G)\setminus S$ is adjacent to at least one vertex of S in G. The domination number of G, denoted by $\gamma (G),$ is the cardinality of a minimum dominating set of G. The independent domination number of a graph G, denoted by i(G), is the cardinality of a minimum maximal independent set of G.

Poljak [24] showed that finding a maximum clique problem is NP-complete for claw-free graphs. In contrast, Minty [22] and Sbihi [26] showed that there is a polynomial algorithm to find an independent set of maximum weight in a weighted claw-free graph, and so there is a polynomial algorithm to determine $\alpha (G).$ Johnson [13] was the first person to show that the determination of the domination number $\gamma (G)$ of a graph is NP-complete. Later, Hedetniemi and Lasker [15] showed the determination of the domination number $\gamma (G)$ of a claw-free graph is NP-complete.

In contrast, we show that $\gamma (\overline{G})\le 3$ for a claw-free G with $\alpha (G)\ge 3,$ and thus determining the domination number of the complement of a claw-free G with $\alpha (G)\ge 3$ is polynomial. Furthermore, if G is a graph without the isolated vertex and isolated edge and is not a star, then $2\le \gamma (J(G))\le 3,$ where J(G) is the complement of the line graph L(G) of G.

Given a graph G, an interesting question is that how many vertices must be removed so that no cycles remain? In this context, the number is called the decycling number of G, and was originally explored by Beineke and Vandell [8]. Of course, what remains is an induced forest $〈F〉$ of G. As it happens, Erdős, Saks, and Sós considered the more restricted problem of the maximum order of an induced tree in G [12]. The same concept was also studied earlier in the context of electronics where cycles cause interference-hence the alternative but less natural name of vertex feedback. In general, we call this vertex set a feedback vertex set. A set $S\subseteq V(G)$ is called a feedback vertex set of G if G – S is a forest of G. The feedback vertex number of G, denoted by $\tau (G),$ is the cardinality of a minimum feedback set of G. The forest number f(G) of G is $n-\tau (G).$ In general, it is NP-hard to determine the feedback vertex number of a graph G [16]. However, it becomes polynomial for specific families of graphs such as interval graph [20], permutation graphs [7], graphs with maximum degree 3 [27]. Bau and Beineke [3] provided a review of some earlier results and open problems on the decycling number of graphs. We refer to [5, 9, 17, 19] for some recent results on it.

It is not hard to see that for a graph G, $$f(L(G))=\max \{e(H)|H\subseteq G\mathrm{ }\text{is}\text{ a }\text{forest}\mathrm{ }\text{with}\mathrm{ }\Delta (H)\le 2\}.$$

Thus, $f(L(G))\le n-1,$ with equality if and only if G has a Hamilton path, where n is the order of G. Furthermore, determining the feedback number (or the forest number) of a line graph (claw-free) is NP-hard since it is NP-complete to determine whether a graph G has a Hamilton path [6]. It is also well-known that determining the feedback vertex number of a bipartite (triangle-free) graph (their complements are claw-free) is NP-complete [30].

The situation becomes different for the complements of line graphs. In Section 3, we show that $f(J(G))=\Delta (G)+1$ for a graph G if $\Delta (G)=1$ or $\Delta (G)\ge 5.$ For a graph without isolated vertices and with $\Delta (G)=2$ and $m\ge 4,$ we have $3\le f(J(G))\le 4,$ with the left side of equality if and only if G contains a subgraph $H\in \{C_4,P_5,K_3+K_2\}.$ For the case when $\Delta (G)\in \{3,4\},f(J(G))$ is also determined.

2. Domination number

Ore [23] proved that for $\gamma (G)\le \frac{n}{2}$ for a graph G of order n without isolated vertices. McCuaig and Shepherd [21] showed that $\gamma (G)\le \frac{2n}{5}$ for a connected graph with exception of seven graphs. Reed [25] proved that $\gamma (G)\le \frac{3n}{8}.$ Allan and Laskar [1] proved that $\gamma (G)=i(G)$ for a claw-free G. Gernert [14] proved that if G is 2-connected and claw-free of order n, then $\gamma (G)\le \lceil \frac{n}{3}\rceil ,$ and the bound is sharp, since $\gamma (C_n)=\lceil \frac{n}{3}\rceil .$

Theorem 2.1.

Let $k\ge 3$ be a fixed integer. If G is a $K_{1,k}$-free graph with $\alpha (G)\ge k$, then $\gamma (\overline{G})\le k$. In particular, $\gamma (\overline{G})\le 3$ for a claw-free G with $\alpha (G)\ge 3.$

Proof.

Let $S=\{v_1,v_2,\dots ,v_k\}$ be an independent set of G. Take a vertex $v\in V(G)\setminus S.$ Since G is $K_{1,k}$-free, v cannot be adjacent to each element of S in G, implying that v is adjacent to at least one element of S in $\overline{G}.$ This shows that S is a dominating set of $\overline{G},$ and thus $\gamma (\overline{G})\le k.$ □

Note that for a graph G, $\alpha (G)\le 2$ if and only if $\overline{G}$ is a triangle-free graph. In general, $\gamma (\overline{G})$ can be arbitrarily large for a triangle-free graph $\overline{G}.$ For example, if $\alpha (G)=1,$ then $G\cong K_n,$ thus $\gamma (\overline{G})=n.$

A matching M of G is called an induced matching if $E(G[M])=M.$ If G has an isolated edge then, trivially, $\gamma (J(G))=1.$ If G is a star of size m then $J(G)\cong \overline{K_m}$ and thus $\gamma (J(G))=m.$ The following theorem says that for any graph G, one can find a minimum dominating set of J(G) in polynomial time.

Theorem 2.2.

Let G be a graph without isolated vertices and isolated edges. If G is not a star, then $$2\le \gamma (J(G))\le 3.$$

Moreover, $\gamma (J(G))=2$ if and only if one of the following holds:

1. G has an induced matching of size of 2,

2. there exists a vertex of degree 2, whose two neighbors are not adjacent in G.

Proof.

Since G has no isolated edge, $\gamma (J(G))\ge 2.$

If G has a triangle, then the three edges of the triangle form a dominating set of J(G), and thus $\gamma (J(G))\le 3.$ So, assume that G has no triangle. Since G is not a star, $\alpha \prime (G)\ge 2.$ If $\alpha \prime (G)\ge 3,$ then any matching of cardinality three forms a dominating set of J(G). So, now we consider the remaining case when $\alpha \prime (G)=2,$ and let $M=\{e_1,e_2\}$ be a matching of G. If there is no edge adjacent to both e₁ and e₂ in G, then M is a dominating set of J(G). So, now take an edge e₃ adjacent to both e₁ and e₂ in G. Since G has no triangle, any edge $e\in E(G)\setminus \{e_1,e_2,e_3\}$ is not adjacent to some element of $\{e_1,e_2,e_3\},$ implying that $\{e_1,e_2,e_3\}$ is a dominating set of J(G). Summing up the above, $$\gamma (J(G))\le 3.$$

We proceed to show the second half of the statement.

Sufficiency. Let $\{e_1,e_2\}$ be an induced matching of size 2. Any edge $e\in E(G)\setminus \{e_1,e_2\}$ cannot be adjacent to both of e₁ and e₂. Hence e is adjacent to one of e₁ and e₂ in J(G), and thus $\gamma (J(G))\le 2.$ Now assume that there exists a vertex u with $N_G(u)=\{v,w\}$ such that $vw\notin E(G).$ Set $e_1=uv,e_2=uw.$ Clearly, it is easy to see that every edge $e\in E(G)\setminus \{e_1,e_2\}$ is adjacent to one of e₁ and e₂ in J(G). Again, we have $\gamma (J(G))\le 2.$

Necessity. Let $\gamma (J(G))=2$ and $S=\{e_1,e_2\}$ be a dominating set of J(G). We consider two cases. If e₁ and e₂ are not adjacent, then $\{e_1,e_2\}$ is an induced matching of G. Otherwise, an edge e₃ is adjacent to both e₁ and e₂ in G, implying that e is adjacent to neither e₁ nor e₂ in J(G), contradicting that $S=\{e_1,e_2\}$ is a dominating set of J(G). Assume that e₁ and e₂ are adjacent in G and let $e_1=uv$ and $e_2=uw.$ Since S is a dominating set of J(G), it is easy to see that $d_G(u)=2$ and $vw\notin E(G).$ □

3. Forest number

In this section, we determine the forest number of the complement of a line graph. Since an isolated vertex does not affect the number of vertices in the complement of the line graph, we only consider the case where the graph G does not contain isolated vertex. Note that we will use e(G) to represent the number of edges of graph G in the rest of the article. We begin with a simple observation.

Observation 3.1.

If H is a subgraph of a graph G, then J(H) is an induced subgraph of J(G).

Lemma 3.2.

If G is a graph with $e(G)\le \Delta (G)+1$, then J(G) is a forest.

Proof.

Since $e(G)\le \Delta (G)+1,e(G)=\Delta$ or $e(G)=\Delta +1.$ If $e(G)=\Delta ,$ then $G\cong K_{1,\Delta },$ J(G) is a independent set with Δ vertices. If $e(G)=\Delta +1,$ then J(G) is the union of a star of Δ vertices and a isolated vertex. Combining the above, we conclude that J(G) is a forest if $e(G)\le \Delta (G)+1.$ □

Corollary 3.3.

For any graph G with $e(G)\ge \Delta (G)+1,f(J(G))\ge \Delta (G)+1.$

Lemma 3.4.

Let G be a graph with $\Delta (G)=1$ or $\Delta (G)\ge 5$. If J(G) is a forest, then $e(G)\le \Delta (G)+1.$

Proof.

If $\Delta (G)=1$ and J(G) is a forest, then $G\cong 2K_2,$ and thus $e(G)=\Delta (G)+1.$ Now we consider the case when $\Delta (G)\ge 5.$ We assume that $e(G)\ge \Delta (G)+2.$ Let v be a vertex of maximum degree in G, and $e_1,e_2,\dots ,e_{\Delta }$ the edges incident with v in G. Take two edges $e_{\Delta +1},e_{\Delta +2}$ of G not incident with v. We consider two cases.

Case 1.

$e_{\Delta +1}$ and $e_{\Delta +2}$ are not adjacent.

Since $\Delta \ge 5,$ there exists an edge e_k that is adjacent to neither $e_{\Delta +1}$ nor $e_{\Delta +2}$ in G. Then $\{e_k,e_{\Delta +1},e_{\Delta +2}\}$ induces a triangle in J(G).

Case 2.

$e_{\Delta +1}$ and $e_{\Delta +2}$ are adjacent.

Since $\Delta \ge 5,$ there exist two edges e_i and e_j, each of which is adjacent to neither $e_{\Delta +1}$ nor $e_{\Delta +2}$ in G. It can be seen that $\{e_i,e_j,e_{\Delta +1},e_{\Delta +2}\}$ induces a 4-cycle in J(G). □

The following result is an immediate consequence of the above lemmas.

Corollary 3.5.

If G is a graph with $\Delta (G)=1$ or $\Delta (G)\ge 5$, then J(G) is a forest if and only if G has at most $\Delta (G)+1$ edges.

Lemma 3.6.

If G is a graph with $\Delta (G)=2$, then J(G) is a forest if and only if G has at most three edges or is $C_4,P_{5}or{K}_3+K_2.$

Proof.

If $e(G)\le \Delta (G)+1,$ then by Lemma 3.2, J(G) is a forest. It is straightforward to check that J(G) is forest for each $G\in \{C_4,P_5,K_3+K_2\},$ since $J(C_4)\cong 2K_2,J(K_3+K_2)\cong K_{1,3}$ and $J(P_5)\cong P_4.$

Conversely, assume that J(G) is a forest. Since $\{C_4,P_5,2P_3,P_4+K_2,K_3+K_2,P_3+2K_2\}$ is the set of all graphs with e(G) = 4 and $\Delta (G)=2,$ we have $G\in \{C_4,P_5,K_3+K_2\}.$ If $e(G)\ge 5,$ then either $\alpha \prime (G)\ge 3$ or G is a subgraph of $2K_3.$ Let $\{e_1,e_2,e_3\}$ be a matching of G. Clearly, $\{e_1,e_2,e_3\}$ induces a triangle in J(G). In the latter case, J(G) contains C₄. □

Let ${\mathit{G}}_3^5=\{A,B,C,D\},$ where $A,B,C,D$ are the graphs as shown in Figure 1.

Figure 1. All graphs G of size 5 with $\Delta (G)=3$ such that J(G) is a forest.

Lemma 3.7.

If G is a graph with $\Delta (G)=3$, then J(G) is a forest if and only if G has at most four edges or $G\in {\mathit{G}}_3^5$ or $G\in \{K_4,K_4^{\prime }$}, as shown in Figure 2.

Figure 2. All graphs G of size 6 with $\Delta (G)=3$ such that J(G) is a forest.

Proof.

If $e(G)\le \Delta (G)+1,$ then by Lemma 3.2, J(G) is a forest. One can check that both $J(K_4)$ and $J(K_4^{\prime })$ are forests. Since $G\subseteq K_4$ or $G\subseteq K_4^{\prime },$ by Lemma 3.1, J(G) is also a forest.

Assume that J(G) is a forest and $e(G)\ge \Delta (G)+2.$

Claim 1.

If e(G) = 5, $G\in {\mathit{G}}_3^5.$

Let $v\in V(G)$ with $d_G(v)=3,$ and $N_G(v)=\{v_1,v_2,v_3\}.$ Let e₁ and e₂ be two edges of G not incident with v in G. First assume that e₁ and e₂ are not adjacent in G. If $G\ncong C,$ as depicted in Figure 1, then there exists an edge vv_i which is adjacent to neither e₁ nor e₂. So, $\{e_1,e_2,v{v}_i\}$ induces a triangle of J(G), and thus $G\cong C.$ Next assume that e₁ and e₂ are adjacent in G, and let $e_1=xy,e_2=yz.$ If $\{x,y,z\}\cap \{v_1,v_2,v_3\}\le 1,$ J(G) contains C₄. If $\{x,y,z\}\cap \{v_1,v_2,v_3\}\le 2,$ then $G\in \{A,B,D\}.$ Summing up the above, $G\in {\mathit{G}}_3^5.$

Claim 2.

If e(G) = 6, $G\in \{K_4,K_4^{\prime }\}.$

Let $v\in V(G)$ with $d_G(v)=3,$ and $N_G(v)=\{v_1,v_2,v_3\}.$ Let e₁, e₂ and e₃ be the three edges of G not incident with v in G. By the result of Claim 1, $G-e_i\in {\mathit{G}}_3^5$ for each $i\in \{1,2,3\}.$ Otherwise G contains cycles. It follows that $G\in \{K_4,K_4^{\prime }\}.$

Finally, we complete the whole proof by showing that $e(G)\ge 7$ is not possible. Suppose $H\subseteq G$ with e(H) = 7. By Lemma 3.1, J(H) is a forest and further $J(H-e)$ is also a forest for any $e\in E(H).$ By Claim 2, $H-e\in \{K_4,K_4^{\prime }\}$ if possible isolated vertices of H – e are deleted. If $H-e\cong K_4,$ then by $\Delta (H)\le 3,\alpha \prime (H)\ge 3,$ and thus J(H) contains a triangle, a contradiction. If $H-e\cong K_4^{\prime },$ then J(H) contains C₆. The proof is complete. □

Let ${\mathit{G}}_4^6=\{K_1\vee (K_1+P_3),K_1\vee 2K_2$}, as given in Figure 3.

Figure 3. $K_1\vee (K_1+P_3)\mathrm{ }\text{and}\mathrm{ }{K}_1\vee 2K_2.$

Lemma 3.8.

If G is a graph with $\Delta (G)=4$, then J(G) is a forest if and only if G has at most five edges or $G\in {\mathit{G}}_4^6$ or $G\cong K_1\vee (K_1+K_3).$

Proof.

If $e(G)\le \Delta (G)+1,$ then by Lemma 3.2, J(G) is a forest. It is straightforward to check that J(G) is a forest for each $G\in {\mathit{G}}_4^6\cup \{K_1\vee (K_1+K_3)\}.$

Assume that J(G) is a forest and $e(G)\ge \Delta (G)+2.$

Claim 1.

If e(G) = 6, then $G\in {\mathit{G}}_4^6.$

Let $v\in V(G)$ with $d_G(v)=4,$ and $N_G(v)=\{v_1,v_2,v_3,v_4\}.$ Let e₁ and e₂ be two edges of G not incident with v in G. First assume that e₁ and e₂ are not adjacent in G. If $G\ncong K_1\vee 2K_2,$ then there exists an edge vv_i which is adjacent to neither e₁ nor e₂. So, $\{e_1,e_2,v{v}_i\}$ induces a triangle in J(G), and thus $G\cong K_1\vee 2K_2.$ Next assume that e₁ and e₂ are adjacent in G. If $G\ncong K_1\vee (K_1+P_3),$ then there exists two edges vv_i, vv_j each of which is adjacent to neither e₁ nor e₂. So, $\{e_1,e_2,v{v}_i,v{v}_j\}$ induces a C₄ in J(G), and thus $G\cong K_1\vee (K_1+P_3).$

Claim 2.

If e(G) = 7, then $G\cong K_1\vee (K_1+K_3).$

Let $v\in V(G)$ with $d_G(v)=4,$ and $N_G(v)=\{v_1,v_2,v_3,v_4\}.$ Let e₁, e₂ and e₃ be the three edges of G not incident with v in G. By Claim 1 when $e(G)=6,G-e_i\in {\mathit{G}}_4^6$ for each $i\in \{1,2,3\}.$ It follows that $G\in \{K_1\vee (K_1+K_3),K_1\vee P_4,3K_1\vee K_2\}.$ However, $J(K_1\vee P_4)$ contains C₅ and $J(3K_1\vee K_2)$ contains C₆. This shows that $G\cong K_1\vee (K_1+K_3)$ (Figure 4).

Figure 4. $K_1\vee (K_1+K_3).$

Finally, we complete the proof by showing that $e(G)\ge 8$ is impossible. Suppose $e(G)\ge 8$ and $H\subseteq G$ with e(H) = 8. By Lemma 3.1, J(H) is a forest and further $J(H-e)$ is also a forest for any $e\in E(H).$ By Claim 2, $H-e\cong K_1\vee (K_1+K_3),$ (see Figure 5) if possible isolated vertices of H – e are deleted. It follows that H is isomorphic to the graph shown in Figure 5. It is easy to check that J(H) contains C₅, a contradiction. The proof is complete. □

Figure 5. H where $H-e\cong K_1\vee (K_1+K_3)$ for an edge e.

Now we are ready to give our main theorem. The jump graph of a graph G is determined in terms of its maximum degree.

Theorem 3.9.

For any graph G, we have $$f(J(G))=\{\begin{array}{c}\Delta (G),\mathrm{ }\text{if}\mathrm{ }e(G)=\Delta (G);\hfill \\ \Delta (G)+3,\mathrm{ }\text{if}\mathrm{ }\{\begin{array}{c}\Delta (G)=4\mathrm{ }\text{and}\mathrm{ }{K}_1\vee (K_1+K_3)\subseteq G,\hfill \\ \Delta (G)=3\mathrm{ }\text{and}\mathrm{ }{K}_4\subseteq G\mathrm{ }\text{or}\mathrm{ }{K}_4^{\prime }\subseteq G;\hfill \end{array}\hfill \\ \Delta (G)+2,\mathrm{ }\text{if}\mathrm{ }\{\begin{array}{c}G\mathrm{ }\text{has}\text{ a }\text{subgraph}\mathrm{ }H\in \{C_4,P_5,K_3+K_2\}\cup {\mathit{G}}_3^5\cup {\mathit{G}}_4^6,\hfill \\ \Delta (G)=4\mathrm{ }\text{and}\mathrm{ }{K}_1\vee (K_1+K_3)⊈G,\mathrm{ }\text{and}\mathrm{ }{K}_4\subseteq G\mathrm{ }\text{or}\mathrm{ }{K}_4^{\prime }\subseteq G,\hfill \\ \Delta (G)=5\mathrm{ }\text{and}\mathrm{ }{K}_1\vee (K_1+K_3)\subseteq G;\hfill \end{array}\hfill \\ \Delta (G)+1,\text{otherwise}.\hfill \end{array}$$

Proof.

If $e(G)=\Delta (G),$ then $G\cong K_{1,\Delta },$ and $J(G)\cong \overline{K_{\Delta }}.$ So, J(G) is itself a forest, and $f(J(G))=\Delta (G).$

Next assume that $e(G)\ge \Delta (G)+1.$ By Corollary 3.3, $f(J(G))\ge \Delta (G)+1.$ We assume that $f(J(G))\ge \Delta (G)+2.$ Let H be a subgraph of G with $\delta (H)>0$ such that J(H) is a forest, subject to this, e(H) is maximum. By Lemma 3.1, $f(J(G))=e(H).$

If $\Delta (H)=1$ or $\Delta (H)\ge 5,$ then by Corollary 3.5, $e(H)\le \Delta (H)+1.$ Since $e(H)=f(J(G))\ge \Delta (G)+1,$ we have $\Delta (H)=\Delta (G),$ and $f(J(G))=\Delta (G)+1.$ Thus, $\Delta (H)\in \{2,3,4\}.$ Since J(H) is a forest, by Lemmas 3.6-3.8, $e(H)\le \Delta (H)+3.$ If $e(H)=\Delta (H)+2,$ then by $e(H)\ge \Delta (G)+2,$ we have $\Delta (H)=\Delta (G).$ Moreover, by Lemmas 3.6-3.8, $H\in \{C_4,P_5,K_3+K_2\}\cup {\mathit{G}}_3^5\cup {\mathit{G}}_4^6$ with $\Delta (H)=\Delta (G).$

Now assume that $e(H)=\Delta (H)+3.$ Since J(H) is a forest and $\Delta (H)\in \{2,3,4\},$ by Lemmas 3.6-3.8, $\Delta (H)\in \{3,4\}.$ Since $e(H)\ge \Delta (G)+2,\Delta (H)\ge \Delta (G)-1.$ If $\Delta (H)=\Delta (G),$ then by Lemmas 3.6-3.8, $\Delta (G)=3,$ and $K_4\subseteq G$ or $K_4^{\prime }\subseteq G;$ or $\Delta (G)=4$ and $K_1\vee (K_1+K_3)\subseteq G.$

Next suppose that $\Delta (H)=\Delta (G)-1.$ If $\Delta (H)=3,$ then by Lemma 3.7, $H\in \{K_4,K_4^{\prime }\},$ and $\Delta (G)=4.$ Since $f(J(G))=6=\Delta (G)+2,$ by Lemma 3.8, $K_1\vee (K_1+K_3)⊈G.$ If $\Delta (H)=4,$ then $\Delta (G)=5,$ and by Lemma 3.8, $H\cong K_1\vee (K_1+K_3).$ □

Acknowledgments

The authors would like to thank the anonymous referees for their valuable comments and suggestions.

Data availability

No data were used for the research described in the article.

Additional information

Funding

The work was supported by NSFC (No. 12061073) and Open Project of Key Laboratory in Xinjiang Uygur Autonomous Region of China (2022D04026).