The Narumi-Katayama index of a graph is defined as the product of the degrees of all vertices in the graph. In this paper, we obtain upper bounds of the Narumi-Katayama index of a connected graph. We further present sufficient conditions based on the Narumi-Katayama index and other graph invariants for Hamiltonian and traceable graphs.
We consider only finite undirected graphs without loops or multiple edges. Notation and terminology not defined here follow those in [1]. For a graph \(G = (V(G), E(G))\), we use \(n\) and \(e\) to denote its order \(|V(G)|\) and size \(|E(G)|\), respectively. We use \(G^{c}\) to denote the complement of a graph \(G\). The minimum degree and maximum degree of \(G\) are denoted by \(\delta(G)\) and \(\Delta(G)\), respectively. The neighborhood of a vertex \(u\) in \(G\), denoted \(N_G(u)\), is defined as the set of all the vertices which are adjacent to \(u\) in \(G\). The average (arithmetic mean) of the degrees of the vertices adjacent to \(u\) is denoted by \(m(u)\). If a vertex \(u \in V – V_1\), where \(V_1\) is a subset of the vertex set \(V\), we define \(d_{G[V_1]}(u)\) as \(|N_G(u) \cap V_1|\), where \(G[V_1]\) is a subgraph of \(G\) which is induced by \(V_1\). A subset \(V_2\) of the vertex set \(V(G)\) of \(G\) is independent if no two vertices in \(V_2\) are adjacent in \(G\). A maximum independent set in a graph \(G\) is an independent set of largest possible size. The independence number, denoted \(\alpha(G)\), of a graph \(G\) is the cardinality of a maximum independent set in \(G\). For disjoint vertex subsets \(P\) and \(Q\) of \(V(G)\), We define \(E(P, Q)\) as \(\{\, e : e = pq \in E, p \in P, q \in Q \,\}\). For two disjoint graphs \(G_1\) and \(G_2\), we use \(G_1 \vee G_2\) to denote the join of \(G_1\) and \(G_2\). We use \(K_{r}\) to denote a complete graph of order \(r\). We also use \(K_{r, \, s}\) to denote a complete bipartite graph with two partition sets \(X\) and \(Y\) such that \(|X| = r\) and \(|Y| = s\). A graph \(G\) is called a (\(\delta\), \(\Delta\))-smeiregular bipartite graph if \(G\) is a bipartite graph such that the degrees of all vertices in one partition set are equal to \(\delta\) and the degrees of all vertices in another partition set are equal to \(\Delta\). Let \(A(G)\) be the adjacency matrix of \(G\). The spectral radius of \(G\), denoted \(\lambda_1(G)\), is defined as the largest eigenvalue of \(A(G)\). The Laplacian spectral radius of \(G\), denoted \(\mu_1(G)\), is defined as the largest eigenvalue of \(L(G) : = D(G) – A(G)\), where \(D(G)\) is a diagonal matrix whose entries are the degrees of vertices in \(G\). The signless Laplacian spectral radius of \(G\), denoted \(q_1(G)\), is defined as the largest eigenvalue of \(Q(G) : = D(G) + A(G)\), where \(D(G)\) is a diagonal matrix whose entries are the degrees of vertices in \(G\). A cycle \(C\) in a graph \(G\) is called a Hamiltonian cycle of \(G\) if \(C\) contains all the vertices of \(G\). A graph \(G\) is called Hamiltonian if \(G\) has a Hamiltonian cycle. A path \(P\) in a graph \(G\) is called a Hamiltonian path of \(G\) if \(P\) contains all the vertices of \(G\). A graph \(G\) is called traceable if \(G\) has a Hamiltonian path.
For a graph \(G\), Narumi and Katayama [11] introduced the “simple topological index” which was defined as the the product of the degrees of all vertices in \(G\). In the later works, researchers have used the ‘‘Narumi-Katayama index’’ for the “simple topological index”. See, for instance, [4]. We in this paper will also use the same terminology as the one in [4] and denote the Narumi-Katayama index of \(G\) by \(NK(G)\). It is noted that some results on the Narumi-Katayama index have been obtained. The readers are referred to References [3, 4, 6, 10, 11, 13, 14].
In this paper, we first establish upper bounds of the Narumi-Katayama index of a connected graph. Using the ideas of obtaining the upper bounds, we further present sufficient conditions based on the Narumi-Katayama index and other graph invariants such as the spectral radius, the Laplacian spectral radius, or the signless Laplacian spectral radius for Hamiltonian and traceable graphs. The main results are as follows.
Theorem 1.1. Let \(G\) be a connected graph of order \(n \geq 2\) vertices and \(e\) edges. Then
[1] \(NK(G) \leq (n – \alpha)^{\alpha} \Delta^{n – \alpha}\) with equality if and only if \(G\) is \(K_{\alpha}^{c} \vee H\), where \(H = G[V – I]\), \(I\) is a maximum independent set in \(G\) with \(|I| = \alpha\) such that \(d(y) = \delta = (n – \alpha)\) for each \(y \in I\) and \(d(z) = \Delta\) for each \(z \in V – I\).
[2] \(NK(G) \leq \left(\frac{e}{\alpha}\right)^{\alpha} \Delta^{n – \alpha}\) with equality if and only if \(G\) is a connected bipartite graph with partition sets of \(I\) and \(V – I\) such that \(|I| = \alpha\), \(d(y) = \delta\) for each \(y \in I\) and \(d(z) = \Delta\) for each \(z \in V – I\).
[3] \(NK(G) \leq \left(\lambda_1 \sqrt{\frac{n – \alpha}{\alpha}} \,\right)^{\alpha}\Delta^{n – \alpha}\) with equality if and only if \(G\) is a connected bipartite graph with partition sets of \(I\) and \(V – I\) such that \(|I| = \alpha\), \(d(y) = \delta\) for each \(y \in I\) and \(d(z) = \Delta\) for each \(z \in V – I\).
[4] \(NK(G) \leq \left(\frac{\mu_1 (n – \alpha)}{n}\right)^{\alpha} \Delta^{n – \alpha}\) with equality if and only if \(G\) is a connected graph with vertex subsets of \(I\) and \(V – I\) such that \(|I| = \alpha\), \(d(y) = \delta\) for each \(y \in I\), \(d(z) = \Delta\) for each \(z \in V – I\) and \(d_{G[I]}(w)\) is a constant for each vertex each \(w \in V – I\).
[5] \(NK(G) \leq \left(\frac{q_1 e (n – \alpha)}{\alpha n}\right)^{\frac{\alpha}{2}} \Delta^{n – \alpha}\) with equality if and only if \(G\) is a connected bipartite graph with partition sets of \(I\) and \(V – I\) such that \(|I| = \alpha\), \(d(y) = \delta\) for each \(y \in I\) and \(d(z) = \Delta\) for each \(z \in V – I\).
Theorem 1.2. Let \(G\) be a \(k\)-connected graph (\(k \geq 2\)) of order \(n \geq 3\) and size \(e\).
[1] If \(NK(G) \geq (n – k – 1)^{k + 1} \Delta^{n – k – 1}\), then \(G\) is Hamiltonian or \(G\) is \(K_{k + 1}^{c} \vee H\), where \(H = G[V – I]\) and \(|V(H)| = k\), \(I\) is an independent set in \(G\) with \(|I| = k + 1\) such that \(d(y) = \delta = (n – k – 1)\) for each \(y \in I\) and \(d(z) = \Delta\) for each \(z \in V – I\).
[2] If \(NK(G) \geq \left(\frac{e}{k + 1}\right)^{k + 1} \Delta^{n – k – 1}\), then \(G\) is Hamiltonian or \(G\) is \(K_{k, \, k + 1}\).
[3] If \(P(G) \geq \left(\lambda_1 \sqrt{\frac{n – k – 1}{k + 1}} \, \right)^{k + 1}\Delta^{n – k – 1}\), then \(G\) is Hamiltonian or \(G\) is \(K_{k, \, k + 1}\).
[4] If \(NK(G) \geq \left(\frac{\mu_1 (n – k – 1)}{n}\right)^{k + 1} \Delta^{n – k – 1}\), then \(G\) is Hamiltonian \(G\) is \(K_{k, \, k + 1}\).
[5] If \(NK(G) \geq \left(\frac{q_1 e (n – k – 1)}{(k + 1) n}\right)^{\frac{k + 1}{2}} \Delta^{n – k – 1}\), then \(G\) is Hamiltonian or \(G\) is \(K_{k, \, k + 1}\).
Theorem 1.3. Let \(G\) be a \(k\)-connected graph (\(k \geq 1\)) of order \(n \geq 9\) and size \(e\).
[1] If \(NK(G) \geq (n – k – 2)^{k + 2} \Delta^{n – k – 2}\), then \(G\) is traceable or \(G\) is \(K_{k + 2}^{c} \vee H\), where \(H = G[V – I]\) and \(|V(H)| = k\), \(I\) is an independent set in \(G\) with \(|I| = k + 2\) such that \(d(y) = \delta = (n – k – 2)\) for each \(y \in I\) and \(d(z) = \Delta\) for each \(z \in V – I\).
[2] If \(NK(G) \geq \left(\frac{e}{k + 2}\right)^{k + 2} \Delta^{n – k – 2}\), then \(G\) is traceable or \(G\) is \(K_{k, \, k + 2}\).
[3] If \(NK(G) \geq \left(\lambda_1 \sqrt{\frac{n – k – 2}{k + 2}} \, \right)^{k + 2}\Delta^{n – k – 2}\), then \(G\) is traceable or \(G\) is \(K_{k, \, k + 2}\).
[4] If \(NK(G) \geq \left(\frac{\mu_1 (n – k – 2)}{n}\right)^{k + 2} \Delta^{n – k – 2}\), then \(G\) is traceable or \(G\) is \(K_{k, \, k + 2}\).
[5] If \(NK(G) \geq \left(\frac{q_1 e (n – k – 2)}{(k + 2) n}\right)^{\frac{k + 2}{2}} \Delta^{n – k – 2}\), then \(G\) is traceable or \(G\) is \(K_{k, \, k + 2}\).
The following results will be used as lemmas when we prove our theorems. Lemma 2.1 below is the well-known AM-GM inequality. See, for example, Theorem 1.1 on Page \(27\) in [8].
Lemma 2.1. Let \(a_1\), \(a_2\), …, \(a_n\) be positive numbers. Then \[(a_1 a_2 \cdots a_n)^{\frac{1}{n}} \leq \frac{a_1 + a_2 + \cdots + a_n}{n},\] with equality if and only if \(a_1 = a_2 = \cdots = a_n\).
Applying Theorem \(3.2\) on Page \(304\) in [15] to the adjacency matrix of a graph \(G\), we have the following Lemma 2.2.
Lemma 2.2. Let \(G\) be a connected graph of order \(n\) with degree sequence \(d_1\), \(d_2\), …, \(d_n\). Then \[\lambda_1 \geq \sqrt{\frac{d_1^2 + d_2^2 + \cdots + d_n^2}{n}},\] with eqaulity if and only if \(G\) is a regular graph or \(G\) is a bipartite graph with partition sets of \(S\) and \(V – S\) such that \(d(y) = a\) for each \(y \in S\), where \(a\) is positive integer, and \(d(z) = b\) for each \(z \in V – S\), where \(b\) is a positive integer.
Lemma 2.3 below is Lemma 3 on Page \(392\) in [7].
Lemma 2.3. Let \(G = (V , E)\) be a connected graph of order \(n\) and \(G_1\) be an induced subgraph of \(G\) with \(n_1\) (\(n_1 < n\)) vertices and average degree \(r_1\) (i.e., \(r_1 = \sum\limits_{v \in V(G_1)} d_{G_1}(v)/n_1)\). Set \(d_1 = \sum\limits_{v \in V(G_1)}d(v)/n_1\). Then \[\mu_1(G) \geq \frac{n(d_1 – r_1)} {n – n_1}.\] Moreover, if the equality holds, then \(d_{G_2}(u) = s\) for all vertex \(u \in V(G_1)\) and \(d_{G_1}(v) = t\) for all vertex \(v \in V(G_2)\), where \(G_2 = G[V – V(G_1)]\).
Lemma 2.4. Let \(G\) be a connected graph. Then \(\mu_1 \leq \{\, d(u) + m(u) : u \in V \,\}\) with equality if and only if G is either a regular bipartite graph or a semiregular bipartite graph.
Lemma 2.5. Let \(G\) be a graph with at least one edge, then \[q_1 \geq \frac{\sum\limits_{v \in V} d^2(v)}{e}.\]
The next two results are from [2].
Lemma 2.6. Let \(G\) be a \(k\)-connected graph of order \(n \geq 3\). If \(\alpha \leq k\), then \(G\) is Hamiltonian.
Lemma 2.7. Let \(G\) be a \(k\)-connected graph of order \(n\). If \(\alpha \leq k + 1\), then \(G\) is traceable.
Lemma 2.8. Let \(G\) be a balanced bipartite graph of order \(2n\) with bipartition (\(A\), \(B\)). If \(d(x) + d(y) \geq n + 1\) for any \(x \in A\) and any \(y \in B\) with \(xy \not \in E\), then \(G\) is Hamiltonian.
Lemma \(9\) below is from [5].
Lemma 2.9. Let \(G\) be a \(2\)-connected bipartite graph with bipartition (\(A\), \(B\)), where \(|A| \geq |B|\). If each vertex in \(A\) has degree at least \(j\) and each vertex in \(B\) has degree at least \(i\), then \(G\) contains a cycle of length at least \(2 \min \{\, |B|, j + i – 1, 2j – 2\, \}\).
Proof of Theorem 1.1. Let \(I\) be an independent set in \(G\) with \(|I| = \alpha\). Clearly, \(1 \leq \alpha \leq n – 1\).
Proof of [1] in Theorem 1.1. Notice that \(d(y) \leq (n – \alpha)\) for each \(y \in I\). Then \[NK(G) = \prod_{x \in V} d(x) = \prod_{y \in I} d(y) \prod_{z \in V – I} d(z) \leq (n – \alpha)^{\alpha} \Delta^{n – \alpha}.\]
If \(NK(G) = (n – \alpha)^{\alpha} \Delta^{n – \alpha}\), we, from the above proofs, have that \(d(y) = (n – \alpha) = \delta\) for each \(y \in I\) and \(d(z) = \Delta\) for each \(z \in V – I\). Thus \(G\) is \(K_{\alpha}^{c} \vee H\), where \(H = G[V – I]\), \(I\) is a maximum independent set in \(G\) with \(|I| = \alpha\) such that \(d(y) = \delta = (n – \alpha)\) for each \(y \in I\) and \(d(z) = \Delta\) for each \(z \in V – I\).
If \(G\) is \(K_{\alpha}^{c} \vee H\), where \(H = G[V – I]\), \(I\) is a maximum independent set in \(G\) with \(|I| = \alpha\) such that \(d(u) = \delta = (n – \alpha)\) for each \(u \in I\) and \(d(v) = \Delta\) for each \(v \in V – I\), it is evident that \(NK(G) = (n – \alpha)^{\alpha} \Delta^{n – \alpha}\). \(\square\)
Proof of [2] in Theorem 1.1. Notice that \(\sum\limits_{y \in I} d(y) = |E(I, V – I)| \leq \sum\limits_{z \in V – I} d(z)\) and \(\sum\limits_{y \in I} d(y) + \sum\limits_{z \in V – I} d(z) = 2e\). We have that \[\sum\limits_{y \in I} d(y) \leq e \leq \sum\limits_{z \in V – I} d(z).\]
Applying Lemma 2.1 to the degrees of the vertices in \(I\), we have that \[\begin{aligned} NK(G) =&\prod_{x \in V} d(x) = \prod_{y \in I} d(y) \prod_{z \in V – I} d(z)\\ \leq& \left(\frac{\sum\limits_{y \in I} d(y)}{\alpha}\right)^{\alpha} \Delta^{n – \alpha} \leq \left(\frac{e}{\alpha}\right)^{\alpha} \Delta^{n – \alpha}. \end{aligned}\]
If \(NK(G) = \left(\frac{e}{\alpha}\right)^{\alpha} \Delta^{n – \alpha}\), then \[\begin{aligned} NK(G) =& \prod_{x \in V} d(x) = \prod_{y \in I} d(y) \prod_{z \in V – I} d(z)\\ =& \left(\frac{\sum\limits_{y \in I} d(y)}{\alpha}\right)^{\alpha} \Delta^{n – \alpha} = \left(\frac{e}{\alpha}\right)^{\alpha} \Delta^{n – \alpha}. \end{aligned}\]
Thus \(\prod_{y \in I} d(y) = \left(\frac{\sum\limits_{y \in I} d(y)}{\alpha}\right)^{\alpha}\), \(\prod_{z \in V – I} d(z) = \Delta^{n – \alpha}\), and \(\sum\limits_{y \in I} d(y) = e\). Therefore we, by Lemma 2.1, have that \(d(y) = \delta\) for each \(y \in I\) and \(d(z) = \Delta\) for each \(z \in V – I\). Since \(\sum\limits_{y \in I} d(y) = e\) and \(\sum\limits_{y \in I} d(y) + \sum\limits_{z \in V – I} d(z) = 2e\), we have that \(\sum\limits_{z \in V – I} d(z) = e\). Thus \(G\) is a bipartite graph. Therefore \(G\) is a connected bipartite graph with partition sets of \(I\) and \(V – I\) such that \(|I| = \alpha\), \(d(y) = \delta\) for each \(y \in I\), and \(d(z) = \Delta\) for each \(z \in V – I\).
If \(G\) is a connected bipartite graph with partition sets of \(I\) and \(V – I\) such that \(|I| = \alpha\), \(d(y) = \delta\) for each \(y \in I\), and \(d(z) = \Delta\) for each \(z \in V – I\). Then \(e = \alpha \delta\) and \[NK(G) = \prod_{x \in V} d(x) = \delta^{\alpha} \Delta^{n – \alpha} = \left(\frac{e}{\alpha}\right)^{\alpha} \Delta^{n – \alpha}.\] \(\square\)
Proof of [3] in Theorem 1.1. From Cauchy-Schwarz inequality, we have that \[\left(\sum\limits_{y \in I} 1*d(y)\right)^2 \leq \sum\limits_{y \in I} 1^2 \sum\limits_{y \in I} d^2(y).\]
Thus \[\sum\limits_{y \in I} d^2(y) \geq \frac{(\sum\limits_{y \in I} d(y))^2}{\alpha}.\]
Similarly, we have that \[\sum\limits_{z \in V- I} d^2(z) \geq \frac{(\sum\limits_{z \in V – I} d(z))^2}{n – \alpha}.\]
Notice that \(\sum\limits_{z \in v – I} d(z) \geq \sum\limits_{u \in I} d(y)\), we, by Lemma 2.2, have that \[\begin{aligned} \lambda_1 \geq& \sqrt{\frac{\sum\limits_{x \in V} d^2(x)}{n}}\\ =& \sqrt{\frac{\sum\limits_{y \in I} d^2(y) + \sum\limits_{z \in V – I} d^2(z)}{n}}\\ \geq& \sqrt{\frac{1}{n} \left( \frac{(\sum\limits_{y \in I} d(y))^2}{\alpha} + \frac{(\sum\limits_{z \in V – I} d(z))^2}{n – \alpha} \right) }\\ \geq& \sqrt{\frac{1}{n} \left( \frac{(\sum\limits_{y \in I} d(y))^2}{\alpha} + \frac{(\sum\limits_{y \in I} d(y))^2}{n – \alpha} \right) }\\ =& \sum\limits_{y \in I} d(y) \sqrt{\frac{1}{\alpha (n – \alpha)}}. \end{aligned}\]
Thus \[\sum\limits_{y \in I} d(y) \leq \lambda_1 \sqrt{\alpha (n – \alpha)}.\]
Applying Lemma 2.1 to the degrees of the vertices in \(I\), we have that \[\begin{aligned} NK(G) =& \prod_{x \in V} d(x) = \prod_{y \in I} d(y) \prod_{z \in V – I} d(z)\\ \leq& \left(\frac{\sum\limits_{y \in I} d(y)}{\alpha}\right)^{\alpha} \Delta^{n – \alpha}\\ \leq& \left(\frac{\lambda_1 \sqrt{\alpha (n – \alpha)}}{\alpha}\right)^{\alpha} \Delta^{n – \alpha}\\ =& \left(\lambda_1 \sqrt{\frac{n – \alpha}{\alpha}} \, \right)^{\alpha}\Delta^{n – \alpha}. \end{aligned}\]
If \(NK(G) = \left(\lambda_1 \sqrt{\frac{n – \alpha}{\alpha}} \, \right)^{\alpha}\Delta^{n – \alpha}\), We have that \[\begin{aligned} NK(G) =& \prod_{x \in V} d(x) = \prod_{y \in I} d(y) \prod_{z \in V – I} d(z)\\ =& \left(\frac{\sum\limits_{y \in I} d(y)}{\alpha}\right)^{\alpha} \Delta^{n – \alpha}\\ =& \left(\frac{\lambda_1 \sqrt{\alpha (n – \alpha)}}{\alpha}\right)^{\alpha} \Delta^{n – \alpha}\\ =& \left(\lambda_1 \sqrt{\frac{n – \alpha}{\alpha}} \, \right)^{\alpha}\Delta^{n – \alpha}. \end{aligned}\]
Thus \(\sum\limits_{y \in I} d(y) = \lambda_1 \sqrt{\alpha (n – \alpha)}\) and \(d(z) = \Delta\) for each \(z \in V – I\). Therefore \[\sum\limits_{y \in I} d^2(y) = \frac{\left(\sum\limits_{y \in I} d(y)\right)^2}{\alpha},\] and \(\sum\limits_{z \in V – I} d(z) = \sum\limits_{y \in I} d(y)\). From Lemma 2.1, we have that \(d(y) = \delta\) for each \(y \in I\). Since \(\sum\limits_{y \in I} d(y) + \sum\limits_{z \in V – I} d(z) = 2e\), we have that \(\sum\limits_{y \in I} d(y) = \sum\limits_{z \in V – I} d(z) = e\). Hence \(G\) is a bipartite graph. Therefore \(G\) is a connected bipartite graph with partition sets of \(I\) and \(V – I\) such that \(|I| = \alpha\), \(d(y) = \delta\) for each \(y \in I\), and \(d(z) = \Delta\) for each \(z \in V – I\).
If \(G\) is a connected bipartite graph with partition sets of \(I\) and \(V – I\) such that \(|I| = \alpha\), \(d(y) = \delta\) for each \(y \in I\), and \(d(z) = \Delta\) for each \(z \in V – I\). When \(\delta = \Delta\), then \(G\) is a regular graph with \(\alpha \delta = e = (n – \alpha) \Delta\). Therefore \(\alpha = (n – \alpha) = \frac{n}{2}\). From Lemma 2.2, we have that \(\lambda_1 = \delta\). Hence \[NK(G) = \left(\lambda_1 \sqrt{\frac{n – \alpha}{\alpha}} \, \right)^{\alpha}\Delta^{n – \alpha} = \delta^n \Delta^{n – \alpha}.\]
When \(\delta \neq \Delta\), we still have that \(\alpha \delta = e = (n – \alpha) \Delta\). We, from Lemma 2.2 again, further have that \[\lambda_1 = \sqrt{\frac{\alpha \delta^2 + (n – \alpha) \Delta^2}{n}} = \sqrt{\frac{\alpha \delta^2 + \alpha \delta \Delta}{n}} = \sqrt{\frac{\alpha \delta (\delta + \Delta)}{n}}.\]
Thus \[\begin{aligned} \lambda_1 \sqrt{\frac{n – \alpha}{\alpha}} =& \sqrt{\frac{\delta (\delta + \Delta) (n – \alpha)}{n}} \\ =& \sqrt{\frac{\delta ((n – \alpha) \delta + (n – \alpha) \Delta)}{n}}\\ =& \sqrt{\frac{\delta ((n – \alpha) \delta + \alpha \delta)}{n}} = \delta. \end{aligned}\]
Therefore \[NK(G) = \delta^{\alpha} \Delta^{n – \alpha} = \left(\lambda_1 \sqrt{\frac{n – \alpha}{\alpha}} \, \right)^{\alpha}\Delta^{n – \alpha}.\]
Remark 3.1. It was informed by the referee that \(\lambda_1(G) = \sqrt{\delta \, \Delta}\) if \(G\) is a connected (\(\delta\), \(\Delta\))-smeiregular bipartite graph. Obviously, combining this fact with \(\alpha \delta = e = (n – \alpha) \Delta\), we can shorten the above proofs. But the author couldn’t find references stating directly that fact.
\(\square\)
Proof of [4] in Theorem 1.1. Applying Lemma 2.3 with \(G_1 = G[I]\) and \(G_2 = G[V – I]\), we have that \[\mu_1 \geq \frac{n \sum\limits_{y \in I} d(y)}{\alpha (n – \alpha)}.\]
Thus \[\sum\limits_{y \in I} d(y) \leq \frac{\mu_1 \alpha (n – \alpha)}{n}.\]
Applying Lemma 2.1 to the degrees of the vertices in \(I\), we have that \[\begin{aligned} NK(G) &= \prod_{x \in V} d(x) = \prod_{y \in I} d(y) \prod_{z \in V – I} d(z) \\ &\leq \left(\frac{\sum\limits_{y \in I} d(y)}{\alpha}\right)^{\alpha} \Delta^{n – \alpha}\\ &\leq \left(\frac{\mu_1 (n – \alpha)}{n}\right)^{\alpha} \Delta^{n – \alpha}. \end{aligned}\]
If \(NK(G) = \left(\frac{\mu_1 (n – \alpha)}{n}\right)^{\alpha} \Delta^{n – \alpha}\), we, from the above proofs, Lemma 2.1, and Lemma 2.3, have that \(G\) is a connected graph with vertex subsets of \(I\) and \(V – I\) such that \(|I| = \alpha\), \(d(y) = \delta\) for each \(y \in I\), \(d(z) = \Delta\) for each \(z \in V – I\), and \(d_{G[I]}(w)\) is a constant for each vertex each \(w \in V – I\). \(\square\)
If \(G\) is a connected graph with vertex subsets of \(I\) and \(V – I\) such that \(|I| = \alpha\), \(d(y) = \delta\) for each \(y \in I\), \(d(z) = \Delta\) for each \(z \in V – I\), and \(d_{G[I]}(w)\) is a constant for each \(w \in V – I\), we, from Lemma 2.4, have that \(\mu_1 = \delta + \Delta\). Thus \[\begin{aligned} NK(G) &= \left(\frac{\mu_1 (n – \alpha)}{n}\right)^{\alpha} \Delta^{n – \alpha} \\ &= \left(\frac{(\delta + \Delta) (n – \alpha)}{n}\right)^{\alpha} \Delta^{n – \alpha}\\ &= \left(\frac{\delta (n – \alpha) + \Delta (n – \alpha)}{n}\right)^{\alpha} \Delta^{n – \alpha}\\ &= \left(\frac{\delta (n – \alpha) + \delta \alpha)}{n}\right)^{\alpha} \Delta^{n – \alpha}\\ &= \delta^{\alpha} \Delta^{n – \alpha}. \end{aligned}\] \(\square\)
Proof of [5] in Theorem 1.1. From Cauchy-Schwarz inequality, we again have that \[\sum\limits_{y \in I} d^2(y) \geq \frac{(\sum\limits_{y \in I} d(y))^2}{\alpha},\] \[\sum\limits_{z \in V – I} d^2(z) \geq \frac{(\sum\limits_{z \in v – I} d(z))^2}{n – \alpha}.\]
Notice that \(\sum\limits_{z \in V – I} d(z) \geq \sum\limits_{y \in I} d(y)\), we, by Lemma 2.5, have that \[\begin{aligned} q_1 &\geq \frac{\sum\limits_{x \in V} d^2(x)}{e} = \frac{\sum\limits_{y \in I} d^2(y) + \sum\limits_{z \in V – I} d^2(z)}{e}\\ &\geq \frac{1}{e} \left(\frac{(\sum\limits_{y \in I} d(y))^2}{\alpha} + \frac{(\sum\limits_{z \in V – I} d(z))^2}{n – \alpha} \right)\\ &\geq \frac{1}{e} \left( \frac{(\sum\limits_{y \in I} d(y))^2}{\alpha} + \frac{(\sum\limits_{y \in I} d(y))^2}{n – \alpha} \right)\\ &= \left(\sum\limits_{y \in I} d(y) \right)^2 \frac{n}{e \alpha (n – \alpha)}. \end{aligned}\]
Thus \[\sum\limits_{y \in I} d(y) \leq \sqrt{\frac{q_1 e \alpha (n – \alpha)}{n}}.\]
Applying Lemma 2.1 to the degrees of the vertices in \(I\), we have that \[\begin{aligned} NK(G) &= \prod_{x \in V} d(x)\\ &= \prod_{y \in I} d(y) \prod_{z \in V – I} d(z)\\ &\leq \left(\frac{\sum\limits_{y \in I} d(y)}{\alpha}\right)^{\alpha} \Delta^{n – \alpha}\\ &\leq \left(\frac{q_1 e (n – \alpha)}{\alpha n}\right)^{\frac{\alpha}{2}} \Delta^{n – \alpha}. \end{aligned}\]
If \(NK(G) = \left(\frac{q_1 e (n – \alpha)}{\alpha n}\right)^{\frac{\alpha}{2}} \Delta^{n – \alpha}\), we have that \[\begin{aligned} NK(G) &= \prod_{x \in V} d(x) = \prod_{y \in I} d(y) \prod_{z \in V – I} d(z)\\ &= \left(\frac{\sum\limits_{y \in I} d(y)}{\alpha}\right)^{\alpha} \Delta^{n – \alpha}\\ &= \left(\frac{q_1 e (n – \alpha)}{\alpha n}\right)^{\frac{\alpha}{2}} \Delta^{n – \alpha}. \end{aligned}\]
Thus \(\sum\limits_{y \in I} d(y) = \sqrt{\frac{q_1 e \alpha (n – \alpha)}{n}}\) and \(d(z) = \Delta\) for each \(z \in V – I\). Therefore \[\sum\limits_{y \in I} d^2(y) = \frac{\left(\sum\limits_{y \in I} d(y)\right)^2}{\alpha},\] and \(\sum\limits_{z \in V – I} d(z) = \sum\limits_{y \in I} d(y)\). From Lemma 2.1, we have that \(d(y) = \delta\) for each \(y \in I\). Since \(\sum\limits_{y \in I} d(y) + \sum\limits_{z \in V – I} d(z) = 2e\), we have that \(\sum\limits_{y \in I} d(y) = \sum\limits_{z \in V – I} d(z) = e\). Hence \(G\) is a bipartite graph. Therefore \(G\) is a connected bipartite graph with partition sets of \(I\) and \(V – I\) such that \(|I| = \alpha\), \(d(y) = \delta\) for each \(y \in I\), and \(d(z) = \Delta\) for each \(z \in V – I\).
If \(G\) is a connected bipartite graph with partition sets of \(I\) and \(V – I\) such that \(|I| = \alpha\), \(d(y) = \delta\) for each \(y \in I\), and \(d(z) = \Delta\) for each \(z \in V – I\). Then the line graph of \(G\), denoted \(Line(G)\), is a (\(\delta + \Delta – 2\))-regular graph. Thus \(\lambda_1(Line(G)) = \delta + \Delta – 2\). From the proof of Lemma 2.3 on Page \(567\) in [16], we have \(q_1(G) = \lambda_1(Line(G)) + 2 = \delta + \Delta\).
Note again that \(\alpha \delta = e = (n – \alpha) \Delta\). We have that \[\begin{aligned} \left(\frac{q_1 e (n – \alpha)}{\alpha n}\right)^{\frac{\alpha}{2}} &= \left(\frac{(\delta + \Delta) \alpha \delta (n – \alpha)}{\alpha n}\right)^{\frac{\alpha}{2}}\\ &= \left(\frac{\delta (\delta + \Delta)(n – \alpha)} {n}\right)^{\frac{\alpha}{2}}\\ &= \left(\frac{\delta ((n – \alpha) \delta + (n – \alpha) \Delta)}{n}\right)^{\frac{\alpha}{2}}\\ &= \left(\frac{\delta ((n – \alpha) \delta + \alpha \delta)}{n}\right)^{\frac{\alpha}{2}}\\ &= \delta^{\alpha}. \end{aligned}\]
Hence \[NK(G) = \delta^{\alpha} \Delta^{n – \alpha} = \left(\frac{q_1 e (n – \alpha)}{\alpha n}\right)^{\frac{\alpha}{2}} \Delta^{n – \alpha}.\] \(\square\)
Proof of Theorem 1.2. Let \(G\) be a \(k\)-connected (\(k \geq 2\)) graph with \(n \geq 3\) vertices and \(e\) edges. Suppose \(G\) is not Hamiltonian. Then Lemma 2.6 implies that \(\alpha \geq k + 1\). Also, we have that \(n \geq 2 \delta + 1 \geq 2 k + 1\) otherwise \(\delta \geq k \geq n/2\) and \(G\) is Hamiltonian. Let \(I_1 := \{\, u_1, u_2, …, u_{\alpha} \,\}\) be a maximum independent set in \(G\). Then \(I := \{\, u_1, u_2, …, u_{k + 1} \,\}\) is an independent set in \(G\).
Proof of [1] in Theorem 1.2. Suppose \(G\) satisfies the conditions in this case. Using proofs which are similar to the ones in Proof of [1] in Theorem 1.1, we have that \[(n – k – 1)^{k + 1} \Delta^{n – k – 1} \leq NK(G) \leq (n – k – 1)^{k + 1} \Delta^{n – k – 1}.\] Thus \[NK(G) = (n – k – 1)^{k + 1} \Delta^{n – k – 1}.\] Therefore \(d(y) = (n – k – 1) = \delta\) for each \(y \in I\) and \(d(z) = \Delta\) for each \(z \in V – I\). If \(n = 2k + 1\), then \(G\) is \(K_{k + 1}^{c} \vee H\), where \(H = G[V – I]\) and \(|V(H)| = k\), \(I\) is an independent set in \(G\) with \(|I| = k + 1\) such that \(d(y) = \delta = (n – k – 1)\) for each \(y \in I\) and \(d(z) = \Delta\) for each \(z \in V – I\). If \(n \geq 2k + 2\), then \(\delta = n – k – 1 \geq \frac{n – k – 1 + k + 1}{2} = n/2\) and \(G\) is Hamiltonian, a contradiction. \(\square\)
Proof of [2] in Theorem 1.2. Suppose \(G\) satisfies the conditions in this case. Using proofs which are similar to the ones in Proof of [2] in Theorem 1.1, we have that \[\left(\frac{e}{k + 1}\right)^{k + 1} \Delta^{n – k – 1} \leq NK(G) \leq \left(\frac{e}{k + 1}\right)^{k + 1} \Delta^{n – k – 1}.\]
Thus \[NK(G) = \left(\frac{e}{k + 1}\right)^{k + 1} \Delta^{n – k – 1}.\]
Therefore \(G\) is a connected bipartite graph with partition sets of \(I\) and \(V – I\) such that \(|I| = (k + 1)\), \(d(y) = \delta\) for each \(y \in I\), and \(d(z) = \Delta\) for each \(z \in V – I\). Since \(\delta (k + 1) = e = \Delta (n – k – 1) \geq \delta (n – k – 1)\), we have that \(n \leq 2k + 2\). Since \(n \geq 2k + 1\), we have that \(n = 2k + 1\) or \(n = 2k + 2\). If \(n = 2k + 1\), then \(G\) is \(K_{k, \, k + 1}\). If \(n = 2k + 2\), Lemma 2.8 implies that \(G\) is Hamiltonian, a contradiction. \(\square\)
Proof of [3] in Theorem 1.2. Suppose \(G\) satisfies the conditions in this case. Using proofs which are similar to the ones in Proof of [3] in Theorem 1.1, we have that \[\left(\lambda_1 \sqrt{\frac{n – k – 1}{k + 1}} \, \right)^{k + 1}\Delta^{n – k – 1} \leq NK(G) \leq \left(\lambda_1 \sqrt{\frac{n – k – 1}{k + 1}} \, \right)^{k + 1}\Delta^{n – k – 1}.\]
Thus \[NK(G) = \left(\lambda_1 \sqrt{\frac{n – k – 1}{k + 1}} \, \right)^{k + 1}\Delta^{n – k – 1}.\]
Using the same proofs as the ones in the last paragraph in Proof of [2] in Theorem 1.2, we can complete the proof of this case. \(\square\)
Proof of [4] in Theorem 1.2. Suppose \(G\) satisfies the conditions in this case. Using proofs which are similar to the ones in Proof of [4] in Theorem 1.1, we have that \[\left(\frac{\mu_1 (n – k – 1)}{n}\right)^{k + 1} \Delta^{n – k – 1} \leq NK(G) \leq \left(\frac{\mu_1 (n – k – 1)}{n}\right)^{k + 1} \Delta^{n – k – 1}.\]
Thus \[NK(G) = \left(\frac{\mu_1 (n – k – 1)}{n}\right)^{k + 1} \Delta^{n – k – 1}.\]
Using the same proofs as the ones in the last paragraph in Proof of [2] in Theorem 1.2, we can complete the proof of this case. \(\square\)
Proof of [5] in Theorem 1.2. Suppose \(G\) satisfies the conditions in this case. Using proofs which are similar to the ones in Proof of [5] in Theorem 1.1, we have that \[\left(\frac{q_1 e (n – k – 1)}{(k + 1) n}\right)^{\frac{k + 1}{2}} \Delta^{n – k – 1} \leq NK(G) \leq \left(\frac{q_1 e (n – k – 1)}{(k + 1) n}\right)^{\frac{k + 1}{2}} \Delta^{n – k – 1}.\]
Thus \[NK(G) = \left(\frac{q_1 e (n – k – 1)}{(k + 1) n}\right)^{\frac{k + 1}{2}} \Delta^{n – k – 1}.\]
Using the same proofs as the ones in the last paragraph in Proof of [2] in Theorem 1.2, we can complete the proof of this case. \(\square\)
\(\square\)
The proofs of Theorem 1.3 are similar to the ones of Theorem 1.2. For the sake of completeness, we present the proofs of Theorem 1.3 below.
Proof of Theorem 1.3. Let \(G\) be a \(k\)-connected (\(k \geq 1\)) graph with \(n \geq 9\) vertices and \(e\) edges. Suppose \(G\) is not traceable. Then Lemma 2.7 implies that \(\alpha \geq k + 2\). Also, we have that \(n \geq 2 \delta + 2 \geq 2 k + 2\) otherwise \(\delta \geq k \geq (n – 1)/2\) and \(G\) is traceable. Let \(I_1 := \{\, u_1, u_2, …, u_{\alpha} \,\}\) be a maximum independent set in \(G\). Then \(I := \{\, u_1, u_2, …, u_{k + 2} \,\}\) is an independent set in \(G\).
Proof of [1] in Theorem 1.3. Suppose \(G\) satisfies the conditions in this case. Using proofs which are similar to the ones in Proof of [1] in Theorem 1.1, we have that \[(n – k – 2)^{k + 2} \Delta^{n – k – 2} \leq NK(G) \leq (n – k – 2)^{k + 2} \Delta^{n – k – 2}.\]
Thus \[NK(G) = (n – k – 2)^{k + 2} \Delta^{n – k – 2}.\]
Therefore \(d(y) = (n – k – 2) = \delta\) for each \(y \in I\) and \(d(z) = \Delta\) for each \(z \in V – I\). If \(n = 2k + 2\), then \(G\) is \(K_{k + 2}^{c} \vee H\), where \(H = G[V – I]\) and \(|V(H)| = k\), \(I\) is an independent set in \(G\) with \(|I| = k + 2\) such that \(d(u) = \delta = (n – k – 2)\) for each \(u \in I\) and \(d(v) = \Delta\) for each \(v \in V – I\). If \(n \geq 2k + 3\), then \(\delta = n – k – 2 \geq \frac{n – k – 2 + k + 1}{2} = (n – 1)/2\) and \(G\) is traceable, a contradiction. \(\square\)
Proof of [2] in Theorem 1.3. Suppose \(G\) satisfies the conditions in this case. Using proofs which are similar to the ones in Proof of [2] in Theorem 1.1, we have that \[\left(\frac{e}{k + 2}\right)^{k + 2} \Delta^{n – k – 2} \leq NK(G) \leq \left(\frac{e}{k + 2}\right)^{k + 2} \Delta^{n – k – 2}.\]
Thus \[NK(G) = \left(\frac{e}{k + 2}\right)^{k + 2} \Delta^{n – k – 2}.\]
Therefore \(G\) is a connected bipartite graph with partition sets of \(I\) and \(V – I\) such that \(|I| = (k + 2)\), \(d(y) = \delta\) for each \(y \in I\), and \(d(z) = \Delta\) for each \(z \in V – I\). Since \(\delta (k + 2) = e = \Delta (n – k – 2) \geq \delta (n – k – 2)\), we have that \(n \leq 2k + 4\). Since \(n \geq 2k + 2\), we have that \(n = 2k + 2\), \(n = 2k + 3\), or \(n = 2k + 4\). If \(n = 2k + 2\), then \(G\) is \(K_{k, \, k + 2}\). If \(n = 2k + 3\), then \(k \geq 3\) since \(n \geq 9\). Thus Lemma \(9\) implies that \(G\) has a cycle of length at least \(2 \min \{\, k + 1, k + k – 1, 2k – 2\,\} = 2k + 2 = (n – 1)\) and therefore \(G\) is traceable, a contradiction. If \(n = 2k + 4\), then \(k \geq 3\) since \(n \geq 9\). Thus Lemma 2.8 implies that \(G\) has a cycle of length \(n\) and therefore \(G\) is traceable, a contradiction. \(\square\)
Proof of [3] in Theorem 1.3. Suppose \(G\) satisfies the conditions in this case. Using proofs which are similar to the ones in Proof of [3] in Theorem 1.1, we have that \[\left(\lambda_1 \sqrt{\frac{n – k – 2}{k + 2}} \, \right)^{k + 2}\Delta^{n – k – 2} \leq NK(G) \leq \left(\lambda_1 \sqrt{\frac{n – k – 2}{k + 2}} \, \right)^{k + 2}\Delta^{n – k – 2}.\]
Thus \[NK(G) = \left(\lambda_1 \sqrt{\frac{n – k – 2}{k + 2}} \, \right)^{k + 2}\Delta^{n – k – 2}.\]
Using the same proofs as the ones in the last paragraph in Proof of [2] in Theorem 1.3, we can complete the proof of this case. \(\square\)
Proof of [4] in Theorem 1.3. Suppose \(G\) satisfies the conditions in this case. Using proofs which are similar to the ones in Proof of [4] in Theorem 1.1 and the given conditions in this case, we have that \[\left(\frac{\mu_1 (n – k – 2)}{n}\right)^{k + 2} \Delta^{n – k – 2} \leq NK(G) \leq \left(\frac{\mu_1 (n – k – 2)}{n}\right)^{k + 2} \Delta^{n – k – 2}.\]
Thus \[NK(G) = \left(\frac{\mu_1 (n – k – 2)}{n}\right)^{k + 2} \Delta^{n – k – 2}.\]
Using the same proofs as the ones in the last paragraph in Proof of [2] in Theorem 1.3, we can complete the proof of this case. \(\square\)
Proof of [5] in Theorem 1.3. Suppose \(G\) satisfies the conditions in this case. Using proofs which are similar to the ones in Proof of [5] in Theorem 1.1 and the given conditions in this case, we have that \[\left(\frac{q_1 e (n – k – 2)}{(k + 2) n}\right)^{\frac{k + 2}{2}} \Delta^{n – k – 2} \leq NK(G) \leq \left(\frac{q_1 e (n – k – 2)}{(k + 2) n}\right)^{\frac{k + 2}{2}} \Delta^{n – k – 2}.\] \[NK(G) = \left(\frac{q_1 e (n – k – 2)}{(k + 2) n}\right)^{\frac{k + 2}{2}} \Delta^{n – k – 2}.\]
Using the same proofs as the ones in the last paragraph in Proof of [2] in Theorem 1.3, we can complete the proof of this case. \(\square\)
\(\square\)