The first, second Zagreb connection indices and modified first Zagreb connection index are defined as \(Z{C_1}(G)={\sum\limits_{{v\in V(G)}} {{\tau _G}^2(v)} }\), \(ZC{}_{2}(G)=\displaystyle\sum_{uv\in E(G)}^{}\tau{}_{G}(u)\tau{}_{G}(v)\) and \(ZC{}_{1}^{\ast }(G)=\displaystyle\sum_{v\in V(G)}^{}d{}_{G}(v)\tau{}_{G}(v)\), respectively. In this paper, we consider the maximum values of \(Z{C_1}(G)\), \(Z{C_2}(G)\), \(Z{C_1}^{*}(G)\) of \(n\)-vertex trees with fixed matching number \(m\) and the extremal graphs are also characterized.
Throughout this paper, we are concerned with only simple and finite graphs. Let \(G\) be a graph with vertex set \(V(G)\) and edge set \(E(G)\). Let \(N\left ( v \right )\) be the neighborhood of the vertex \(v\in V\left ( G \right )\), that is \(N\left ( v \right )=\left \{ u\in V\left ( G \right ) |uv\in E\left ( G \right ) \right \}\). For a vertex \(v\in V(G)\), the degree of \(v\), denoted by \(d_{G} (v)\), is defined as the number of vertices adjacent to \(v\), that is \(d_{G} (v)=\left | N\left ( v \right ) \right |\). The maximum degree of a graph \(G\) is denoted by \(\bigtriangleup (G)\), i.e., \(\bigtriangleup (G)=\underset {v\in V\left ( G \right )}{max}d_{G} (v)\). The eccentricity \(e\left ( v \right )\) of \(v\) is defined as \(e\left ( v \right ) = \underset{w\in V\left ( G \right ) }{max}\left \{ d\left ( v,w \right ) \right \}\), where \(d\left ( v,w \right )\) is the length of the shortest paths connecting \(v\) and \(w\). The diameter of a graph \(G\) is defined as \(d=\underset{v\in V\left ( G \right ) }{max}\left \{ e\left ( v \right ) \right \}\). The connection number of \(v\) is defined as the number of vertices having distance \(2\) from \(v\), denoted by \({\tau _G}(v)\), see [17]. The subgraph of \(G\) obtained by deleting a vertex \(x\)(\(x\in V(G)\)) as well as its incident edges is denoted by \(G-\left \{ x\right \}\). A star denoted by \(K{}_{1,n-1}\) is a tree having \(n\) vertices and \(n-1\) pendant vertices. Undefined terminology and notations of graph theory can be found in [3].
A topological index is a number that can be associated with chemical structures to predict their various properties [9]. Topological indices have been widely used in the field of mathematical chemistry, especially in the field of quantitative structure-property relationship and quantitative structure-activity relationship investigations. In \(1947\), Wiener proposed the first well-known topological index [19]. Afterwards, a large number of topological indices were designed, under different parameters of graph such as degree, distance, eccentricity. Most of the chemical graph theory literature is occupied by the degree-based topological indices [8]. It is well-known for the first and second Zagreb indices [5, 6], which are defined as follows: \[\begin{aligned} M_{1}(G)=\sum_{v\in V(G) }^{} d_{G}^{2} \left ( v \right ),\quad M_{2} \left ( G \right ) =\sum_{uv\in E\left ( G \right ) } d_{G} \left ( u \right ) d_{G} \left ( v \right ). \end{aligned}\]
Over the past decades, numerous results concerning the Zagreb indices have been put forward. Inspired by the great potential of application, researchers proposed several variants of the Zagreb index. We focus on the Zagreb connection indices, which are based on the connection number of vertex \(v\). The Zagreb connection indices are often used in network topology optimization, where it measures the overall connectivity and robustness of a network. It is useful for designing efficient and fault-tolerant networks, for example in telecommunications or transportation systems. The Zagreb connection indices can also be used to predict the solubility, stability, or reactivity of DNA molecules, among other chemical characteristics.
Naji et al. [10] presented the first Zagreb connection index \(Z{C_1}(G)\) and the second Zagreb connection index \(Z{C_2}(G)\) in \(2017\), which are defined as follows:
\[Z{C_1}(G) = {\sum\limits_{{v\in V(G)}} {{\tau _G}^2(v)}},\qquad ZC{}_{2}(G)=\displaystyle\sum_{uv\in E(G)}^{}\tau{}_{G}(u)\tau{}_{G}(v).\]
In \(2018\), a new index named as the modified first Zagreb connection index is proposed in [1], which is defined as
\[ZC{}_{1}^{\ast }(G)=\displaystyle\sum_{v\in V(G)}^{}d{}_{G}(v)\tau{}_{G}(v).\]
In [16] Raza et al. presents the identification of an extremal tree with the maximum first Zagreb connection index among all trees with a specific total domination number. In [14] Raza compute the leap Zagreb Connection Numbers for Some Networks Models. Wang et al. [18] explore upper and lower bounds of the hyper Zagreb indices, and provide the relation between Zagreb indices and hyper Zagreb indices. In [13], Noureen et al. found the modified first Zagreb connection index of trees with fixed order and number of branching vertices. Noureen et al. [12] found the extremal trees for the modified first Zagreb connection index with a fixed number of pendent vertices. Raza and Akhter [15] identified extremal trees with the highest Zagreb connection indices among a set of trees with specific domination numbers. Gutman et al. [7] determined the different bounds for the connection Zagreb indices of unicyclic graphs and trees by finding their extremal graphs. Another study [7] established various bounds for the connection Zagreb indices of unicyclic graphs and trees by discovering their extremal graphs. Details about the mathematical properties of the index \(ZC{}_{1}^{\ast }(G)\) can be found in [4, 20, 11, 2].
A matching of a graph is a set of pairwise non-adjacent edges [3]. If \(M\) is a matching, the two ends of each edge of \(M\) are said to be matched under \(M\), and each vertex incident with an edge of \(M\) is said to be covered by \(M\). A maximum matching is a matching that covers as many vertices as possible. If a maximum matching covers every vertex of the graph, we call it a perfect matching. A graph is matchable if it has a perfect matching. The number of edges in a maximum matching is called the matching number of \(G\), denoted by \(m_{G}\). In network design, the matching number is used to optimize resource allocation. In graph theory, the matching number can be applied to various problems such as maximum bipartite matching, resource allocation, and solving systems of linear equations, particularly in optimization problems where finding the maximum matching is crucial.
In this paper, we concentrate on characterizing the extremal graphs with the maximum values of \(Z{C_1}(G)\), \(Z{C_2}(G)\) and \(ZC{}_{1}{}^{\ast }(G)\), where \(G\in \mathcal{T}(n,m)\) and \(\mathcal{T}(n,m)\) is the set of trees on \(n\) vertices with matching number \(m\). Since \(m=1\) if and only if \(T\cong K{}_{1,n-1}\), we restrict our attention to \(2\le m\le \left \lfloor \frac{n}{2}\right \rfloor\). Let \(T_{n,m} ^{*}\) be constructed by attaching a pendant edge to \(m-1\) pendant vertices of \(K{}_{1,n-m}\), respectively. Obviously, \(T_{n,m} ^{*} \in \mathcal{T}(n,m)\) and \(\varDelta (T_{n,m} ^{*} )=n-m\) (depicted in Figure 1).
First, we determine the maximum value of the first Zagreb connection index in \(\mathcal{T}(n,m)\), where \(2\le m\le \left \lfloor \frac{n}{2}\right \rfloor\).
By direct computation, we can get \[\begin{aligned} ZC{}_{1}(T_{n,m} ^{*} )&=(n-m)(n-m-1){}^{2}+(m-1){}^{2}+(m-1)\\&=m{}^{2}-m+(n-m)(n-m-1){}^{2}. \end{aligned}\]
Theorem 2.1. If \(T\in\mathcal{T}(n,m)\), then we have \[\label{2.1} ZC{}_{1}(T)\leq m{}^{2}-m+(n-m)(n-m-1){}^{2}, \tag{1}\] equality holds if and only if \(T\cong T_{n,m} ^{*}\).
Proof. Case 1. If \(\varDelta(T)=2\).
In this case, we must have \(T\cong P{}_{n}\), \(m=\left \lfloor \frac{n}{2}\right \rfloor\). For \(n=4\), \(T\cong T{}_{4,2}^{* }\), then inequality (1) is obviously true. Otherwise, for \(n\geq5\), we have \(ZC{}_{1}(P{}_{n})=4n-12\).
If \(n\) is odd, then \(m=\frac{n-1}{2}\), we have \[\begin{aligned} ZC{}_{1}(P{}_{n})-ZC{}_{1}(T{}_{n,\frac{n-1}{2}}^{* })&=4n-12- \left ( \frac{n-1}{2} \right ) ^{2}+\frac{n-1}{2}\\&\quad-\left ( n-\frac{n-1}{2}\right )\left ( n-\frac{n-1}{2}-1\right )^{2}\\& =-\frac{1}{8} \left ( n^{3}+n^{2} -41n+103 \right ) < 0. \end{aligned}\]
If \(n\) is even, then \(m=\frac{n}{2}\), we get \[\begin{aligned} ZC{}_{1}(P{}_{n})-ZC{}_{1}(T{}_{n,\frac{n}{2}}^{* })&=4n-12- \left ( \frac{n}{2} \right ) ^{2}+\frac{n}{2}-\left ( n- \frac{n}{2}\right )\left ( n-\frac{n}{2}-1 \right ) ^{2} \\&=-\frac{1}{8}(n-4){}^{2}(n+6)< 0. \end{aligned}\]
Therefore, the inequality in Eq. (1) will be hold.
Case 2. If \(\varDelta(T)\geq3\).
We prove the result by using induction on \(n\). Since \(\varDelta(T)\geq3\), we have \(n\ge 5\). For \(n=5\), we have \(T\cong T{}_{5,2}^{* }\), Eq. (1) is true. So we assume that Eq. (1) is always true for trees of order at most \(n-1\). Let \(T\in\mathcal{T}(n,m)\), suppose \(P{}_{d+1}=x{}_{1}x{}_{2}\text{···}x{}_{d+1}\) is a longest path in \(T\), where \(d\) is the diameter of \(T\). We know that \(\varDelta(T)\le n-m\) and for every vertex \(x\in V(T)\), \(\tau(x)\leq n-m-1\). Construct \(T{}^{'}=T-\left \{ x{}_{1}\right \}\).
Subcase 2.1. If \(m{}_{T{}^{'}}=m{}_{T}-1=m-1\).
In this case, we must have \(d{}_{T}(x{}_{2})=2\), \(\tau {}_{T}(x{}_{2})=\tau {}_{T{}^{'}}(x{}_{2})\), \(\tau {}_{T}(x{}_{3})=\tau {}_{T{}^{'}}(x{}_{3})+1\) and \(\tau {}_{T}(x{}_{3})\le m-1\).
By induction hypothesis, it follows that \[\begin{aligned} ZC{}_{1}(T)&=ZC{}_{1}(T{}^{'})+2\tau {}_{T}(x{}_{3})\\ &\leq (m-1){}^{2}-(m-1)+(n-m)(n-m-1)^{2}+2(m-1)\\ &=m{}^{2}-m+(n-m)(n-m-1)^{2}, \end{aligned}\] equality holds if and only if \(T{}^{'}\cong T{}_{n-1,m-1}^{* }\), and \(x{}_{1}\) is adjacent to \(x{}_{2}\), whose degree is \(2\) in \(T\). Hence, there may be two possibilities, which is showed in Figure 2. Since \(m{}_{T{}^{'}}=m{}_{T}-1\), we know \(T\cong T_{n,m} ^{*}\).
Subcase 2.2. If \(m{}_{T{}^{'}}=m{}_{T}=m\).
For \(z\in N{}_{T}(x{}_{2})\setminus \left \{ x{}_{1}\right \}\), We have \(\tau {}_{T}(z)=\tau {}_{T{}^{'}}(z)+1\) and \(\tau {}_{T}(z)\le n-m-1\). \(\tau {}_{T}(x{}_{2})=\tau {}_{T{}^{'}}(x{}_{2})\), \(\tau {}_{T}(x{}_{1})\le n-m-1\).
By induction hypothesis, we have \[\begin{aligned} ZC_{1}(T)&=ZC_{1}(T^{'})+\tau _{T}^{2}(x_{1})+\displaystyle\sum_{z\in N_{T}(x_{2})\setminus \left \{ x_{1}\right \}}\left ( 2\tau_{T}(z)-1 \right )\\ &\leq m^{2}-m+(n-m-1)(n-m-2)^{2}+(n-m-1)^{2}\\&\quad+(n-m-1)\times [2\times(n-m-1)-1]\\&=m^{2}-m+(n-m)(n-m-1)^{2}, \end{aligned}\] equality holds if and only if \(T{}^{'}\cong T{}_{n-1,m-1}^{* }\), and also \(x{}_{1}\) is adjacent to \(x{}_{2}\), whose degree is \(n-m\) in \(T\). Hence \(T\cong T_{n,m} ^{*}\). ◻
Here we list two examples.
Example 2.2. Consider all five trees in \(\mathcal{T}(8,2)\) (as shown in Figure 3). It follows from straightforward calculations that we get the first Zagreb connection index for these trees as follows:
\(ZC{}_{1}(T{}_{1}=T{}_{8,2}^{* })=152\quad ZC{}_{1}(T{}_{2})=92\quad ZC{}_{1}(T{}_{3})=72\quad ZC{}_{1}(T{}_{4})=92\quad ZC{}_{1}(T{}_{5})=62\).
Thus \(T{}_{8,2}^{* }\) has the maximum value of the first Zagreb connection index in \(\mathcal{T}(8,2)\).
Consider all trees in \(\mathcal{T}(8,3)\) (as shown in Figure 4). By direct computation, we get the first Zagreb connection index for these trees as follows:
\(ZC{}_{1}(T{}_{1}^{'} =T{}_{8,3}^{* })=86\quad ZC{}_{1}(T{}_{2}^{'} )=50\qquad ZC{}_{1}(T{}_{3}^{'} )=28\qquad ZC{}_{1}(T{}_{4}^{'} )=44\\ ZC{}_{1}(T{}_{5}^{'} )=54\qquad \quad\quad ZC{}_{1}(T{}_{6}^{'} )=56\qquad ZC{}_{1}(T{}_{7}^{'} )=30\qquad ZC{}_{1}(T{}_{8}^{'} )=38\\ ZC{}_{1}(T{}_{9}^{'} )=38\qquad\qquad ZC{}_{1}(T{}_{10}^{'} )=50 \quad\enspace ZC{}_{1}(T{}_{11}^{'} )=36\).
Thus \(T{}_{8,3}^{* }\) has the maximum value of the first Zagreb connection index in \(\mathcal{T}(8,3)\).
Next, we consider the maximum value of the modified first Zagreb connection index in \(\mathcal{T}(n,m)\), by direct computation, we can get \[\begin{aligned} ZC{}_{1}^{\ast}(T_{n,m} ^{*} )&=(n-m)(m-1)+(n-2m+1)(n-m-1)+(m-1)\\&\quad+2(m-1)(n-m-1)\\&=(n-m)(n+m-3). \end{aligned}\]
Theorem 2.3. If \(T\in\mathcal{T}(n,m)\), then we have \[\label{2.3} ZC{}_{1}^{\ast }(T)\leq (n-m)(n+m-3), \tag{2}\] with equality if and only if
(1) \(T\cong S{}_{p,q}\)(depicted in Figure 5) or \(T\cong T_{n,2} ^{*}\), for \(m=2\);
(2) \(T\cong T_{n,m} ^{*}\), for \(3\le m\le \left \lfloor \frac{n}{2}\right \rfloor\).
Proof. (\(1\)) For \(m=2\), we have two possibilities in \(\mathcal{T}(n,2)\), depicted in Figure 6. Since
\[\begin{aligned} ZC_{1}^{*}(T{}_{1}^{* })-ZC_{1}^{*}(T{}_{2}^{* })&=k^{2} +(n-k-2)(k+1)+k(n-k-1)+(n-k-2)^{2}\\&\quad-[k^{2}+k+1+2(n-3) +(n-k-2)+(n-k-3)^{2}]\\&=-2(k^{2}-kn+3k), \end{aligned}\] and \(1\le k\le n-4\), so we get \(ZC_{1}^{*}(T{}_{1}^{* })>ZC_{1}^{*}(T{}_{2}^{* })\), that is when \(T\cong S{}_{p,q}\) or \(T\cong T_{n,2} ^{*}\), \(T\) have the maximum value of \(ZC_{1}^{*}\), for \(m=2\).
(\(2\)) For \(3\le m\le \left \lfloor \frac{n}{2}\right \rfloor\), we will consider the following two cases.
Case 1. If \(\varDelta(T)=2\).
Then \(T\cong P{}_{n}\), we have \(ZC{}_{1}^{* }(P{}_{n})=4n-10\).
If \(n\) is odd, then \(m=\frac{n-1}{2}\), we obtain \[\begin{aligned} ZC{}_{1}^{* }(P{}_{n})-ZC{}_{1}^{*}(T{}_{n,\frac{n-1}2{}}^{* })&=4n-10-\left ( n-\frac{n-1}{2} \right ) \left ( n+\frac{n-1}{2} -3 \right ) \\&=-\frac{1}{4}(n-3)(3n-11)< 0. \end{aligned}\]
If \(n\) is even, then \(m=\frac{n}{2}\), we have \[\begin{aligned} ZC{}_{1}^{*}(P{}_{n})-ZC{}_{1}^{*}(T{}_{n,\frac{n}{2}}^{* })&=4n-10-\left ( n-\frac{n}{2} \right ) \left ( n+\frac{n}{2} -3 \right ) \\&=-\frac{3}{4}(3n-10)(n-4)< 0. \end{aligned}\] Therefore, the inequality in Eq. (2) will be hold.
Case 2. If \(\varDelta(T)\geq3\).
We use induction on \(n\). If \(n=6\), we have \(T\cong T{}_{6,3}^{* }\), Eq. (2) is true. So we assume that Eq. (2) is always true for trees of order at most \(n-1\). Let \(T\in\mathcal{T}(n,m)\), suppose \(P{}_{d+1}=x{}_{1}x{}_{2}\text{···}x{}_{d+1}\) is a longest path in \(T\), where \(d\) is the diameter of \(T\). We know that \(\varDelta(T)\le n-m\) and for every vertex \(x\in V(T)\), \(\tau(x)\leq n-m-1\). Construct \(T^{'}=T-\left \{ x{}_{1}\right \}\).
Subcase 2.1. If \(m{}_{T{}^{'}}=m{}_{T}-1=m-1\).
In this case, we must have \(d{}_{T}(x{}_{2})=2\), \(d{}_{T}(x{}_{2})=d{}_{T{}^{'}}(x{}_{2})+ 1\), \(\tau {}_{T}(x{}_{2})=\tau {}_{T{}^{'}}(x{}_{2})\), \(\tau {}_{T}(x{}_{2})\le n-m-1\), and \(d{}_{T}(x{}_{3})=d{}_{T{}^{'}}(x{}_{3})\), \(d{}_{T}(x{}_{3})\le n-m\), \(\tau {}_{T}(x{}_{3})=\tau {}_{T{}^{'}}(x{}_{3})+1\).
By induction hypothesis, it follows that \[\begin{aligned} ZC{}_{1}^{\ast }(T)&=ZC{}_{1}^{\ast }(T{}^{'})+\tau {}_{T}(x{}_{2})+d{}_{T}(x{}_{3})+1\\&\leq(n-m)(n+m-5)+(n-m-1)+(n-m)+1\\&=(n-m)(n+m-3), \end{aligned}\] equality holds if and only if \(T{}^{'}\cong T{}_{n-1,m-1}\), and also \(x{}_{1}\) is adjacent to \(x{}_{2}\), whose degree is \(2\) in \(T\). Hence, there may be two situations, which is showed in Figure 2. Since \(m{}_{T{}^{'}}=m{}_{T}-1\), we know \(T\cong T_{n,m} ^{*}\).
Subcase 2.2. If \(m{}_{T{}^{'}}=m{}_{T}=m\).
For \(z\in N{}_{T}(x{}_{2})\setminus \left \{ x{}_{1}\right \}\), we have \(d{}_{T}(z)=d{}_{T{}^{'}}(z)\), \(\tau {}_{T}(z)=\tau {}_{T{}^{'}}(z)+1\), \(\tau {}_{T}(x{}_{1})\le n-m-1\), \(\tau {}_{T}(x{}_{2})=\tau {}_{T{}^{'}}(x{}_{2})\) and \(\tau {}_{T}(x{}_{2})\le m-1\).
By induction hypothesis, we obtain \[\begin{aligned} ZC{}_{1}^{\ast }(T)&=ZC{}_{1}^{\ast }(T^{'})+\tau {}_{T}(x{}_{1})+\tau {}_{T}(x{}_{2})+\displaystyle\sum_{z\in N{}_{T}(x{}_{2})\setminus \left \{ x{}_{1}\right \}} d{}_{T}(z)\\&\leq (n-m-1)(n+m-4)+(n-m-1)+(m-1)+(n-2)\\ &=(n-m)(n+m-3), \end{aligned}\] equality holds if and only if \(T{}^{'}\cong T{}_{n-1,m}^{* }\), and \(x{}_{1}\) is adjacent to \(x{}_{2}\), whose degree is \(n-m\) in \(T\). Hence \(T\cong T_{n,m} ^{*}\). ◻
Here we list two examples.
Example 2.4. Consider all five trees \(T\in\mathcal{T}(8,2)\) as shown in Figure 3. By direct computation, we get the modified first Zagreb connection index for these trees as follows:
\(ZC{}_{1}^{* }(T{}_{1}=T{}_{8,2}^{* })=42\quad ZC{}_{1}^{* }(T{}_{2})=34\quad ZC{}_{1}^{* }(T{}_{3}=S{}_{3,3})=42\\ ZC{}_{1}^{* }(T{}_{4}=S{}_{4,2})=42\quad ZC{}_{1}^{* }(T{}_{5})=30\).
Thus \(T{}_{8,2}^{* }\), \(S{}_{3,3}\), \(S{}_{4,2}\) have the maximum value of the modified first Zagreb connection index in \(\mathcal{T}(8,2)\).
Consider all trees \(T\in \mathcal{T}(8,3)\) as shown in Figure 4. It follows from straightforward calculations that we get the modified first Zagreb connection index for these trees as follows:
\(ZC{}_{1}^{* }(T{}_{1}^{'}=T{}_{8,3}^{* })=40\quad ZC{}_{1}^{* }(T{}_{2}^{'})=28\quad\enspace ZC{}_{1}^{* }(T{}_{3}^{'})=24\quad ZC{}_{1}^{* }(T{}_{4}^{'})=34\\\qquad\qquad ZC{}_{1}^{* }(T{}_{5}^{'})=38\qquad\qquad ZC{}_{1}^{* }(T{}_{6}^{'})=36\quad\enspace ZC{}_{1}^{* }(T{}_{7}^{'})=26\quad ZC{}_{1}^{* }(T{}_{8}^{'})=28\\ ZC{}_{1}^{* }(T{}_{9}^{'})=32\qquad\qquad ZC{}_{1}^{* }(T{}_{10}^{'})=32\quad ZC{}_{1}^{* }(T{}_{11}^{'})=30\).
Thus \(T{}_{8,3}^{* }\) has the maximum value of the modified first Zagreb connection index in \(\mathcal{T}(8,3)\).
Finally, we consider the maximum value of the second Zagreb connection index in \(\mathcal{T}(n,m)\).
\[\begin{aligned} ZC{}_{2}{}(T{}^{* })&=\left \lceil \frac{n-2}{2}\right \rceil\left \lceil \frac{n-2}{2}\right \rceil\left \lfloor \frac{n-2}{2}\right \rfloor+\left \lceil \frac{n-2}{2}\right \rceil\left \lfloor \frac{n-2}{2}\right \rfloor\left \lfloor \frac{n-2}{2}\right \rfloor+\left \lceil \frac{n-2}{2}\right \rceil\left \lfloor \frac{n-2}{2}\right \rfloor\\ &=\left \lceil \frac{n-2}{2}\right \rceil\left \lfloor \frac{n-2}{2}\right \rfloor\left (\left \lceil \frac{n-2}{2}\right \rceil+ \left \lfloor \frac{n-2}{2}\right \rfloor+1\right )\\ &=\left \lceil \frac{n-2}{2}\right \rceil\left \lfloor \frac{n-2}{2}\right \rfloor\left (n-1\right ) \\ &=\begin{cases} \frac{1}{4}(n-1){}^{2}(n-3),\quad n\quad is\quad odd;\\ \frac{1}{4}(n-2){}^{2}(n-1), \quad n\quad is\quad even. \end{cases}\\ ZC{}_{2}(T{}^{* * })&=\left ( \left \lceil \frac{n}{2}\right \rceil-1\right )\left ( \left \lceil \frac{n}{2}\right \rceil-2\right )\left ( \left \lfloor \frac{n}{2}\right \rfloor-1\right )+\left ( \left \lceil \frac{n}{2}\right \rceil-1\right )\left ( \left \lfloor \frac{n}{2}\right \rfloor-2\right )\left ( \left \lfloor \frac{n}{2}\right \rfloor-2\right )\\&\quad+\left ( \left \lceil \frac{n}{2}\right \rceil-1\right )\left( \left \lfloor \frac{n}{2}\right \rfloor-1\right )+\left ( \left \lceil \frac{n}{2}\right \rceil-1\right )+\left ( \left \lceil \frac{n}{2}\right \rceil-1\right )\left ( \left \lfloor \frac{n}{2}\right \rfloor-1\right )\\&=\left ( \left \lceil \frac{n}{2}\right \rceil-1\right )\left ( \left \lfloor \frac{n}{2}\right \rfloor{}^{2}+\left \lceil \frac{n}{2}\right \rceil\left \lfloor \frac{n}{2}\right \rfloor-4\left \lfloor \frac{n}{2}\right \rfloor-\left \lceil \frac{n}{2}\right \rceil+5\right )\\&=\begin{cases} \frac{1}{4}(n-1)(n{}^{2}-6n+13),\quad n\quad is\quad odd;\\ \frac{1}{4}(n-2)(n{}^{2}-5n+10), \quad n \quad is\quad even. \end{cases} \end{aligned}\]
Theorem 2.5. If \(T\in\mathcal{T}(n,m)\), then we have
\((1)\) For \(m=2\), \[\label{2.5.1} ZC{}_{2}(T)\le\begin{cases} \frac{1}{4}(n-1){}^{2}(n-3),\quad n\quad is\quad odd,\\ \frac{1}{4}(n-2){}^{2}(n-1), \quad n\quad is\quad even, \end{cases} \tag{3}\] equality holds if and only if \(T\cong T{}^{* }\) (depicted in Figure 7).
\((2)\) For \(m=3\), \[\label{2.5.2} ZC{}_{2}(T)\le\begin{cases} \frac{1}{4}(n-1)(n{}^{2}-6n+13),\quad n\quad is\quad odd,\\ \frac{1}{4}(n-2)(n{}^{2}-5n+10), \quad n \quad is\quad even, \end{cases} \tag{4}\] equality holds if and only if \(T\cong T{}^{** }\) (depicted in Figure 7).
Proof. (1) For \(m=2\), we have two possibilities in \(\mathcal{T}(n,2)\), depicted in Figure 6. It follows that \[\begin{aligned} ZC_{2}(T_{1} ^{*} )-ZC_{2}(T_{2} ^{*} )&=kn^{2} -nk^{2}+k^{2}-3nk+2k-(2k^{2}+n^{2}-2nk-4n+6k+3)\\&=-(1+n)k^{2} +(n^{2}-n-4)k-n^{2} +4n-3. \end{aligned}\]
Since \(1\le k\le n-4\), so we get \(ZC_{2}(T{}_{1}^{* })>ZC_{2}(T{}_{2}^{* })\), and if and only if \(k=\left \lceil \frac{n-2}{2} \right \rceil\) or \(\left \lfloor \frac{n-2}{2} \right \rfloor\), \(ZC_{2}(T_{1} ^{*} )\) have the maximum value, that is \(T^{*}\) (as shown in Figure 8).
(2) For \(m=3\), we first consider tree with the longest path is 4, when \(k\ge s\), it follows that
\[\begin{aligned} ZC_{2}(T_{3} ^{*})-ZC_{2}(T_{4} ^{*}) &=k^{2} (t+1)+(2+t)(t+1)(k+s)+s^{2} (t+1)\\&\quad-[(k+1)^{2} (t+1)+(2+t)(t+1)(k+s)+(s-1)^{2} (t+1)]\\&=2(t+1)(s-k-1), \end{aligned}\] so we get \(ZC_{2}(T{}_{3}^{* })<ZC_{2}(T{}_{4}^{* })\). Similarly, it follows that \(ZC_{2}(T{}_{4}^{* })<ZC_{2}(T{}_{5}^{* })\). \[\begin{aligned} ZC_{2}(T_{5}^{*})-ZC_{2}(T_{6}^{*})&=(n-k-3)(k^{2}+2k+2)+(n-k-3)[(n-k-4)(k+1)+1]\\&\quad-[2k^{2} +6(n-4)+2+2(n-k-5)^{2} ]\\&=(-1-n)k^{2}+(n^{2}-3n-10)k-(n-5)^{2}, \end{aligned}\] since \(1\le k\le n-6\), then we have \(ZC_{2}(T{}_{5}^{* })> ZC_{2}(T{}_{6}^{* })\), that is \(T{}_{5}^{* }\) have the maximum value of \(ZC_{2}\) with the longest path is 4, for \(m=3\).
In the following, we consider tree with the longest path is 5. Similarly, when \(k\ge s\), we obtain \[\begin{aligned} ZC_{2}(T_{7}^{*})-ZC_{2}(T_{8}^{*})&=(k^{2}+tk+t)(t+1)+(k+1)(2t+s+2)+t+s+1+s^{2}\\&\quad-[(k+1)^{2}(t+1)+(k+3)(t+s)+(s-1)^{2}+(t+1)^{2}(k+2)]\\&=-t^{2}-(4+2k)t-k+s-1, \end{aligned}\] then we have \(ZC_{2}(T{}_{7}^{* })< ZC_{2}(T{}_{8}^{* })\), likewise, we obtain \(ZC_{2}(T{}_{8}^{* })<ZC_{2}(T{}_{9}^{* })\), that is \(T{}_{9}^{* }\) have the maximum value of \(ZC_{2}\) with the longest path is 5, for \(m=3\).
Finally, we consider tree with the longest path is 6. When \(k\ge s\), we get \[\begin{aligned} ZC_{2}(T_{10}^{*})-ZC_{2}(T{}_{11}^{*})&=k^{2}+3(k+2t+s+2)+2t(t+1)+s^{2}\\&\quad-[(k+1)^{2}+3(k+2t+s+2)+(s-1)^{2}+2t(t+1)]\\&=2s-2k-2, \end{aligned}\] then we have \(ZC_{2}(T{}_{10}^{* })<ZC_{2}(T{}_{11}^{* })\). Similarly, it follows that \(ZC_{2}(T{}_{11}^{* })<ZC_{2}(T{}_{12}^{* })\), that is \(T{}_{12}^{* }\) have the maximum value of \(ZC_{2}\) with the longest path is 6, for \(m=3\).
\[\begin{aligned} ZC_{2}(T_{5}^{*})-ZC_{2}(T{}_{9}^{*})&=(3-n)k^{2}+(n^{2}-7n+10)k+n^{2}-4n+3\\&\quad-[(4-n)k^{2}+(n^{2}-9n+19)k+n^{2}-6n+11]\\&=-k^{2}+(2n-9)k+2n-8, \end{aligned}\] since \(1\le k\le n-6\), then we have \(ZC_{2}(T{}_{5}^{* })> ZC_{2}(T{}_{9}^{* })\). \[\begin{aligned} ZC_{2}(T_{5}^{*})-ZC_{2}(T{}_{12}^{*})&=(3-n)k^{2}+(n^{2}-7n+10)k+n^{2}-4n+3\\&\quad-[k^{2}+3(2n-k-9)+1+2(n-k-6)(n-k-5)]\\&=-nk^{2}+(n^{2}-3n-9)k-n^{2}+12n-31, \end{aligned}\] since \(1\le k\le n-7\), then we have \(ZC_{2}(T{}_{5}^{* })> ZC_{2}(T{}_{12}^{* })\). Then \(T{}_{5}^{* }\) have the maximum value of \(ZC_{2}\), for \(m=3\). And if and only if \(k=\left \lfloor \frac{n-4}{2} \right \rfloor\), \(ZC_{2}(T_{5} ^{*} )\) have the maximum value, that is \(T^{**}\)(as shown in Figure 7). ◻
Here we list two examples.
Example 2.6. Consider all five trees \(T\in \mathcal{T}(8,2)\) as shown in Figure 3. It follows from straightforward calculations that we get the second Zagreb connection index for these trees as follows:
\(ZC{}_{2}(T{}_{1}=T{}_{8,2}^{* })=35\quad ZC{}_{2}(T{}_{2})=27\quad ZC{}_{2}(T{}_{3}=T{}^{* })=63\\ ZC{}_{2}(T{}_{4})=56\qquad \qquad ZC{}_{2}(T{}_{5})=23\).
Thus \(T{}^{* }\) has the maximum value of the second Zagreb connection index in \(\mathcal{T}(8,2)\).
Consider all trees \(T\in \mathcal{T}(8,3)\) as shown in Figure 4. By direct computation, we get the second Zagreb connection index for these trees as follows:
\(ZC{}_{2}(T{}_{1}^{'}=T{}_{8,3}^{* })=48\quad \enspace ZC{}_{2}(T{}_{2}^{'})=24\qquad ZC{}_{2}(T{}_{3}^{'})=20\quad ZC{}_{2}(T{}_{4}^{'})=40\quad \\ ZC{}_{2}(T{}_{5}^{'}=T^{**})=51\quad\enspace ZC{}_{2}(T{}_{6}^{'})=44\qquad ZC{}_{2}(T{}_{7}^{'})=24\quad ZC{}_{2}(T{}_{8}^{'})=26\\ ZC{}_{2}(T{}_{9}^{'})=36\quad \quad\qquad ZC{}_{2}(T{}_{10}^{'})=34\quad\enspace \enspace ZC{}_{2}(T{}_{11}^{'})=33\).
Thus \(T{}^{** }\) has the maximum value of the second Zagreb connection index in \(\mathcal{T}(8,3)\).
\[ZC_{2}(T_{n,m}^{**})= \begin{cases} \frac{n-1}{4}(n^{2}-2mn+2m^{2}-5), n\quad is\quad odd; \\ \frac{n-2}{4}(n^{2}-2mn+2m^{2}-2+n-2m),n\quad is\quad even. \end{cases}\] \[ZC_{2}(T_{n,m}^{''})= \begin{cases} \frac{n-1}{4}(n^{2}-2mn+2m^{2}-5), n\quad is\quad odd; \\ \frac{n}{4}(n^{2}-2mn+2m^{2}-8-n+2m),n\quad is\quad even. \end{cases}\]
When \(n=10,m=4\), it follows from straightforward calculations that \(ZC_{2}(T_{1} ^{\star })=ZC_{2}(T_{10,4}^{\ast })\) is the largest, that is \(T_{10,4}^{*}\) has the maximum value in \(\mathcal{T}(10,4)\); When \(n=11,m=4\), \(ZC_{2}(T_{2} ^{\star })=ZC_{2}(T_{11,4}^{\ast\ast })=ZC_{2}(T_{11,4}^{\prime \prime })\) is the largest, that is \(T_{11,4}^{\ast\ast }\cong T_{11,4}^{\prime \prime }\) has the maximum value in \(\mathcal{T}(11,4)\); Similarly, \(T_{3} ^{\star }\cong T_{12,5}^{\ast }\) has the maximum value in \(\mathcal{T}(12,5)\); \(T_{4} ^{\star }\cong T_{13,4}^{\ast \ast}\cong T_{13,4}^{\prime \prime }\) has the maximum value in \(\mathcal{T}(13,4)\). When \(n=13,m=5\), we have \(ZC_{2}(T_{5} ^{\star })=ZC_{2}(T_{6} ^{\star })\), so \(T_{5} ^{\star }\cong T_{13,5}^{\ast }\) and \(T_{6} ^{\star }\cong T_{13,5}^{\ast\ast }\cong T_{13,5}^{\prime \prime }\) have the maximum value in \(\mathcal{T}(13,5)\). Therefore, we have the following conjecture.
Conjecture 3.1. If \(T\in\mathcal{T}(n,m)\), \(4\le m\le \left \lfloor \frac{n}{2}\right \rfloor\), it follows that the maximum value of the second Zagreb connection index is \(ZC_{2}(T_{n,m}^{*})\) or \(ZC_{2}(T_{n,m}^{**})\) or \(ZC_{2}(T_{n,m}^{''})\). In particular,
(1) For \(n=2m+1\), \[\begin{aligned} ZC_{2}(T)&\le m(m-1)(m+2). \end{aligned}\] The equality holds if and only if \(T\cong T_{n,m}^{*}\cong T_{n,m}^{**}\cong T_{n,m}^{''}\)(depicted in Figure 9), that is \(T\cong T_{2m+1,m}^{*}\) (depicted in Figure 10).
(2) For \(n=2m+2\), \[\begin{aligned} ZC_{2}(T)&\le(m-1)(m+1)(m+3). \end{aligned}\] The equality holds if and only if \(T\cong T_{n,m}^{*}\cong T_{n,m}^{''}\) (depicted in Figure 9), that is \(T\cong T_{2m+2,m}^{*}\) (depicted in Figure 10).
This conjecture maybe correct, for example, we list some special cases.
\(ZC_{2}(T_{12}^{'}=T_{18,7}^{*})=720\quad \enspace ZC_{2}(T_{13}^{'}=T_{18,7}^{**})=688\qquad ZC_{2}(T_{14}^{'}=T_{18,7}^{''})=711\\ ZC_{2}(T_{15}^{'})=651\qquad \qquad\enspace\enspace ZC_{2}(T_{16}^{'})=217\qquad \qquad\quad\enspace ZC_{2}(T_{17}^{'})=206\\ ZC_{2}(T_{18}^{'}=T_{20,4}^{*})=765\quad \enspace ZC_{2}(T_{19}^{'}=T_{20,4}^{''})=1260\quad \enspace ZC_{2}(T_{20}^{'}=T_{20,4}^{**})=1269\\ ZC_{2}(T_{21}^{'})=1248\qquad\quad\enspace\enspace\enspace ZC_{2}(T_{22}^{'})=1249\qquad\qquad\enspace\enspace ZC_{2}(T_{23}^{'})=1118\\ ZC_{2}(T_{24}^{'})=1019\qquad\qquad\enspace ZC_{2}(T_{25}^{'})=837\qquad\qquad\enspace\enspace\enspace ZC_{2}(T_{26}^{'})=691\).
The authors are thankful to the anonymous referee and the handling editor for their valuable comments and suggestions which improve the previous version of the paper.
No potential conflict of interest was reported by the authors.