On sufficient conditions for a graph to be \(k\)-path-coverable, \(k\)-edge-hamiltonian, Hamilton-connected, traceable and \(k^{-}\)-independent

1. Introduction

Let \(G=(V(G), E(G))\) be a finite simple connected graph with \(n=|V(G)|\) vertices and \(m=|E(G)|\) edges. The number of edges in \(G\) that are incident to a vertex \(v\in V(G)\) is called its degree and denoted by \(d_{G}(v)\). A sequence of positive integers \(\pi=(d_{1}, d_{2}, \cdots, d_{n})\) is called the degree sequence of \(G\) if \(d_{i}=d_{G}(v_i)\), \(i=1, 2, \cdots, n\), holds for any \(v_i\in{V(G)}\). In particular, if the vertex degrees is non-decreasing, we use \(\pi=(d_{1}\leq d_{2}\leq\cdots\leq d_{n})\) to denote the degree sequence for simplicity. We denote by \(K_{n}\) and \(\overline{K}_{n}\) the complete graph with \(n\) vertices and its complement graph, respectively.

A cycle (resp. path) passing through each vertex of a graph is said to be a Hamilton cycle (resp. Hamilton path). We call the graph is Hamiltonian (resp. traceable) if there exists a Hamilton cycle (resp. Hamilton path) in it. For some integer \(k\), a connected graph \(G\) is said to be \(k\)-edge-hamiltonian if any collection of vertex-disjoint paths with at most \(k\) edges altogether belong to a hamiltonian cycle in \(G\). A graph is \(k\)-path-coverable if its vertex set can be covered by \(k\) or fewer vertex-disjoint paths, and we call a graph is Hamilton-connected if every two vertices in \(G\) are connected by a Hamiltonian path. For a graph \(G\), a subset \(I\) of \(V(G)\) is said to be an independent set of \(G\) if the induced subgraph \(G[I]\) is a graph with \(|I|\) isolated vertices. The independence number, denoted by \(\alpha(G)\), of \(G\) is the number of vertices in the largest independent set of \(G\), and we call a graph is \(k^{-}\)-independent if its independent number does not exceed to a positive real number \(k\). In what follows, we always omit the subscript \(G\) from the notation if there is no confuse from the context. For standard graph-theoretic notation and terminology the reader is referred to [1].

2. Motivation

In theoretical chemistry molecular structure descriptor, also called topological indices, are used to characterize the properties of the corresponding graph. Up to now, a series of topological indices, such as Wiener index [2] and Harary index [3,4], have been introduced and found a large amount of useful applications. Other nice related results and information could be found in [5,6,7] and therein.

The inverse degree, denoted by \(ID(G)\), of a graph \(G\) was defined as the sum of the inverses of the degrees of the vertices, formally

\begin{equation*} \begin{split} ID(G)=\sum_{u\in V}\frac{1}{d_{G}(u)}, \end{split} \end{equation*} which maybe firstly be investigated in the conjectures of computer program [8]. It was stated that Zhang et al., [9] gave out a counterexample of the Graffiti's conjecture, and obtained the best bound upper and lower bounds on \(ID(T)+\beta(T)\) for any tree \(T\), where \(\beta(T)\) denotes the matching number of \(T\). Two years later, Hu et al., [10] characterized the extremal graphs with respect to the inverse degree among all connected graphs of order \(n\) and with \(m\) edges. In 2008, Dankelmann et al., [11] proved that, if \(G\) is connected and of order \(n\), then the diameter of \(G\) is less than \((3ID(G)+2+o(1))\frac{log n}{log{log n}}\) which improves a bound by Erdös et al., [12]. About one year after, Dankelmann et al., [13] found a relation between the inverse degree and edge-connectivity of graph. In [14], Mukwembi presented a better bound on diameter by the inverse degree than those mentioned in the previous two papers. It is worth mentioning that Li et al., [15] improved the bound on diameter in terms of the inverse degree by Dankelmann et al., [11] for trees and unicyclic graphs. In 2013, Chen and Fujita [16] obtained a nice relation between diameter and the inverse degree of a graph, which settled a conjecture in [14]. In 2016, Xu and co-author determined some upper and lower bounds on the inverse degree for a connected graph in terms of other graph parameters, such as chromatic number, clique number, connectivity, number of cut edges and matching number [17]. We encourage the interested reader to consult [18,19,20,21] and the references therein for more details.

The problem of determining whether a graph keeps certain reasonable property is often difficult and meaningful in graph theory. It is reported in [22] that determining whether a graph is traceable or Hamiltonian is \(NP\)-complete. From then on, exploring such sufficient conditions for graphs attracts a vast number of mathematicians. For example, the authors in [23] studied the traceability of graphs by using a kind of distance-based topological index, the Harary index. In the same year, similar problem was also considered in [24] and a new sufficient condition was found for a graph to be traceable based on the Wiener index. Subsequently, these results mentioned previously were generalized by means of other techniques, we encourage readers to consult [25,26] for more details and information. To the best of our knowledge, there are absolutely few such conditions in terms of the well-known degree-based and distance-based topological indices.

Motivated by the results in [27], in the subsequent sections we attempt to explore sufficient conditions in terms of the inverse degree for graphs to be \(k\)-path-coverable, \(k\)-edge-hamiltonian, Hamilton-connected, traceable and \(k^{-}\)-independent, respectively.

3. \(k\)-path-coverable graphs

In this section, a sufficient condition for a graph to be \(k\)-path-coverable, graphs is presented. To do this, we need the following well-known theorem, which could be found in the book of Bondy and Lesniak, respectively.

