Given a connected graph \(H\), its first Zagreb index \(M_{1}(H)\) is equal to the sum of squares of the degrees of all vertices in \(H\). In this paper, we give a best possible lower bound on \(M_{1}(H)\) that guarantees \(H\) is \(\tau\)-path-coverable and \(\tau\)-edge-Hamiltonian, respectively. Our research supplies a continuation of the results presented by Feng et al. (2017).
We study simple, undirected, connected, and finite graphs throughout this paper. Let \(H\) be a graph with vertex set \(V(H)=\{v_{1},\,v_{2},\ldots,\,v_{p}\}\), i.e., \(p=|V(H)|\). For a vertex \(v_s \in V(H)\), the degree \(\text{deg}_{H}(v_{s})\,(=d_s)\) of \(v_s\) is the number of edges incident with \(v_s\) in \(H\). Denote by \((d_{1}, d_{2}, \ldots, d_{p})\) the degree sequence of \(H\) with \(d_{1}\leq d_{2} \leq \cdots \leq d_{p}\). We remove the footnote \(H\) from the symbols in the following context if there is no ambiguity. Furthermore, any given integer sequence \(\pi=(d_1\leq d_2\leq\cdots\leq d_n)\) is called a graphical sequence if there exists a graph \(G\) having \(\pi\) as its vertex degree sequence.
We shall use \(H_1\cup H_2\), \(H_1+H_2\) to denote the union and the join of two vertex-disjoint graphs \(H_1\) and \(H_2\), respectively. We use \(K_p\) to denote the complete graph of order \(p\), and by \(\overline{H}\) we denote the complement of \(H\).
A path with \(|V(H)|\) vertices is called a Hamiltonian path of \(H\). If \(H\) contains a Hamiltonian path, then \(H\) is traceable. We say a graph \(H\), \(\tau\)-path-coverable (\({\tau}\) is a positive integer), if the vertex set of \(H\) can be covered by \({\tau}\) or fewer vertex-disjoint paths. In particular, the notions “\(1\)-path-coverable” and “traceable” are equivalent. A graph \(H\) is \({\tau}\)-edge-Hamiltonian if any collection of pairwise vertex-disjoint paths altogether with at most \({\tau}\) edges belong to a Hamiltonian cycle in \(H\). We refer the reader to [6] for undefined notation and terminology.
The first and second Zagreb indices of a graph \(H\), which were introduced by Gutman and Trinajstić in [13], are defined as: \[M_1(H)=\sum\limits_{x\in V(H)}\,\text{deg}(x)^2~~\mbox{ and }~~M_2(H)=\sum\limits_{xy\in E(H)}\,\text{deg}(x)\,\text{deg}(y).\]
For historical background and mathematical properties of Zagreb indices, one can refer to [7,8,9,10,12,23].
A popular research topic in graph theory is to study whether a given graph has some important property (such as Hamiltonian or traceable). It is shown in [15] that determining whether a graph has a Hamiltonian cycle is NP-complete. Although there are some literatures [11,14,16,17,18,19,20,21] using the bounds of topological indices (or spectral conditions) to confirm the structure of graphs, there are still few results related to them. Recently, results concerning the first Zagreb index or reciprocal degree distance have been utilized to study the \(\kappa\)-connectivity, \(\beta\)-deficiency [3], Hamiltonian-connectedness [1] and \({\hbar}\)-Hamiltonicity, \({\hbar}\)-path-coverability and \({\hbar}\)-edge-Hamiltonicity [4] of graphs. By employing the Wiener (or Harary) index, some vulnerability parameters (such as integrity, toughness, tenacity and binding number) of graphs have been studied [2,22]. However, from the findings above, one can find that there are still some unsolved problems, such as the \({\tau}\)-path coverable and \({\tau}\)-edge Hamiltonian property of graphs in terms of \(M_{1}\).
In this paper, we have partially solved the problems above, that is to say, we give a best possible lower bound on \(M_{1}(H)\) that guarantees \(H\) is \(\tau\)-path-coverable and \(\tau\)-edge-Hamiltonian, respectively.
In this section, we give a best possible lower bound on \(M_{1}(H)\) that guarantees \(H\) is \(\tau\)-path-coverable. First, we present the following important conclusion.
Theorem 2.1. [5] Let \((d_{1}, d_{2}, \ldots, d_{p})\) be a graphical sequence, and \(\tau\geq 1\). Suppose that there is no integer \(k\) with \(1\leq k<\frac{1}{2}(p-\tau)\) such that \(d_{k+\tau}\leq k\) and \(d_{p-k}\leq p-k-\tau-1\). Then any graph with this degree sequence is \(\tau\)-path-coverable.
For any positive integer \(p\), let \(\tau_{1}=\frac{1}{9}\big(8p-9-\sqrt{37p^{2}-54p+9}\big)\) and \(\tau^{*}_{1}=\frac{1}{9}\big(8p-12-\sqrt{37p^{2}-30p+9}\big)\), and denote \(\mathcal{H}=\Big\{K_{1}+(K_{p-{\tau}-2}\cup \overline{K_{{\tau}+1}}\,),\,\,K_{\frac{p-{\tau}-2}{2}}+ (K_{2}\cup \overline{K_{\frac{p+{\tau}-2}{2}}}\,),\,\overline{K_{\frac{p+{\tau}+1}{2}}}+ K_{\frac{p-{\tau}-1}{2}}\Big\}\).
Theorem 2.2. Let \(H\) be a graph with \(p\geq 10\) vertices and \(\tau\in[1,\,p-3]\). If \(M_{1}(H)\geq (p-\tau)(p-\tau-1)^{2}+F(p,\tau)\), then \(H\) is \(\tau\)-path-coverable if and only if \(H\,\notin \mathcal{H}\), where \[F(p,\tau)=\left\{ \begin{array}{lcc} -4\tau^{2}+(8p-10)\tau-3p^{2}+9p-6, ~~~~~~~~\text{if}~p-\tau~\text{is even}~\text{and}~\tau\in [1,\, \tau_{1}];\\ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\text{or}~p-\tau~\text{is odd}~\text{and}~\tau\in [1,\, \tau^{*}_{1}];\\ \big(9\tau^{3} -(25p-22)\tau^{2}+(19p^{2}-28p)\tau\\ -3p^{3}-2p^{2}+24p-16\big)/8, ~~~~~~~~~~~~~~~~~\text{if}~p-\tau~\text{is even}~\text{and}~\tau\in(\tau_{1}, p-4];\\\, \big(9\tau^{3}-(25p-19)\tau^{2}+(19p^{2}-26p+7)\tau\\ -3p^{3}+3p^{2}+3p-3\big)/8, ~~~~~~~~~~~~~~~~~~~~\text{if}~p-\tau~\text{is odd}~\text{and}~\tau\in (\tau^{*}_{1}, p-3]. \end{array} \right.\]
Proof. Sufficiency. Suppose that \(H\) is not \(\tau\)-path-coverable. According to Theorem 2.1, there exists an integer \(s\) with \(1\leq s\leq\frac{1}{2}(p-\tau-1)\) such that \(d_{s+\tau}\leq s\) and \(d_{p-s}\leq p-s-\tau-1\). Recall that \(1\leq \tau\leq p-3.\) Then \[\begin{aligned} M_{1}(H)=&\sum_{j=1}^{p}d_{j}^{2}\leq(s+\tau)s^{2}+(p-2s-\tau)(p-s-\tau-1)^{2}+s(p-1)^{2}\\ =&-s^{3}+(5p-4\tau-4)s^{2}+\big[(p-1)^{2}-2(p-\tau-1)(2p-2\tau-1)\big]s\\ &+(p-\tau)(p-\tau-1)^{2}. \end{aligned}\]
Now we consider the following function \[f(x)=-x^{3}+(5p-4\tau-4)x^{2}+\big[(p-1)^{2}-2(p-\tau-1)(2p-2\tau-1)\big]x,\] with \(1\leq x\leq \frac{1}{2}(p-\tau-1)\). So we get \[f'(x)=-3x^{2}+2(5p-4\tau-4)x+(p-1)^{2}-2(p-\tau-1)(2p-2\tau-1), f''(x)=-6x+2(5p-4\tau-4).\]
Since \(p\geq 10\), \(x\leq \frac{1}{2}(p-{\tau}-1)\) and \(\tau\leq p-3\), we have \[\begin{split} f''(x)=3[-2x+(p-\tau-1)]+7p-5\tau-5 \geq 2p+10>0, \end{split}\] implying that \(f(x)\) is concave up for \(x\in [1, \frac{p-\tau-1}{2}]\).
Case 1. \(p-\tau\) is even. Then the maximum value of \(f(x)\) can only be \(f(1)\) or \(f(\frac{p-\tau-2}{2})\) as \(x\) is an integer. Note that in this case \({\tau}\neq p-3\). Elementary computations yield \[f(1)=-4\tau^{2}+(8p-10)\tau-3p^{2}+9p-6,\label{f1} \tag{1}\] and \[f\bigg(\frac{p-\tau-2}{2}\bigg)=\frac{1}{8}\big(9\tau^{3}-(25p-22)\tau^{2}+(19p^{2}-28p)\tau-3p^{3}-2p^{2}+24p-16\big).\]
By subtracting Eq. (1), \[f\bigg(\frac{p-\tau-2}{2}\bigg)-f(1)=\frac{1}{8}\big(9\tau^{3}-(25p-54)\tau^{2}+(19p^{2}-92p+80)\tau-3p^{3}+22p^{2}-48p+32\big).\]
Define \[\Phi_{1}(\tau)=9\tau^{3}-(25p-54)\tau^{2}+(19p^{2}-92p+80)\tau-3p^{3}+22p^{2}-48p+32 ~\mbox{ for } {\tau}\in [1,\,p-4].\]
One can check that \(\tau_{1}=\frac{1}{9}\big(8p-9-\sqrt{37p^{2}-54p+9}\big)\) is a root of \(\Phi_{1}(\tau)=0\), where \(37p^2-54p+9\) is increasing if \(p\ge10\) and hence is always positive at \(p\ge10\). We can show that \(\Phi_{1}(\tau)=0\) has two other solutions, say \(\tau_{2}\) and \(\tau_{3}\). Without loss of generality, we may suppose that \(\tau_{2}\leq \tau_{3}\). With the help of Matlab, we obtain \(\tau_{2}=p-4\) and \(\tau_{3}=\frac{1}{9}\big(8p-9+\sqrt{37p^{2}-54p+9}\big)\).
Since \(p\geq 10\), we get \(\tau_{1}<p-4\), \(\tau_{3}>p-3\), and \(37p^{2}-54p+9<(8p-18)^{2}\). Hence \(\tau_{1}>\frac{1}{9}\big(8p-9-\sqrt{(8p-18)^{2}}\big)=1\). Note that \(\Phi_{1}(\tau)\) is continuous on \([1,p-4]\). We now consider the following two subcases.
Subcase 1.1. \(\tau\in [1, \tau_{1}]\). Thus \(\Phi_{1}(\tau)\leq 0 \Rightarrow f\big(\frac{p-\tau-2}{2}\big)-f(1)\leq 0\). So \(f(x)\leq f(1)\) for \(x\in \left[1, \frac{p-\tau-2}{2}\right]\). Therefore \[\begin{split} M_{1}(H)&\leq (p-\tau)(p-\tau-1)^{2}-4\tau^{2}+(8p-10)\tau-3p^{2}+9p-6\\ &=(p-\tau)(p-\tau-1)^{2}+f(p,\tau). \end{split}\]
In combination with the conditions of the theorem, the inequality above can only be true if we take the equal sign. Thus \(s=1,\) and correspondingly \(d_{1}=d_{2}=\cdots=d_{\tau+1}=1\), \(d_{\tau+2}=\cdots=d_{p-1}=p-\tau-2\), and \(d_{p}=p-1\). So \(H\cong K_{1}+(K_{p-\tau-2}\cup \overline{K_{\tau+1}}\,)\), contradicting the assumption.
Subcase 1.2. \(\tau\in (\tau_{1}, p-4]\). Thus \(\Phi_{1}(\tau)\geq0 \Rightarrow f\big(\frac{p-\tau-2}{2}\big)-f(1)\geq 0\). So \(f(x)\leq f\big(\frac{p-\tau-2}{2}\big)\) for \(x\in \left[1, \frac{p-\tau-2}{2}\right]\). Hence \[\begin{aligned} M_{1}(H)\leq& (p-\tau)(p-\tau-1)^{2}+\frac{1}{8}\big[9\tau^{3}-(25p-22)\tau^{2}+(19p^{2}-28p)\tau\\ &-3p^{3}-2p^{2}+24p-16\big]\\ =&(p-\tau)(p-\tau-1)^{2}+f(p,\tau). \end{aligned}\]
In combination with the conditions of the theorem, the inequality above can only be true if the equality holds. So \(s=\frac{p-\tau-2}{2}\), and correspondingly \(d_{1}=d_{2}=\cdots=d_{\frac{p+\tau-2}{2}}=\frac{p-\tau-2}{2}\), \(d_{\frac{p+\tau}{2}}=d_{\frac{p+\tau+2}{2}}=\frac{p-\tau}{2}\), and \(d_{\frac{p+\tau+4}{2}}=\cdots =d_{p}=p-1\). Therefore \(H\cong K_{\frac{p-\tau-2}{2}}+ (K_{2}\cup \overline{K_{\frac{p+\tau-2}{2}}}\,)\), a contradiction.
Case 2. \(p-\tau\) is odd. Then the maximum value of \(f(x)\) can only be \(f(1)\) or \(f(\frac{p-\tau-1}{2})\). Note that \[f\bigg(\frac{p-\tau-1}{2}\bigg)=\frac{1}{8}\big(9\tau^{3}-(25p-19)\tau^{2}+(19p^{2}-26p+7)\tau-3p^{3}+3p^{2}+3p-3\big).\] By subtracting Eq. (1), \[f\bigg(\frac{p-\tau-1}{2}\bigg)-f(1)=\frac{1}{8}\big(9\tau^{3}-(25p-51)\tau^{2}+(19p^{2}-90p+87)\tau-3p^{3}+27p^{2}-69p+45\big).\] Denote \[\Phi_{2}(\tau)=9\tau^{3}-(25p-51)\tau^{2}+(19p^{2}-90p+87)\tau-3p^{3}+27p^{2}-69p+45~\mbox{ for }{\tau}\in [1,\,p-3].\]
Note that \(\tau^{*}_{1}=\frac{1}{9}\big(8p-12-\sqrt{37p^{2}-30p+9}\big)\) is a root of \(\Phi_{2}(\tau)=0\), where \(37p^2-30p+9\) is increasing if \(p\ge10\) and hence is always positive at \(p\ge10\). We can show that \(\Phi_{2}(\tau)=0\) has two other solutions, say \(\tau^{*}_{2}\) and \(\tau^{*}_{3}\). Without loss of generality, we may suppose that \(\tau^{*}_{2}\leq \tau^{*}_{3}\). Using Matlab, one can get \(\tau^{*}_{2}=p-3\) and \(\tau^{*}_{3}=\frac{1}{9}\big(8p-12+\sqrt{37p^{2}-30p+9}\big)\).
Since \(p\geq 10\), we have \(\tau^{^{*}}_{1}<p-3\), \(\tau^{*}_{3}>p-3\), and \(37p^{2}-30p+9<(8p-21)^{2}\). So \(\tau_{1}>\frac{1}{9}\big(8p-12-\sqrt{(8p-21)^{2}}\big)=1\). Note that \(\Phi_{2}(\tau)\) is continuous on \([1,p-3]\).
Subcase 2.1. \(\tau\in [1,\, \tau^{*}_{1}]\). Then \(\Phi_{2}(\tau)\leq 0\), which implies that \(f\big(\frac{p-\tau-1}{2}\big)-f(1)\leq 0\). Hence \(f(x)\leq f(1)\) for \(x\in [1, \frac{p-\tau-1}{2}]\). Therefore the remaining proof is the same as the proof in Subcase 1.1, and the conclusion holds.
Subcase 2.2. \(\tau\in (\tau^{*}_{1},\, p-3]\). Thus \(\Phi_{2}(\tau)\geq 0 \Rightarrow f\big(\frac{p-\tau-1}{2}\big)-f(1)\geq 0\). Hence \(f(x)\leq f\big(\frac{p-\tau-1}{2}\big)\) for \(x\in [1, \frac{p-\tau-1}{2}]\). So \[\begin{aligned} M_{1}(H)\leq& (p-\tau)(p-\tau-1)^{2}+\frac{1}{8}\bigg[9\tau^{3}-(25p-19)\tau^{2}+(19p^{2}-26p+7)\tau\\ &-3p^{3}+3p^{2}+3p-3\bigg]\\ =&(p-\tau)(p-\tau-1)^{2}+f(p,\tau). \end{aligned}\]
In combination with the conditions of the theorem, the inequality above can only be true if the equality holds. Thus \(d_{1}=d_{2}=\cdots=d_{\frac{n+\tau+1}{2}}=\frac{p-\tau-1}{2}\), \(d_{\frac{p+\tau+3}{2}}=\cdots =d_{p}=p-1\). Hence \(H\cong \overline{K_{\frac{p+\tau+1}{2}}}+ K_{\frac{p-\tau-1}{2}}\), which contradicts the assumption. Therefore \(H\) is \(\tau\)-path-coverable.
Conversely, suppose that \(H\,\in \mathcal{H}\). Then one can check that \(H\) is not \(\tau\)-path-coverable. ◻
From the proof of Theorem 2.2, if \(\tau=1\), then the following corollary regarding the traceable property can be drawn.
Corollary 2.3. Let \(H\) be a graph with \(p\geq 10\) vertices. If \[M_{1}(H)\geq p^{3}-8p^{2}+25p-24,\] then \(H\) is traceable if and only if \(H\,\ncong K_{1}+(K_{p-3}\cup \overline{K_{2}}\,)\).
Again, we begin with the degree sequence theorem.
Theorem 3.1. [5] Let (\(d_{1}, d_{2}, \ldots,d_{p}\)) be a graphical sequence, \(0\leq \tau \leq p-3\). Suppose that there is no integer \(k\) with \(\tau+1\leq k<\frac{1}{2}(p+\tau)\) such that \(d_{k-\tau}\leq k\) and \(d_{p-k}\leq p-k+\tau-1\). Then any graph with this degree sequence is \(\tau\)-edge-Hamiltonian.
For the following theorem, we will give a best possible lower bound on \(M_{1}(H)\) that guarantees \(H\) is \(\tau\)-edge-Hamiltonian.
Theorem 3.2. Let \(H\) be a graph with \(p\geq 5\) vertices and \(\tau\in[0,\,p-3]\). If \[M_{1}(H)\geq(p+\tau)(p+\tau-1)^{2}-\tau^{3}+3(1-p)\tau^{2}-(3p^{2}-6p+2)\tau-3p^{2}+9p-6,\] then \(H\) is \(\tau\)-edge-Hamiltonian if and only if \(H\,\ncong K_{\tau+1}+(K_{1}\cup K_{p-\tau-2})\).
Proof. Sufficiency. Suppose that \(H\) is not \({\tau}\)-edge-Hamiltonian. According to Theorem 3.1, there exists an integer \(s\) with \(\tau+1\leq s\leq\frac{1}{2}(p+\tau-1)\) such that \(d_{s-\tau}\leq s\), \(d_{p-s}\leq p-s+\tau-1\). Note that \(0\leq \tau\leq p-3\). We have \[\begin{aligned} M_{1}(H)=&\sum_{j=1}^{p}d_{j}^{2}\\ \leq&(s-\tau)s^{2}+(p-2s+\tau)(p-s+\tau-1)^{2}+s(p-1)^{2}\\ =&-s^{3}+(5p+4\tau-4)s^{2}+\big[(p-1)^{2}-2(p+\tau-1)(2p+2\tau-1)\big]s\\ &+(p+\tau)(p+\tau-1)^{2}. \end{aligned}\] We define \[g(x)=-x^{3}+(5p+4\tau-4)x^{2}+\big[(p-1)^{2}-2(p+\tau-1)(2p+2\tau-1)\big]x~\mbox{ with }{\tau}+1\leq x\leq \frac{1}{2}(p+{\tau}-1).\] Thus \[g'(x)=-3x^{2}+2(5p+4\tau-4)x+(p-1)^{2}-2(p+\tau-1)(2p+2\tau-1), g''(x)=-6x+2(5p+4\tau-4).\] Since \(p\geq 5\), \(x\leq \frac{1}{2}(p+{\tau}-1)\) and \(\tau\geq 0\), we obtain \[\begin{aligned} g''(x)=3\big[-2x+(p+\tau-1)\big]+7p+5\tau-5\geq 7p-5>0. \end{aligned}\] So \(g(x)\) is concave up for \(\tau+1 \leq x\leq \frac{p+\tau-1}{2}\).
Case 1. \(p+\tau\) is even. Thus the maximum value of \(g(x)\) can only be \(g(\tau+1)\) or \(g\left(\frac{p+\tau-2}{2}\right)\). Note that in this case \(0\leq \tau\leq p-4\). Elementary computations yield \[g(\tau+1)=-\tau^{3}+3(1-p)\tau^{2}-(3p^{2}-6p+2)\tau-3p^{2}+9p-6,\label{f2} \tag{2}\] and \[g\bigg(\frac{p+\tau-2}{2}\bigg)=\frac{1}{8}\big(-9\tau^{3}-(25p-22)\tau^{2}-(19p^{2}-28p)\tau-3p^{3}-2p^{2}+24p-16\big).\] Then \[g\bigg(\frac{p+\tau-2}{2}\bigg)-g(\tau+1)=-\frac{1}{8}\big(\tau^{3}+(p+2)\tau^{2}-(5p^{2}-20p+16)\tau+3p^{3}-22p^{2}+48p-32\big).\] Let \[\Psi_{1}(\tau)=\tau^{3}+(p+2)\tau^{2}-(5p^{2}-20p+16)\tau+3p^{3}-22p^{2}+48p-32 ~\mbox{ for }{\tau}\in [0, p-4].\]
] \(\Psi_{1}(\tau)\ge0\) for \(0\leq \tau\leq p-4\).
In fact, the first derivative of \(\Psi_{1}(\tau)\) is \[\Psi_{1}'(\tau)=3\tau^{2}+2(p+2)\tau-5p^{2}+20p-16.\]
So the discriminant of \(\Psi_{1}'(\tau)=0\) is \(\Delta=16(4p^{2}-14p+13)\). Since \(p\geq 5\), \(\Psi'_{1}(0)=-5p(p-4)-16<0\) and \(\Delta>0\). By direct calculation, one can obtain that the two real solutions \(\tau'_{1}\) and \(\tau'_{2}\) (say \(\tau'_{1}\leq \tau'_{2}\)) of \(\Psi_{1}'(\tau)=0\) are \[\tau'_{1,2}=\frac{-p-2\mp2\sqrt{4p^{2}-14p+13}}{3}.\]
Clearly, \(\tau'_{1}<0\) and \(\tau'_{2}>p-4\) for \(p\geq 5\). Note that the function \(\Psi_{1}'(\tau)\) is continuous on \([0,\,p-4]\). Thus \(\Psi_{1}'(\tau)<0\) for \(0\leq \tau\leq p-4\), implying that \(\Psi_{1}(\tau)\) is a decreasing function on \(\tau\in[0, p-4]\). An elementary calculation gives \(\Psi_{1}(p-4)=0\). Therefore \(\Psi_{1}(\tau)\geq \Psi_{1}(p-4)=0\), and Claim 1 is proven.
By Claim 1, we immediately have \(g\big(\frac{p+\tau-2}{2}\big)-g(\tau+1)=-\frac{1}{8}\Psi_{1}(\tau)\le0\) for \(0\leq \tau\leq p-4\). Thus \(g\big(\frac{p+\tau-2}{2}\big)\leq g(\tau+1)\) for \(0\leq \tau\leq p-4\) (the equality holds only if \(\tau=p-4\)).
Case 2. \(p+\tau\) is odd. Thus the maximum value of \(g(x)\) can only be \(g(\tau+1)\) or \(g(\frac{p+\tau-1}{2})\). Recall that \(0\leq \tau\leq p-3\) (\(\tau\neq p-4\)). Note that \[g\bigg(\frac{p+\tau-1}{2}\bigg)=-\frac{1}{8}\big(9\tau^{3}+(25p-19)\tau^{2} +(19p^{2}-26p+7)\tau+3p^{3}-3p^{2}-3p+3\big).\] By subtracting Eq. (2), \[g\bigg(\frac{p+\tau-1}{2}\bigg)-g(\tau+1)=-\frac{1}{8}\big(\tau^{3}+(p+5)\tau^{2} -(5p^{2}-22p+9)\tau+3p^{3}-27p^{2}+69p-45\big).\] Consider the following function \[\Psi_{2}(\tau)=\tau^{3}+(p+5)\tau^{2} -(5p^{2}-22p+9)\tau+3p^{3}-27p^{2}+69p-45 ~\mbox{ for }{\tau}\in [0,\,p-3].\] Let \(\tau''_{1}, \tau''_{2}\) and \(\tau''_{3}\) be the three roots of \(\Psi_{2}(\tau)=0\). Without loss of generality, we may suppose that \(\tau''_{1}\leq \tau''_{2}\leq \tau''_{3}\). Using Matlab, one can obtain \(\tau''_{1}=3-3p\), \(\tau''_{2}=p-5\) and \(\tau''_{3}=p-3\).
Since \(p\geq 5\), we get \(\tau''_{1}<0\). Note that \(\Psi_{2}(0)\geq 0\) and \(\Psi_{2}(\tau)\) is continuous on \([0,p-5]\). So \(\Psi_{2}(\tau)\geq 0\) for \(\tau\in [0, p-5]\) or \(\tau=p-3\), and consequently \(g\big(\frac{p+\tau-1}{2}\big)\leq g(\tau+1)\).
From Case 1 and Case 2, we always have \(g(x)\leq g(\tau+1)\) for \(\tau+1 \leq x\leq \frac{p+\tau-1}{2}\). Hence \[M_{1}(H)\leq (p+\tau)(p+\tau-1)^{2}-\tau^{3}+3(1-p)\tau^{2}-(3p^{2}-6p+2)\tau-3p^{2}+9p-6.\]
In combination with the conditions of the theorem, the inequality above can only be true if the equality holds. Hence \(s=\tau+1\), and correspondingly \(d_{1}=\tau+1\), \(d_{2}=\cdots=d_{p-\tau-1}=p-2\), \(d_{p-\tau}=\cdots =d_{p}=p-1\). Therefore \(H\cong K_{\tau+1}+(K_{1}\cup K_{p-\tau-2})\), contradicting the assumption. So \(H\) is \(\tau\)-edge-Hamiltonian.
Conversely, suppose that \(H\,\cong K_{\tau+1}+(K_{1}\cup K_{p-\tau-2})\). Then one can check that \(H\) is not \(\tau\)-edge-Hamiltonian. ◻
The second author has been supported by the National Natural Science Foundation of China (Grant No.12001545).