We determine the maximum number of edges of a graph without containing the 2-power of a Hamilton path. Using this result, we establish a spectral condition for a graph containing the 2-power of a Hamilton path. Furthermore, we characterized the extremal graphs with the largest spectral radius that do not contain the 2-power of a Hamilton path.
Graphs considered below will always be simple. A simple graph \(G\) consists of a finite nonempty set of vertices \(V(G)\) and a set of edges \(E(G)\). Let \(e(G)=\left| E(G) \right|\). If \(uv\) is an edge in graph \(G\), edge \(uv\) is said to be incident with vertices \(u\) and \(v\), and vertices \(u\) and \(v\) are said to be adjacent. Let \(d(u)\) be the number of edges in \(G\) which incident with vertex \(u\). We denote by \(\bigtriangleup(G)\) and \(\delta(G)\) the maximum and minimum degree of \(G\), respectively. Let \(\delta^*(G) =\min\{d(u): u\in V(G) ~\mbox{is a non-isolated vertex}\}\). We use \(C_n\), \(P_n\), \(K_n\) and \(S_n\) to denote the cycle, the path, the complete graph and the star on \(n\) vertices, respectively. For a subgraph \(H\) of \(G\), we use \(G-E(H)\) to denote the graph obtained from \(G\) by deleting edges of \(H\). The complement graph of \(G\), denoted \(\overline{G}\), is the graph on the same vertex as \(G\), but in which two such vertices are adjacent if and only if they are not adjacent in \(G\). For graphs \(G\) and \(H\), we denote by \(G\cup H\) the disjoint union of \(G\) and \(H\). We call a cycle and a path contain all vertices of \(G\) as a Hamilton cycle and a Hamilton path of \(G\), respectively.
Ore [10] determined the maximum number of edges in a graph that does not contain a Hamilton cycle. In [5], Erdős and Gallai identified the maximum number of edges in an \(n\)-vertex graph that lacks a Hamilton path. Spectral conditions for Hamilton cycles have been provided in [3, 7, 9, 11]. Fiedler and Nikiforov [4] have established precise conditions on the spectral radius for the existence of Hamilton paths and cycles.
The 2-power of a graph \(G\), denoted by \(G^2\), is another graph that has the same vertex set as \(G\), but in which two vertices are adjacent when their distance in \(G\) is at most two. In 2022, Khan and Yuan [6] determined the maximum number of edges of a graph without containing the 2-power of a Hamilton cycle and characterized all its extremal graphs. Yan, He, Feng, and Liu [12] established a spectral condition for a graph containing \(C^2_n\). Additionally, they proposed the problem of studying the extremal graphs with the maximum spectral radius among all graphs of large order \(n\) that do not contain \(C^k_n\), and conjectured that \(K_1 \vee_{2k-1} K_{n-1}\) is the unique extremal graph when \(n\) is sufficiently large, where \(K_1 \vee_{2k-1} K_{n-1}\) be the graph obtained from \(K_{n-1}\) by adding a new vertex \(u\) and adding \(2k-1\) edges between \(u\) and \(V (K_{n-1})\). Recently, Zhang [14] studied the spectral conditions for a graph to contain a copy of the \(k\)-power of a Hamilton cycle and provided sharp spectral radius bounds for a graph of large order \(n\) to contain \(C^k_n\). This gives a positive answer to a question in [12]. A natural idea is to study Turán-type problems for graphs that do not contain the 2-power of a Hamilton path, as well as the spectral conditions for these problems.
Throughout the paper we use the standard graph theory notation (see, e.g., [6]). We use \(G^{+t}\) to denote the set of graphs obtained from \(G\) by adding a new vertex and joining it to any \(t\) vertices of \(G\). In particularly, we use \(G^+\) instead of \(G^{+t}\) for \(t=1\). Let \(G^-\) denote the set of graphs obtained from \(G\) by deleting any edge. For graphs \(G\) and \(H\), we say that \(G\) packs with \(H\) if \(K_n\) contains edge-disjoint copies of \(G\) and \(H\).
We define the forbidden family of graphs \(\mathcal{H}_n\) with \(n\geqslant 6\) as follows (see Table 1) and let \(\mathcal{H}^*_n\) be the sets of graphs obtained from \(\mathcal{H}_n\) by adding \(S_{n-2} \cup K_2\) and \(S_{n-1}\) to \(\mathcal{H}_n\) for \(n\in \{6,9\}\).
| \(n\) | \(\mathcal{H}_n\) | \(e(H)\), \(H\in \mathcal{H}_n\) | \(t=\left\lfloor {n}/ {4}\right\rfloor\) |
|---|---|---|---|
| 6 | \(K_3\) | 3 | 1 |
| 7 | \(K_4^-, S_5\cup K_2, S_6\) | 5 | 1 |
| 8 | \(K_4, S_6\cup K_2, S_7\) | 6 | 2 |
| 9 | \(K_4\) | 6 | 2 |
| 10 | \(S_8\cup K_2, S_9\) | 8 | 2 |
| 11 | \(S_9\cup K_2, S_{10}\) | 9 | 2 |
| 12 | \(K_5, S_{10}\cup K_2, S_{11}\) | 10 | 3 |
| 13 | \(S_{11}\cup K_2, S_{12}\) | 11 | 3 |
| \(n\geqslant14\) | \(S_{n-2} \cup K_2, S_{n-1}\) | \(n-2\) | \(\left\lfloor{n}/{4}\right\rfloor\) |
Let \(\mathcal{F}\) be the set of \(n\)-vertex graphs, we call \(G\) a \(\mathcal{F}\)-free graph if \(G\) contains no graph in \(\mathcal{F}\) as a subgraph. In particularly, we call \(G\) a \(F\)-free graph instead of a \(\mathcal{F}\)-free graph for \(\mathcal{F} = \{{F}\}\). We will establish the following theorem.
Theorem 1.1. Let \(H\) be a graph on \(n\geqslant 6\) vertices with at most \(n-2\) edges. Then \(H\) packs with \(P_n^2\) if and only if \(H\) is \(\mathcal{H}^*_n\)-free graph.
According to the definition of \(H\) packing with \(P_n^2\), Theorem 1.1 establishes that \(\overline{H}\) contains \(P_n^2\) as a subgraph if and only if \(H\) is \(\mathcal{H}^*_n\)-free. Equivalently, \(\overline{H}\) avoids containing \(P_n^2\) as a subgraph precisely when \(H\) contains some graph in \(\mathcal{H}^*_n\) as a subgraph. This characterization directly yields the maximum number of edges in an \(n\)-vertex \(P_n^2\)-free graph, as stated in the following Corollary.
Corollary 1.2. Let \(G\) be a \(P_n ^2\)-free graph on \(n \geqslant6\) vertices. Then we have \[e(G) \leqslant\left\{\begin{array}{ll}12, & n=6 ; \\ 30, & n=9 ; \text { and } \\ {n-1 \choose 2}+1, & \text { otherwise. }\end{array}\right.\]
Moreover, the equality holds if and only if \(G=K_n-E(H)\) with \(H \in \mathcal{H}_n\).
Note that Theorem 1.1 in [1] determines, for sufficiently large \(n\), the maximum number of edges in \(n\)-vertex \(P_n^{2}\)-free graphs. In contrast, Corollary 1.2 settles all cases with \(n\geqslant6\) and characterizes the extremal graphs. Let \(A\) be the adjacency matrix of \(G\). The spectral radius of \(G\), denoted by \(\mu(G)\), is the maximum eigenvalue of \(A\). We obtain the following theorem concerning \(P_n^2\) and \(\mu(G)\).
Theorem 1.3. Let \(G\) be an \(n\)-vertex graph and \(n \geqslant 6\). If \(\mu(G)>n-2\), then \(G\) contains \(P_n^2\) unless \(G\) is a subgraph of \(K_n- E(S_{n-1})\) or \(K_n- E(K_3)\) for \(n=6\), and a subgraph of \(K_n- E(S_{n-1})\) for \(n \geqslant 7\).
By applying the following lemma, we obtain a corollary of Theorem 1.3.
Lemma 1.4(Brouwer and Haemers [2]).Let \(H\) be a subgraph of a connected graph \(G\), then \(\mu(G)\geqslant \mu(H)\), with equality if and only if \(H = G\).
By tedious calculations, \(\mu(K_6 – E(K_3))>4.1>\mu(K_6- E(S_{5}))\). Clearly, \(K_n – E(K_3)\) and \(K_n – E(S_{n-1})\) contain no copy of \(P_n^2\) for \(n = 6\) and \(n \geqslant 7\), respectively. Then by Lemma 1.4, we get the following Corollary.
Corollary 1.5. Let \(G\) be a \(P_n^2\)-free graph on \(n \geqslant6\) vertices. Then \(\mu(K_n – E(K_3))\geqslant \mu(G)\) for \(n = 6\), and \(\mu(K_n – E(S_{n-1})) \geqslant \mu(G)\) for \(n \geqslant7\). Equality holds if and only if \(G = K_n – E(K_3)\) for \(n = 6\), and \(G = K_n – E(S_{n-1})\) for \(n \geqslant 7\).
Note that Theorem 1.2 in [8] determines, for sufficiently large \(n\), the minimal spectral radius of the \(n\)-vertex \(P_n^{2}\)-free graphs and characterizes the extremal graphs, whereas Corollary 1.5 settles all cases with \(n\geqslant 6\) and likewise characterizes the extremal graphs.
The proof of Theorem 1.1 is based on the following proposition.
Proposition 2.1. Let \(n\geqslant 7\) and \(s \leqslant \left\lfloor{n}/{4}\right\rfloor\). If \(P^2_{n-1}\) packs with \(F\), then \(P^2_{n}\) packs with each graph in \(F^{ +s}\).
Proof. Let \(P_{n-1}=v_1\ldots v_{n-1}\). Suppose that \(\overline{P^2_{n-1}}\) contains a copy of \(F\). For any four consecutive vertices, say \(x_1,x_2,x_3,x_4\) on \(\overline{P^2_{n-1}}\), we can add a new vertex \(y\), edges \(x_1x_3, x_2x_4\) and all edges between \(y\) and \(V(\overline{P^2_{n-1}})\setminus \{x_1,x_2,x_3,x_4\}\) to obtain \(\overline{P^2_{n}}\). If we add a new vertex \(y\) and join all edges between \(y\) and \(V(\overline{P^2_{n-1}})\setminus \{v_1,v_2\}\) (or \(V(\overline{P^2_{n-1}})\setminus \{v_{n-1},v_{n-2}\}\)), then the resulting graph is \(\overline{P^2_{n}}\). Thus if \(\overline{P^2_{n}}\) is \(F^\prime\)-free for some \(F^\prime\in F^{ +s}\), then the added vertex \(z\) must be adjacent to at least one vertex of \(v_1,v_2\), at least one vertex of \(v_{n-2},v_{n-1}\) and at least one vertex of any four consecutive vertices \(\overline{P^2_{n-1}}\). Therefore, \(s\geqslant 2+ \lfloor(n-4)/4 \rfloor= \lfloor n/4 \rfloor+1\), contradicting \(s \leqslant \left\lfloor{n}/{4}\right\rfloor\). ◻
For a subgraph \(H\) of \(G\), we use \(G-H\) to denote the graph obtained from \(G\) by deleting vertices and edges of \(H\).
Proof of of Theorem 1.1. Let \(n\geqslant 6\) and \(t = \left\lfloor{n}/{4}\right\rfloor\). Let \(F\) be an \(n\)-vertex graph with at most \(n – 2\) edges. Since \(\bigtriangleup (\overline{P^2_{n}}) =n-3\), \(P^2_{n}\) does not pack with \(S_{n-1}\). In any packing of \(P^2_{n}\) with \(S_{n-2}\), \(\overline{P^2_{n}} – S_{n-2}\) are two isolated vertices. So \(P^2_{n}\) does not pack with \(S_{n-2}\cup K_2\). Figures 1 and 2 clearly show that \(P^2_{n}\) does not pack with the graph in \(\mathcal{H}^*_{n}\setminus \{S_{n-1}, S_{n-2}\cup K_2\}\) for \(n=6,7,8,9,12\).
Assume that \(F\) is \(\mathcal{H}^*_n\)-free graph. If \(n = 6\), then it is clear that \(F\) packs with \(P^2_{6}\) (see Figures 1 and 3). For \(7\leqslant n \leqslant 13\), assume that the theorem holds for \(n – 1\). For each \(n\), we consider \(F\) in the following three cases:
(a) \(\delta^*(F)\geqslant t+1\),
(b) \(\delta^*(F)\leqslant t\) and there is a vertex \(x\) with \(1 \leqslant d(x) \leqslant t\) such that \(F – x\) is \(\mathcal{H}^*_{n-1}\)-free graph and
(c) \(\delta^*(F)\leqslant t\) and \(F – x\) contains some graph in \(\mathcal{H}^*_{n-1}\setminus \{S_{n-2}, S_{n-3}\cup K_2\}\) as a subgraph for each \(x\) with \(1 \leqslant d(x) \leqslant t\).
For \(\delta^*(F)\leqslant t\), if \(F – x\) contains \(S_{n-2}\) or \(S_{n-3}\cup K_2\) as a subgraph for some vertex \(x\) with \(1 \leqslant d(x) \leqslant t\), then there are \(n-2\) edges in \(F\) and \(d(x)=1\). Since \(F\) is \(\mathcal{H}^*_n\)-free graph, we can easily find a vertex \(y\in V(F)\) with \(1 \leqslant d(y) \leqslant t\) such that \(F – y\) is \(\mathcal{H}^*_{n-1}\)-free graph. i.e., \(F\) belongs to case (b). Therefore, \(F\) belongs one of cases (a), (b) or (c).
For all \(7\leqslant n \leqslant 13\), in case (b), by the induction hypothesis, \(F – x\) packs with \(P^2_{n-1}\), and hence \(F\) packs with \(P^2_{n}\) according to Proposition 2.1. Thus, we are left with cases (a) and (c).
Let \(n=7\). Then \(t = 1\). The graphs with at most 5 edges in case (a) are \(C_5\), \(C_4\) and \(K_3\) (see Figure 1). It is easy to see that \(P^2_{7}\) packs with \(C_5\), \(C_4\) and \(K_3\). Note that \(\mathcal{H}^*_{6}\setminus\{S_{5}, S_{4}\cup K_2\}=\{K_3\}\). The graphs in case (c) are \(K_3 \cup P_3\), \(K_3 \cup M_2\), \(K^+_3\cup K_2\), \(G_1\), \(G_2\) and \(G_3\), where \(M_2\) is the 4-vertex graph on 2 independent edges, \(G_1\), \(G_2\) and \(G_3\) are obtained from \(K ^+_3\) by adding a new vertex and connecting it to a vertex of \(K ^{+}_{3}\) with degree one, two and three respectively. For all such \(F\), we can get \(P^2_{7}\) packs with \(F\) by \(P^2_{7}\) packs with \(K_3\).
Let \(n = 8\). Then \(t = 2\). The unique graph \(H\) with \(\delta^{*}(H) \geqslant 3\) and \(e(H) \leqslant 6\) is \(K_4\).
Since \(F\) is \(\mathcal{H}^*_{8}\)-free graph and \(K_4 \in\mathcal{H}^*_{8}\), thus there is no graph in case (a). Note that after deleting a vertex with degree at most two, the graphs in case (c) must contain \(K^-_4\) as a subgraph. Since there are at most 6 edges in \(F\) and \(F\) is \(K_4\)-free graph, thus there is no graph in case (c).
Let \(n = 9\). Then \(t = 2\). The unique graph \(H\) with \(\delta^{*}(H)\geqslant 3\) and \(e(H) \leqslant 7\) is \(K_4\). Since \(F\) is \(\mathcal{H}^*_{9}\)-free graph and \(K_4 \in\mathcal{H}^*_{9}\), there is no graph in case (a).
Since \(\overline{P^2_{9}}\) is \(K_4\)-free graph (the three vertices of each triangle of \(\overline{P^2_{9}}\) have no common neighbors, see Figure 1), there is no graph in case (c).
Let \(n = 10\). Then \(t = 2\). The graphs with at most 8 edges in case (a) are \(K_4\) and \(W_5\) (the graph obtained from \(C_4\) by adding a new vertex and joining it to all vertices of \(C_4\)). We can easily get that \(F\) packs with \(K_4\) and \(W_5\) (see Figure 1). Note that \(\mathcal{H}^*_{9}\setminus\{S_{8}, S_{7}\cup K_2\}=\{K_4\}\). Hence the graphs with at most 8 edges in case (c) are \(K ^+_4 \cup K_2\), \(K_4 \cup M_2\), \(K_4 \cup P_3\), \(G_4\), \(G_5\), \(G_6\) and \(G_7\), where \(G_4\), \(G_5\) and \(G_6\) are obtained from \(K ^+_4\) by adding a new vertex and joining it to a vertex of \(K ^+_4\) with degree one, three and four respectively and \(G_7\) is obtained from \(K_4\) by adding an isolated vertex and joining it to two vertices of \(K_4\).
For all such \(F\), we can get \(P^2_{10}\) packs with \(F\) by \(P^2_{10}\) packs with \(K_4\) (see Figure 4).
Let \(n = 11\). Then \(t = 2\). In case (a) the graphs with minimum degree at least three and on at most 9 edges are \(K_4\), \(W_5\), \(K ^- _5\), \(K_{3,3}\) and \(G_8\), where \(K_{3,3}\) is the complete bipartite graph with partite sets with sizes 3 and 3, and \(G_8\) is obtained from two vertex disjoint copies of \(K_3\) and joining three independent edges between them. Obviously, \(P^2_{11}\) packs with each graph in case (a) (see Figures 5 and 6).
Since \(\mathcal{H}^*_{10}\setminus\{S_{9}, S_{8}\cup K_2\}=\varnothing\), there is no graph in case (c).
Let \(n = 12\). Then \(t = 3\). The unique graph \(H\) with \(\delta^{*}(H) \geqslant 4\) and \(e(H) \leqslant 10\) is \(K_5\). Since \(F\) is \(\mathcal{H}^*_{12}\)-free graph, thus there is no graph in case(a). Clearly, there is no graph in case (c).
Let \(n = 13\). Then \(t = 3\). In case (a) the unique graph with minimum degree at least 4 on at most 11 edges is \(K_5\). It is obvious that \(P^2_{13}\) packs with \(K_5\). Note that \(\mathcal{H}^*_{12}\setminus\{S_{11}, S_{10}\cup K_2\}=\{K_5\}\). Hence the graphs with at most 11 edges in case (c) are \(K^ +_5\) and \(K_5\cup K_2\). Since \(P^2_{13}\) packs with \(K_5\) (see Figure 6), \(P^2_{13}\) packs with \(K^+ _5\) and \(K_5 \cup K_2\).
Suppose it is true for \(n- 1 \geqslant 13\). For each graph on at most \(n -3\) edges, there is a graph in \(\mathcal{K}(n ,n-2)\setminus \{S_{n-1},S_{n-2}\cup K_2\}\) which contains it as a subgraph, where \(\mathcal{K}(n ,n-2)\) denotes the set of graphs on \(n\) vertices with \(n-2\) edges. It is sufficient to show that \(P^2_{n}\) packs with each \(F\in \mathcal{K}(n,n-2)\setminus \{S_{n-1},S_{n-2}\cup K_2\}\). Then by induction hypothesis, \(P^2_{n-1}\) packs with each \(F'\in \mathcal{K}(n-1,n-3)\setminus \{S_{n-2},S_{n-3}\cup K_2\}\). We consider the following two cases. (a). \(1\leqslant\delta^*(F)\leqslant t\). By Proposition 2.1, we get that \(P^2_{n}\) packs with \(F\). (b). \(\delta^*(F)\geqslant t+1\). Then the number of non-isolated vertices of \(F\) is at most \(\lfloor 2(n -2)/ \lceil(n+4)/4\rceil \rfloor\). On the other hand, it is easy to see that \(P^2_{n}\) packs with \(K_s\), where \(s =\lceil{n}/{3}\rceil\). If \(n \geqslant 16\), then we have \(\lfloor 2(n -2)/ \lceil(n+4)/4\rceil \rfloor\leqslant\lceil{n}/{3}\rceil\), i.e., \(K_s\) contains \(F\). Thus \(P^2_{n}\) packs with \(F\). Let \(n\in\{14, 15\}\). Then \(t=3\). By considering the structure of \(P^2_{n}\), \(P^2_{n}\) packs with \(K^- _6\). Since \(F\) has at most \(n-2\leqslant 13\) edges and \(\delta^\ast(F)\geqslant 4\), the number of non-isolated vertices of \(F\) is at most 6, whence \(K^-_6\) contains \(F\). Therefore, \(P^2_{n}\) packs with \(F\), the proof is complete. ◻
The proof of Theorem 1.3 is based on the following Lemmas.
Lemma 3.1(Fiedler and Nikiforov [4]).Let \(G\) be a graph of order \(n\) and spectral radius \(\mu(G)\). If \[\mu(G)\geqslant n-2,\] then \(G\) contains a Hamilton path unless \(G=K_{n-1}\cup K_1\).
Lemma 3.2(Hong [13]).Let \(G\) be a connected graph of order \(n\) with \(m\) edges. The spectral radius \(\mu(G)\) satisfies \(\mu(G)\leqslant \sqrt{2m-n+1}\) with equality if and only if \(G\) is isomorphic to \(S_n\) or \(K_n\).
Proof of of Theorem 1.3. Let \(\mu(G)> n-2\) and \(n\geqslant 6\). Suppose that \(G\) is not a subgraph of \(K_n – E(S_{n-1})\) and \(K_6 – E(K_3)\) for \(n\geqslant 6\). It follows from Lemma 3.1 that \(G\) contains a Hamilton path (\(K_n – E(S_{n-1})\) contains \(K_{n-1}\cup K_1\) as a subgraph), whence \(G\) is connected. By Lemma 3.2, we have \(\mu(G)\leqslant \sqrt{2e(G)-n+1}\), with equality if and only if \(G=K_n\) (\(S_n\) does not contain a Hamilton path). Since \(K_n\) contains a copy of \(P_n^2\), we may assume that \(\mu(G)< \sqrt{2e(G)-n+1}\). Then \(e(G)>(n^2-3n+3)/2\), implying \(e(G)\geqslant {n-1 \choose 2}+1\). By Corollary 1.5, \(G\) contains a copy of \(P_n^2\) unless \(G\in \{K_n- E(H) : H\in \mathcal{H}^*_n\}\). Since the maximum degree of \(K_n – E(S_{n-2}\cup K_2)\) is \(n-2\), we get \(\mu(K_n – E(S_{n-2}\cup K_2)) \leqslant n-2\). By tedious calculations, we get \(\mu(K_6 – E( K_3)) > 4\), \(\mu(K_7 – E(K_4^-)) < 5\), \(\mu(K_n – E( K_4)) < n-2\) for \(n=8,9\) and \(\mu(K_{12} – E( K_5) ) <10\). Hence, the proof is complete. ◻
This work is supported by National Natural Science Foundation of China (12271169, 12331014 and 12350410356 (RFIS)), Science and Technology Commission of Shanghai Municipality (22DZ2229014), Innovation Action Plan (Basic research projects) of Science and Technology Commission of Shanghai Municipality (21JC1401900), and Shang dian zhi yuan funding of Shanghai University of Electric Power.
The authors have no relevant financial or non-financial interests to disclose.
Data sharing is not applicable to this article as no new data were created or analyzed in this study.