Lemma 1. ([28,29]) Let \(\pi=(d_1\leq d_2\leq \cdots \leq d_n)\) be a degree sequence, and also let \(k \geq 1\). If \[d_{i+k}\leq i\Rightarrow d_{n-i}\geq n-i-k~\text{for}~1\leq i< \frac{n-k}{2},\] then \(\pi\) enforces \(k\)-path-coverable.

Now we shall state the main result:

Theorem 1. Let \(G\) be a connected graph of order \(n\geq 8\) and \(k \geq 1\). If \(ID(G)< Q_{1}(n,k)\), where \begin{equation*} Q_{1}(n,k)= \begin{cases} \frac{- k^2 - 3n^2 + 2n + 1}{2(n - 1)(k - n + 1)}& \text{if}~n-k-1~\text{is even};\\[3mm] \frac{- k^3 + (n - 2)k^2 + (- 3n^2 + 4n)k + 3n^3 - 2n^2 - 16n + 16}{2(n - 1)(k^2 - 2kn + 2k + n^2 - 2n)} & \text{if}~n-k-1~\text{is odd},\\ \end{cases} \end{equation*} then \(G\) is \(k\)-path-coverable. Moreover, \(ID(G)=Q_{1}(n,k)\) if and only if \(G\cong K_{\frac{n-k-1}{2}}+(K_1\cup \overline{\frac{n+k-1}{2}})\) if \(n-k-1\) is even; and \(G\cong K_{\frac{n-k-2}{2}}+(K_2\cup \overline{K_\frac{n+k-2}{2}})\) if \(n-k-1\) is odd.

Proof. Suppose that \(G\) is not \(k\)-path-coverable. In view of Lemma 1, there exists an integer \(i\) such that \(d_{i+k}\leq i\) and \(d_{n-i}\leq n-i-k-1\) for \(1\leq i\leq \frac{n-k-1}{2}\). Hence, we have \begin{equation*} \begin{split} ID(G)&=\sum_{i=1}^{n}\frac{1}{d_i}\\ &\geq \frac{i+k}{i}+ \frac{n-2i-k}{n-i-k-1}+ \frac{i}{n-1}. \end{split} \end{equation*} For simplicity, we define the following function on \([1, \frac{n-k-1}{2}]\): \begin{equation*} \begin{split} \mathcal{A}_1(x)=\frac{x+k}{x}+ \frac{n-2x-k}{n-x-k-1}+ \frac{x}{n-1}. \end{split} \end{equation*} It is routine to check that the derivative of \(\mathcal{A}_1(x)\) equals to \begin{equation*} \begin{split} \mathcal{A}_1'(x)=\frac{r_1(x)}{x^2(n - 1)(x + k - n + 1)^2}, \end{split} \end{equation*} where \begin{equation*} r_1(x)=x^4 + (2k - 2n + 2)x^3 + (k^2 + (2 - 2n)k + n - 1)x^2-k(n - 1)(k - n + 1)(2x + k - n + 1). \end{equation*} Similarly, the second derivative of \(\mathcal{A}_1''(x)\) is \begin{equation*} \begin{split} \mathcal{A}_1''(x)=\frac{\eta(x)}{x^3(x + k - n + 1)^3}\,, \end{split} \end{equation*} where \begin{equation*} \begin{split} \eta(x)&=(2n - 4)x^3 + (6k^2 + ( - 6n+ 6)k)x^2 + (6k^3 + ( - 12n+ 12)k^2 + (6n^2 - 12n + 6)k)x \\ & \;\;\;+ 2k^4 + ( - 6n- 6)k^3 + (6n^2 - 12n + 6)k^2 + (- 2n^3 + 6n^2 - 6n + 2)k. \end{split} \end{equation*} By simple calculations, we have \begin{equation*} \begin{split} \eta''(x)=(12n - 24)x + 12k^2 + (12 - 12n)k, \end{split} \end{equation*} and its unique root \(\eta_0=\frac{- k^2 + (n - 1)k}{n - 2}\) satisfies the following property:

Fact 1. \(1< \eta_0\leq \frac{n-k-1}{2}\) if \(k\in [1, \frac{n-2}{2}]\) and \(\eta_0\geq \frac{n-k-1}{2}\) if \(k\in [\frac{n-2}{2}, n-3]\).

In fact, it can be easily seen that \(\eta_0>1\). It remains to prove the last assertion. Let \(g(k)=2(n-2)(\eta_0-\frac{n-k-1}{2})=- 2k^2 + 3kn - 4k - n^2 + 3n - 2\), which has an root, \(\frac{n-2}{2}\) , in the interval \([1, n-3]\). Thus we get \(g(k)\leq \frac{n-k-1}{2}\) if \(k\in [1, \frac{n-2}{2}]\) and \(g(k)\geq \frac{n-k-1}{2}\) if \(k\in [\frac{n-2}{2}, n-3]\), implying the correction of Fact 1.

It is routine to check that \begin{equation*} \begin{cases} &\eta(\eta_0)=\frac{2k(k - n + 1)^3}{(n - 2)^2} (2k^2 + ( - 3n+ 6)k + n^2 - 4n + 4)\\[3mm] &\eta(\frac{n-k-1}{2})=\frac{(k - n + 1)^3(2k - n + 2)}{4}, \end{cases} \end{equation*} and we also can obtain two auxiliary properties for the function \(\eta(x):\)

Fact 2. \(\eta(\eta_0)\leq 0\) if \(k\in [1, \frac{n-2}{2}]\) and \(\eta(\eta_0)\geq 0\) if \(k\in [ \frac{n-2}{2}, n-3]\).

In fact, let \(g_1(k)=2k^2+(-3n+6)k+n^2-4n+4\). It is routine to check that \(g_1(k)\) has an root, \(\frac{n-2}{2}\), in the interval \([1, n-3]\), implying \(g_1(k)\leq 0\) if \(k\in [1, \frac{n-2}{2}]\) and \(g_1(k)\geq 0\) if \(k\in [ \frac{n-2}{2}, n-3]\). This completes the proof of Fact 2.

Fact 3. \(\eta(\frac{n-k-1}{2})\geq 0\) if \(k\in [1, \frac{n-2}{2}]\) and \(\eta(\frac{n-k-1}{2})\leq 0\) if \(k\in [ \frac{n-2}{2}, n-3]\).

In fact, we use \(g_2(k)\) to denote the right-side of \(\eta(\frac{n-k-1}{2})\). It is routine to check that \(g_2(k)\) has an root, \(\frac{n-2}{2}\), in the interval \([1, n-3]\). As desired.

In what follows, we will confirm that \(\mathcal{A}_1'(x)< 0\) in the whole interval \([1, \frac{n-k-1}{2}]\). It is sufficient to show the following three claims.

Claim 1. \(\mathcal{A}_1'(x)< 0\) for \(k \in [1,\frac{n-2}{2}]\) and \(x\in [1,\eta_0]\) .

Direct calculations that

\begin{equation*} \mathcal{A}_1'(\eta_0)=\frac{r_2(k)}{k(n - 1)(k - n + 1)^2(k - n + 2)^2}, \end{equation*} where \begin{equation*} \begin{split} r_2(k)&=k^5 + ( - 4n+6)k^4 + (6n^2 - 18n + 13)k^3 + (- 4n^3 + 18n^2 - 26n + 12)k^2\\ &\;\;\;+ (2n^4 - 13n^3 + 31n^2 - 32n + 12)k - n^5 + 9n^4 - 32n^3 + 56n^2 - 48n + 16. \end{split} \end{equation*} Note that the denominator of \(\mathcal{A}_1'(\eta_0)\) is non-negative, and the third derivative \(r_2^{(3)}(k)=60k^2+(-96n+ 144)k+36n^2-108n+78\) is a convex function in the interval \([1, \frac{n-2}{2}]\). Hence, \(r_2^{(3)}(k)\geq \min\{r_2^{(3)}(1), r_2^{(3)}(\frac{n-2}{2})\}=\min\{36n^2 - 204n + 282, 3n^2 - 6\}>0\), implying that \(r_2'(k)\) is a convex function. Similarly, we have \(r_2'(k)\geq \min\{r_2'(1),r_2'(\frac{n-2}{2})\}=\min\{2n^4-21n^3+85n^2-154n+104, \frac{(n-2)^2(13n^2-44n+32)}{16}\}>0\), which shows that \(r_2(k)\) is monotonously increasing in the accordingly interval. It is routine to check that \(r_{2}(k)\leq r_2(\frac{n-2}{2})=\frac{-(n - 2)^3(15n^2 - 48n + 32)}{32}< 0\), as desired we prove that \(\mathcal{A}_1'(\eta_0)< 0\).

It follows from Fact 1 that \(1\leq \eta_0 \leq \frac{n-k-1}{2}\), implying that \(\eta''(x)=(12n - 24)x + 12k^2 + (12 - 12n)k\leq 0 \). Hence, \(\eta'(x)\) is a decreasing function in the interval \([1, \eta_0]\). Consequently,

\begin{equation*} \eta'(x)\geq \eta'(\eta_0)=\frac{-6k(k - n + 1)^2(k - n + 2)}{n - 2}>0. \end{equation*} Hence, \(\eta(x)\) is monotonously increasing in the accordingly interval.

To accomplish the proof of Claim 1, it remains to prove that \(\mathcal{A}_1''(x)>0\), which is equivalent to that fact \(\eta(x)< 0.\) It follows from Fact 2, together with \(\eta(x)\) is increasing, that \(\eta(x)\leq \eta(\eta_0)< 0\). This implies that \(\mathcal{A}_1'(x)\) is an increasing function in the interval \([1, \eta_0]\). It then yields that \(\mathcal{A}_1'(x)\leq \mathcal{A}_1'(\eta_0)< 0,\) which completes the proof of Claim 1.

Hence, \(ID(G)\geq \mathcal{A}_1(x)\geq \mathcal{A}_1(\eta_0)\).

Claim 2. \(\mathcal{A}_1'(x)< 0\) for \(k \in [1,\frac{n-2}{2}]\) and \(x\in [\eta_0, \frac{n-k-1}{2}]\) .

We begin with such an optimization problem:

\begin{align*} \max \quad & \mathcal{A}_1'(x, k, n)\\ \mbox{s.t.}\quad &\eta_0\leq x\leq \frac{n-k-1}{2}\\[3mm] &1\leq k \leq \frac{n-2}{2}\\[3mm] &n\geq 8. \end{align*} Throughout this paper, we always assume that the order \(n\) of the graph does not exceed \(10^{10}\). It follows that the global optimal solution of \(\mathcal{A}_1'(x, k, n)\) is \(x=2, k=1, n=8\) through Lingo software after iterating 209 times, and the corresponding optimal value is \(-0.4196429\). This implies that \(\mathcal{A}_1'(x)< 0\).

It yields from Claim 2 that \(\mathcal{A}_1(x)\) is decreasing in the interval \([\eta_0, \frac{n-k-1}{2}]\). Therefore, \(ID(G)\geq \mathcal{A}_1(\frac{n-k-1}{2})\).

Claim 3. \(\mathcal{A}_1'(x)< 0\) for \(k \in [\frac{n-2}{2},n-3]\) and \(x\in [1, \frac{n-k-1}{2}]\).

It directly follows from Fact 1 that \(\eta''(x)\leq 0\), which implies that \(\eta'(x)\) is a decreasing function in the interval \(x\in [1, \frac{n-k-1}{2}]\). Hence, \(\eta'(x)\geq \eta'(\frac{n-k-1}{2})=\frac{3(n - 2)(k - n + 1)^2}{2}>0\), implying that \(\eta(x)\) is monotonously increasing in the accordingly interval. It follows from Fact 3 that \(\eta(x)\leq\eta(\frac{n-k-1}{2})\leq 0\), and therefore we have \(\mathcal{A}_1''(x)>0\). Hence, \(\mathcal{A}_1'(x)\) is an increasing function in \([1,\frac{n-k-1}{2}]\).

Direct calculations show that

\begin{equation*} \mathcal{A}_1'(\frac{n-k-1}{2})=\frac{r_3(k)}{(n - 1)(k - n + 1)^2}, \end{equation*} where \(r_3(k)=k^2 + (2 - 2n)k - 3n^2 + 10n - 7.\) It is obvious to find that \(r_3(k)\) is a convex function in the interval \([\frac{n-2}{2},n-3]\). Note that \(r_3(\frac{n-2}{2})=-\frac{15n^2}{4}+12n-8< 0\) and \(r_3(k)=-4n^2+12n-4< 0\), we get \(\mathcal{A}_1'(x)\leq\mathcal{A}_1'(\frac{n-k-1}{2})< 0\). Thus, we have \(ID(G)\geq \mathcal{A}_1(x)\geq \mathcal{A}_1(\frac{n-k-1}{2})\).

Combining Claims 1, 2 and 3, we get \(\mathcal{A}_1(x)\) is decreasing in the whole interval \([1, \frac{n-k-1}{2}]\), which achieves its minimum value at the right end-point of this interval.

Recall that \(x\) is an integer, we need consider the following two cases:

Case 1. \(n-k-1\) is even.

It immediately yields that \(\mathcal{A}_1(x)\geq \mathcal{A}_1(\frac{n-k-1}{2})\), and therefrore

\begin{equation*} \begin{aligned} ID(G) &\geq \frac{- k^2 - 3n^2 + 2n + 1}{2(n - 1)(k - n + 1)}\doteq \widehat{Q}_{1}(n,k), \end{aligned} \end{equation*} contradicting the hypothesis. Hence, the conclusion follows.

Furthermore, the condition in Theorem 1 cannot be dropped. If \(G\cong K_{\frac{n-k-1}{2}}+(K_1\cup \overline{K_{\frac{n+k-1}{2}}})\), then direct computations yields that \(ID(G)=\widehat{Q}_{1}(n,k)\). Conversely, let \(ID(G)=\widehat{Q}_{1}(n,k)\), then all inequalities in the proof should be equalities. Hence, \(i=\frac{n-k-1}{2}\) and therefore \(d_1=\cdots=d_{\frac{n+k-1}{2}}=\frac{n-k-1}{2}\), \(d_{\frac{n+k+1}{2}}=\frac{n-k-1}{2}\) and \(d_{\frac{n+k+3}{2}}=\cdots=d_n=n-1\). This implies that \(G\cong K_{\frac{n-k-1}{2}}+(K_1\cup \overline{K_{\frac{n+k-1}{2}}})\).

Case 2. \(n-k-1\) is odd.

According to previous analysis, we have \(\mathcal{A}_1(x)\geq \mathcal{A}_1(\frac{n-k-2}{2})\). It follows by simple computations that

\begin{equation*} \begin{aligned} ID(G) &\geq \frac{- k^3 + (n - 2)k^2 + (- 3n^2 + 4n)k + 3n^3 - 2n^2 - 16n + 16}{2(n - 1)(k^2 - 2kn + 2k + n^2 - 2n)}\doteq \widetilde{Q}_{1}(n,k), \end{aligned} \end{equation*} again a contradiction, and the conclusion follows.

Furthermore, the condition in Theorem 1 cannot be dropped. If \(G\cong K_{\frac{n-k-2}{2}}+(K_2\cup \overline{K_\frac{n+k-2}{2}})\), then direct computations yields that \(ID(G)=\widetilde{Q}_{1}(n,k)\). Conversely, let \(ID(G)=\widetilde{Q}_{1}(n,k)\), then all inequalities in the proof should be equalities. Hence, \(i=\frac{n-k-2}{2}\) and therefore \(d_1=\cdots=d_{\frac{n+k-2}{2}}=\frac{n-k-2}{2}\), \(d_{\frac{n+k}{2}}=d_{\frac{n+k+2}{2}}=\frac{n-k}{2}\) and \(d_{\frac{n+k+4}{2}}=\cdots=d_n=n-1\). This implies that \(G\cong K_{\frac{n-k-2}{2}}+(K_2\cup \overline{K_\frac{n+k-2}{2}})\).

4. \(k\)-edge-hamiltonian graphs

We begin by presenting an elementary result for \(k\)-edge-hamiltonian graphs.

Lemma 2. ([30]) Let \(\pi=(d_1\leq d_2\leq \cdots \leq d_n)\) be a degree sequence with \(0\leq k\leq n-3\). If \[d_{i-k}\leq i\Rightarrow d_{n-i}\geq n-i+k~\text{for}~k+1\leq i< \frac{n+k}{2},\] then \(\pi\) enforces \(k\)-edge-hamiltonian.

Let \(k_0, k_1, k_2\) be three non-negative real numbers in terms of \(n\):

\begin{equation*} \begin{split} \left\{ \begin{aligned} &k_0=\frac{- n^2+n + \sqrt{n(n^3 + 2n^2 - 15n + 16)}}{2n}\\ &k_1=\frac{n^2-4n+2-\sqrt{n^4-12n^3+32n^2-24n+4}}{2n}\\ &k_2=\frac{n^2-4n+2+\sqrt{n^4-12n^3+32n^2-24n+4}}{2n}. \end{aligned} \right. \end{split} \end{equation*} The main result is the following:

Theorem 2. Let \(G\) be a connected graph of order \(n\geq 9\) and \(0\leq k\leq n-3\). If \(ID(G)< Q_{2}(n,k) \) , where \begin{equation*} Q_{2}(n, k)= \begin{cases} \frac{- k^2+(n^2 - 2n - 1)k + 2n^2 - 5n + 2}{(k + 1)(n^2 - 3n + 2)}&\text{if}~k\in[k_1, k_2], n+k-1=2p\\[3mm] \frac{- k^2+(n^2 - 2n - 1)k + 2n^2 - 5n + 2}{(k + 1)(n^2 - 3n + 2)}&\text{if}~k\in[k_0, n-4], n+k-1=2p+1\\[3mm] \frac{k^3 + (n - 2)k^2 + (3n^2 - 4n)k + 3n^3 - 2n^2 - 16n + 16}{2(n - 1)(k^2 + 2kn - 2k + n^2 - 2n)}&\text{if}~k\in[0, k_0], n+k-1=2p+1\\[3mm] \frac{k^2+3n^2-2n-1}{2(n-1)(k+n-1)}&\text{if}~k\in[0, k_1]\cup [k_2, n-3], n+k-1=2p, \end{cases} \end{equation*} then \(G\) is \(k\)-edge-hamiltonian. Moreover, \(ID(G)=Q_{2}(n,k)\) if and only if \(G\cong K_{k+1}+(K_1 \cup K_{n-k-2} )\) if \(k\in[k_1, k_2]\) and \(n+k-1\) is even or \(k\in[k_0, n-4]\) and \(n+k-1\) is odd; \(G\cong K_{\frac{n+k-2}{2}}+(K_2 \cup \overline{K_\frac{n-k-2}{2}} )\) if \(k\in[0, k_0]\) and \(n+k-1\) is odd; and \(G\cong K_{\frac{n+k-1}{2}}+\overline{K_\frac{n-k+1}{2}}\) if \(k\in[0, k_1]\cup [k_2, n-3]\) and \(n+k-1\) is even.

Proof. Suppose that \(G\) is not \(k\)-edge-hamiltonian. By Lemma 2, we know that there exists integer \(i\) such that \(d_{i-k}\leq i\) and \(d_{n-i}\leq n-i+k-1\) for \(k+1\leq i\leq \frac{n+k-1}{2}\). Then we have \begin{equation*} \begin{split} ID(G)&=\sum_{i=1}^{n}\frac{1}{d_i}\\ &\geq \frac{i-k}{i}+\frac{n-2i+k}{n-i+k-1}+\frac{i}{n-1}. \end{split} \end{equation*} For simplicity, we define the following function on \([k+1, \frac{n+k-1}{2}]\): \begin{equation*} \begin{split} \mathcal{A}_2(x)=\frac{x-k}{x}+\frac{n-2x+k}{n-x+k-1}+\frac{x}{n-1}, \end{split} \end{equation*} and the corresponding second derivative is \begin{equation*} \begin{split} \mathcal{A}_2''(x)=\frac{\zeta(x)}{x^3(x - k - n + 1)^3}, \end{split} \end{equation*} where \begin{equation*} \begin{split} \zeta(x)=(2n - 4)x^3 + 6k(k + n - 1)x^2 - 6k(k + n - 1)^2x + 2k(k + n - 1)^3. \end{split} \end{equation*} Let \(z=k+n-1\), then \(\zeta(x)=(2n-4)x^3+2kz(3x^2-3zx+z^2)\), and consequently we have \(\zeta(x)\geq (2n-4)x^3+2kz(2\sqrt{3}-3)xz>0\). Hence, \(\mathcal{A}_2(x)\) is a concave function, since \(x^3(x - k - n + 1)^3< 0\) for \([k+1, \frac{n+k-1}{2}].\)

To accomplish the proof, in what follows we need consider whether \(n+k-1\) is odd or even.

Case 1. \(n+k-1\) is odd.

In this case, it is not difficult to find that \(k+1\leq x\leq \frac{n+k-2}{2}\) and \(0\leq k \leq n-4\). Hence, \(\mathcal{A}_2(x)\geq \min\{\mathcal{A}_2(k+1), \mathcal{A}_2(\frac{n+k-2}{2})\}\). Direct calculations yields that

\begin{equation*} \begin{cases} \mathcal{A}_2(k+1)=\frac{- k^2+(n^2 - 2n - 1)k + 2n^2 - 5n + 2}{(k + 1)(n^2 - 3n + 2)}\\[3mm] \mathcal{A}_2(\frac{n+k-2}{2})=\frac{k^3 + (n - 2)k^2 + (3n^2 - 4n)k + 3n^3 - 2n^2 - 16n + 16}{2(n - 1)(k^2 + 2kn - 2k + n^2 - 2n)}, \end{cases} \end{equation*} and consequently we get \begin{equation*} \begin{split} \mathcal{A}_2(k+1)-\mathcal{A}_2\left(\frac{n+k-2}{2}\right)&=\frac{\sigma(k)} {2(k + 1)(n^2 - 3n + 2)(k^2 + 2kn - 2k + n^2 - 2n)}, \end{split} \end{equation*} where \begin{equation*} \begin{split} \sigma(k)=&-nk^4 + (n^2 - 5n)k^3 + (n^3 - n^2 - 6n + 4)k^2\\ +& (- n^4 + 5n^3 - 24n + 24)k + n^4 - 10n^3 + 36n^2 - 56n + 32. \end{split} \end{equation*} It is routine to check that \(\sigma(k)\) has two distinct roots in the interval \([0, n-4]\), say \(k_0\) and \(k_0'\) respectively. Formally \begin{equation*} \begin{cases} k_0=\frac{- n^2+n + \sqrt{n(n^3 + 2n^2 - 15n + 16)}}{2n}\\[3mm] k_0'=n-4. \end{cases} \end{equation*} In the following, we shall confirm that \(0< k_0< n-5\). In fact, the left-side of the inequality always holds under our initial conditions. It is sufficient to verify the last part. Simple calculations show that \begin{equation*} \begin{split} 2n(k_0-(n-5))=- 3n^2+11n + \sqrt{n^4 + 2n^3 - 15n^2 + 16n} , \end{split} \end{equation*} which is non-positive since \(\left(\sqrt{n^4 + 2n^3 - 15n^2 + 16n}\right)^{2}-(3n^2 -11n)^2=- 8n^4 + 68n^3 - 136n^2 + 16n< 0\), as desired.

It then follows from direct calculations that

\begin{equation*} \begin{cases} \sigma(0)=n^4 - 10n^3 + 36n^2 - 56n + 32>0\\[3mm] \sigma(n-5)=- 6n^3 + 51n^2 - 102n + 12< 0. \end{cases} \end{equation*} Applying Rolle's Theorem for the function \(\sigma(k)\), we obtain that \(\sigma(k)\geq 0\) if \(k\in [0, k_0]\), and \(\sigma(k)\leq 0\) if \(k\in [k_0, n-4].\)

To continue to the proof, we need consider the following possibilities.

Case 1.1. \(k\in [0, k_0]\).

Considering that \(\sigma(k)\geq 0\) and applying the hypothesis, we obtain \(\mathcal{A}_2\left(\frac{n+k-2}{2}\right)\leq \mathcal{A}_2(k+1)\). It immediately yields that

\begin{equation*} \begin{split} ID(G)&\geq \mathcal{A}_2\left(\frac{n+k-2}{2}\right)\\ &=\frac{k^3 + (n - 2)k^2 + (3n^2 - 4n)k + 3n^3 - 2n^2 - 16n + 16}{2(n - 1)(k^2 + 2kn - 2k + n^2 - 2n)}\doteq \widetilde{Q}_{2}(n,k). \end{split} \end{equation*} Thus we obtain a contradiction, completing the proof.

Furthermore, the corresponding condition in Theorem 2 cannot be dropped. If \(G\cong K_{\frac{n+k-2}{2}}+(K_2 \cup \overline{K_\frac{n-k-2}{2}}) \), then directly computations yields that \(ID(G)=\widetilde{Q}_{2}(n,k)\). Conversely, let \(ID(G)=\widetilde{Q}_{2}(n,k)\), then all inequalities in the proof should be equalities. Hence, \(i=\frac{n+k-2}{2}\) and therefore \(d_1=\cdots=d_{\frac{n-k-2}{2}}=\frac{n+k-2}{2}\), \(d_{\frac{n-k}{2}}=d_{\frac{n-k+2}{2}}=\frac{n+k}{2}\) and \(d_{\frac{n-k+4}{2}}=\cdots=d_n=n-1\). This implies that \(G\cong K_{\frac{n+k-2}{2}}+(K_2 \cup \overline{K_\frac{n-k-2}{2}})\).

Case 1.2. \(k\in [k_0, n-4]\).

Note that \(\sigma(k)\leq0\), which implies that \(\mathcal{A}_2\left(\frac{n+k-2}{2}\right)\geq\mathcal{A}_2(k+1)\). It immediately yields that

\begin{equation*} \begin{split} ID(G)&\geq \mathcal{A}_2(k+1)\\ &=\frac{- k^2+(n^2 - 2n - 1)k + 2n^2 - 5n + 2}{(k + 1)(n^2 - 3n + 2)}\doteq \widehat{Q}_{2}(n,k), \end{split} \end{equation*} again a contradiction. Hence, \(G\) is \(k\)-edge-hamiltonian.

Furthermore, the corresponding condition in Theorem 2 cannot be dropped. If \(G\cong K_{k+1}+(K_1 \cup K_{n-k-2} )\), then directly computations yields that \(ID(G)=\widehat{Q}_{2}(n,k)\). Conversely, let \(ID(G)=\widehat{Q}_{2}(n,k)\), then all inequalities in the proof should be equalities. Hence, \(i=k+1\) and therefore \(d_1=k+1\), \(d_{2}=\cdots=d_{n-k-1}=n-2\) and \(d_{n-k}=\cdots=d_n=n-1\). This implies that \(G\cong K_{k+1}+(K_1 \cup K_{n-k-2} )\).

Case 2. \(n+k-1\) is even.

In this case, it is routine to check that \(1\leq x\leq\frac{n+k-1}{2}\) and \(k\in [0, n-3]\). Hence, \(\mathcal{A}_2(x)\geq \min\{\mathcal{A}_2(1), \mathcal{A}_2(\frac{n+k-1}{2})\}\). Direct calculations yields that

\begin{equation*} \mathcal{A}_2\left(\frac{n+k-1}{2}\right)=\frac{k^2 + 3n^2 - 2n - 1}{2(n - 1)(k + n - 1)}, \end{equation*} and consequently we have \begin{equation*} \begin{split} \mathcal{A}_2(k+1)-\mathcal{A}_2\left(\frac{n+k-1}{2}\right) =\frac{\varsigma(k)}{2(k + 1)(k + n - 1)(n^2 - 3n + 2)}, \end{split} \end{equation*} where \(\varsigma(k)=-nk^3 + (2n^2 - 7n + 2)k^2 + (- n^3 + 6n^2 - 11n + 4)k + n^3 - 6n^2 + 11n - 6\). It is routine to check that \(\varsigma(k)\) has three distinct roots, says \(k_1, k_2\) and \(k_3\), in the interval \([0, n-3]\). Formally \begin{equation*} \begin{cases} k_1=\frac{n^2 - 4n + 2 -\Delta}{2n}\\[3mm] k_2=\frac{n^2 - 4n + 2 +\Delta}{2n}\\[3mm] k_3=n-3, \end{cases} \end{equation*} where \(\Delta=\sqrt{n^4 - 12n^3 + 32n^2 - 24n + 4}\). It is not difficult to verify that \(0< k_1< k_2< n-4\), and \begin{equation*} \begin{cases} \varsigma(0)=n^3 - 6n^2 + 11n - 6>0\\[3mm] \varsigma\left(\frac{k_1+k_2}{2}\right)=\frac{- n^6 + 14n^5 - 54n^4 + 64n^3 + 12n^2 - 40n + 8}{8n^2}< 0\\[3mm] \varsigma(n-4)=n^2 - 5n + 10>0. \end{cases} \end{equation*} Again applying Rolle's Theorem for the function \(\varsigma(k)\), we obtain that \(\varsigma(k)\geq 0\) if \(k\in [0, k_1] \cup [k_2, n-3]\), and \(\varsigma(k)\leq 0\) if \(k\in[k_1, k_2].\)

To continue to the proof, we need consider the following possibilities.

Case 2.1. \(k\in [0, k_1] \cup [k_2, n-3]\).

Recall that \(\varsigma(k)\geq0\), then we have \(\mathcal{A}_2(k+1)-\mathcal{A}_2\left(\frac{n+k-1}{2}\right)\geq 0\). It yields that

\begin{equation*} \begin{split} ID(G)\geq \mathcal{A}_2\left(\frac{n+k-1}{2}\right)=\frac{k^2 + 3n^2 - 2n - 1}{2(n - 1)(k + n - 1)}\doteq \widehat{\widehat{Q}}_{2}(n,k), \end{split} \end{equation*} which contradicts with our assumption. Hence, \(G\) is \(k\)-edge-hamiltonian.

Furthermore, the corresponding condition in Theorem 2 cannot be dropped. If \(G\cong K_{\frac{n+k-1}{2}}+ \overline{K_\frac{n-k+1}{2}} \), then direct computations yields that \(ID(G)=\widehat{\widehat{Q}}_{2}(n,k)\). Conversely, let \(ID(G)=\widehat{\widehat{Q}}_{2}(n,k)\), then all inequalities in the proof should be equalities. Hence, \(i=\frac{n+k-1}{2}\) and therefore \(d_1=\cdots=d_{\frac{n-k-1}{2}}=\frac{n+k-1}{2}\), \(d_{\frac{n-k+1}{2}}=\frac{n+k-1}{2}\) and \(d_{\frac{n-k+3}{2}}=\cdots=d_n=n-1\). This implies that \(G\cong K_{\frac{n+k-1}{2}}+\overline{K_\frac{n-k+1}{2}} \).

Case 2.2. \(k\in[k_1,k_2]\).

Recall that \(\varsigma(k)\leq0\), then we have \(\mathcal{A}_2(k+1)-\mathcal{A}_2\left(\frac{n+k-1}{2}\right)\leq 0\). It immediately yields that

\begin{equation*} \begin{split} ID(G)\geq \mathcal{A}_2(k+1)=\frac{- k^2+(n^2 - 2n - 1)k + 2n^2 - 5n + 2}{(k + 1)(n^2 - 3n + 2)}\doteq \widetilde{\widetilde{Q}}_{2}(n,k), \end{split} \end{equation*} contradicting the hypothesis. The assertion is proved.

Furthermore, the corresponding condition in Theorem 2 cannot be dropped. If \(K_{k+1}+(K_1 \cup K_{n-k-2} )\), then simple calculations yield that \(ID(G)=\widetilde{\widetilde{Q}}_{2}(n,k)\). Conversely, let \(ID(G)=\widetilde{\widetilde{Q}}_{2}(n,k)\), then all inequalities in the proof should be equalities. Hence, \(i=k+1\) and therefore \(d_1=k+1\), \(d_{2}=\cdots=d_{n-k-1}=n-2\) and \(d_{n-k}=\cdots=d_n=n-1\). This implies that \(K_{k+1}+(K_1 \cup K_{n-k-2} )\).

5. Hamilton-connected graphs

Lemma 3.([31]) Let \(\pi=(d_1\leq d_2\leq \cdots \leq d_n)\) be a degree sequence with \(n\geq 3\). If \[d_{k-1}\leq k\Rightarrow d_{n-k}\geq n-k+1~\text{for}~2\leq k\leq \frac{n}{2},\] then \(\pi\) enforces Hamilton-connected.

Now we shall state the main result:

Theorem 3. Let \(G\) be a connected graph of order \(n.\) If \begin{equation*} \begin{split} ID(G)< \frac{k^3 + (2n - 3)k^2 + (2 - 2n^2)k + n^2 - n}{k(k - n)(n - 1)} \doteq Q_{3}(n,k), \end{split} \end{equation*} then \(G\) is Hamilton-connected. Moreover, \(ID(G)=Q_{3}(n,k)\) if and only if \(G\cong {K_{k}}+(\overline{K_{k-1}} \cup K_{n-2k+1})\).

Proof. Suppose that \(G\) is not Hamilton-connected. Accordingly to Lemma 3, there must exist an integer \(k\) such that \(d_{k-1}\leq k\) and \(d_{n-k}\leq n-k\) for \(2\leq k\leq \frac{n}{2}\). It then follows that \begin{equation*} \begin{split} ID(G)&\geq \frac{k-1}{k}+\frac{n-2k+1}{n-k}+\frac{k}{n-1}\\ &= \frac{k^3 + (2n - 3)k^2 + (2 - 2n^2)k + n^2 - n}{k(k - n)(n - 1)}, \end{split} \end{equation*} which contradicts to our initial assumption. Hence the result follows.

Furthermore, the condition in Theorem 3 cannot be dropped. If \(G\cong {K_{k}}+(\overline{K_{k-1}} \cup K_{n-2k+1})\), then one can easily see that \(ID(G)=Q_{3}(n,k)\). Conversely, let \(ID(G)=\widehat{Q}_{3}(n,k)\), then all inequalities in the proof should be equalities. Therefore, \(d_1=\cdots=d_{k-1}=k\), \(d_{k}=\cdots=d_{n-k}=n-k\) and \(d_{n-k+1}=\cdots=d_n=n-1\). Hence, \(G\cong {K_{k}}+(\overline{K_{k-1}} \cup K_{n-2k+1})\).

6. Traceable graphs

Lemma 4.([1]) Let \(G\) be a nontrivial graph of order \(n\geq 4\), with degree sequence \(\pi=(d_1\leq d_2\leq \cdots \leq d_n)\). Suppose that there is no integer \(k< \frac{n+1}{2}\) such that \(d_k \leq k-1\) and \(d_{n-k+1}\leq n-k-1 \). Then \(G\) is traceable.

Now we shall state the main result:

Theorem 4. Let \(G\) be a connected graph of order \(n.\) If \begin{equation*} \begin{split} ID(G)< \frac{k^3 + (2n - 4)k^2 + (- 2n^2 + 2n + 1)k + n^2 - n}{(k - 1)(n - 1)(k - n + 1)} \doteq Q_{4}(n,k), \end{split} \end{equation*} then \(G\) is traceable. Moreover, \(ID(G)=Q_{4}(n,k)\) if and only if \(G\cong {K_{k-1}}+(\overline{K_{k}} \cup K_{n-2k+1})\).

Proof. Suppose that \(G\) is not traceable. Then it follows from Lemma 4 that \(d_{k}\leq k-1\) and \(d_{n-k+1}\leq n-k-1\). Hence, from the definition of the inverse degree, we have \begin{equation*} \begin{split} ID(G)&\geq \frac{k}{k-1}+\frac{n-2k+1}{n-k-1}+\frac{k-1}{n-1}\\ &= \frac{k^3 + (2n - 4)k^2 + (- 2n^2 + 2n + 1)k + n^2 - n}{(k - 1)(n - 1)(k - n + 1)} \end{split} \end{equation*} which is a contradiction. This completes the proof.

Furthermore, the condition in Theorem 4 cannot be dropped. If \(G\cong {K_{k-1}}+(\overline{K_{k}} \cup K_{n-2k+1})\), then one can easily see that \(ID(G)=Q_{4}(n,k)\). Conversely, let \(ID(G)=\widehat{Q}_{4}(n,k)\), then all inequalities in the proof should be equalities. Hence, therefore \(d_1=\cdots=d_{k}=k-1\), \(d_{k+1}=\cdots=d_{n-k+1}=n-k-1\) and \(d_{n-k+2}=\cdots=d_n=n-1\). Hence, \(G\cong {K_{k-1}}+(\overline{K_{k}} \cup K_{n-2k+1})\).

7. \(k^{-}\)-independent graphs

More recently, An et al., [27] considered the property of \(k^{-}\)-independent graphs by using the first Zagreb index for a graph to be \(k^{-}\)-independent. In this section, we continue this program to explore sufficient conditions for a graph to be \(k^{-}\)-independent in terms of the inverse degree.

The following result is due to a survey by Bauer et al., [32].

Lemma 5. ([32]) Let \(\pi=(d_1\leq d_2\leq \cdots \leq d_n)\) be a graphical sequence and \(k\geq 1\). If \(d_{k+1}\geq n-k\), then \(\pi\) enforces \(k^{-}\)-independent.

We conclude this paper with the following structural result.

Theorem 5. Let \(G\) be a connected graph of order \(n.\) If \begin{equation*} \begin{split} ID(G)< \frac{- k^2 + kn - k - n^2 + n}{(n - 1)(k - n + 1)} \doteq Q_{5}(n,k), \end{split} \end{equation*} then \(G\) is \(k^{-}\)-independent. Moreover, \(F(G)=Q_{5}(n,k)\) if and only if \(G\cong \overline{K_{k+1}}+K_{n-k-1}\).

Proof. Suppose that \(G\) is not \(k^{-}\)-independent. Then it follows from Lemma 5 that \(d_{k+1}\leq n-k-1\). From the definition of the inverse degree, we have \begin{equation*} \begin{split} ID(G)&\geq \frac{k+1}{n-k-1}+\frac{n-k-1}{n-1}\\ &= \frac{- k^2 + kn - k - n^2 + n}{(n - 1)(k - n + 1)} \end{split} \end{equation*} which is a contradiction. Hence the result follows.

Furthermore, the condition in Theorem 5 cannot be dropped. If \(G\cong \overline{K_{k+1}}+K_{n-k-1}\), then one can easily see that \(ID(G)=Q_{5}(n,k)\). Conversely, let \(ID(G)=\widehat{Q}_{5}(n,k)\), then all inequalities in the proof should be equalities. Hence, therefore \(d_1=\cdots=d_{k+1}=n-k-1\), and \(d_{k+2}=\cdots=d_n=n-1\). Hence, \(G\cong \overline{K_{k+1}}+K_{n-k-1}\).

Acknowledgments

This research was supported by the Defense Industrial Technology Development Program (JCKY2018205C003) and National Key Research and Development Project (2019YEB2006602).

Author Contributions

All authors contributed equally to the writing of this paper. All authors read and approved the final manuscript.

Conflict of Interests

The authors declare no conflict of interest.