| Sbornik: Mathematics |
|
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper) On diameter N. A. Kuz'min, D. S. Malyshev National Research University Higher School of Economics, Nizhnii Novgorod, Russia
Bibliographic databases:
     § 1. IntroductionChemical compounds are often represented by molecular graphs, whose vertices correspond to atoms and edges are labelled with the types of bounds. Using this approach the properties of chemical compounds can be described in terms of topological indices, that is, graph parameters which are invariant under redesignations of vertices and which enable one to carry out an analytic investigation of some aspects of the chemical structure of the compound. In this work we consider only simple graphs, that is, undirected unlabelled graphs without loops and multiple edges. A matching in a graph is an arbitrary (perhaps, empty) set of pairwise nonadjacent edges. The Hosoya topological index of a graph $G$, which was introduced in the pioneering paper [1], is defined as the number of matchings in $G$ and denoted by $z(G)$. The values of the Hosoya index determine some physico-chemical properties of the corresponding chemical compounds, in particular, the boiling point of alkanes or the energy of conjugated $\pi$-electron systems: see, for example, [2]–[4]. Since topological indices determine some or other kinds of energy of chemical compounds, the problem of identifying graphs belonging to prescribed classes and having an extremal (minimum or maximum) value of one topological index or another is of particular interest. Recall that the eccentricity of a vertex of a graph is the maximum distance between this and other vertices of the graph. The radius and diameter of a graph are the minimum and maximum eccentricity of its vertices, respectively. It is obvious that the only $n$-vertex tree of radius $1$ is the $n$-star, which has exactly $n$ matchings. The problem of finding diameter $3$ trees of prescribed size with the maximum value of the Hosoya index is also trivial. In [5] all trees of radius $2$ on $n$ vertices with the maximum number of matchings were completely described. In this work we consider and solve the problem of maximizing the Hosoya index for $n$-vertex trees of diameter $5$, which has still been open to the authors’ knowledge. Any $n$-vertex tree of diameter $5$ with the maximum number of matchings is said to be maximal. It turns out that for any $n\geqslant 5$ such a tree is unique. § 2. Some definitions, notation and factsRecall that a leaf in a graph is a vertex of degree 1. A central vertex of a graph is a vertex with minimum eccentricity. A leaf adjacent to a central vertex in a graph is called a central leaf. The centre of a graph is the set of all of its central vertices. By Jordan’s theorem the centre of a tree consists of a single vertex or of two adjacent vertices. The number of matchings (including the empty one) in a graph $G$ is denoted by $z(G)$. Let $A,B\subseteq V(G)$ and $A\cap B=\varnothing$. We denote by $z(G,A,B)$ the number of matchings in the graph $G$ that contain all vertices of $A$ and no vertex of $B$. Let $G$ be a graph and $H$ be its subgraph. Any subset $S\subseteq V(H)$ such that no vertex in $V(G)\setminus V(H)$ is adjacent to a vertex of $V(H)\setminus S$ is said to be $H$-separating. Given an $H$-separating set $S$, denote the graph $((V(G)\setminus V(H))\cup S,E(G)\setminus E(H))$ by $G_S$. The following assertion was proved in [6] (see [6], Lemma 1). Assume that two graphs $G^1$ and $G^2$ contain subgraphs $H_1$ and $H_2$ and the following two conditions are simultaneously valid:
Thereby the equality $z(G^1_S,S',S\setminus S')=z(G^2_S,S',S\setminus S')$ is satisfied for any $S'\subseteq S$. If $z(H_2\setminus S')\geqslant z(H_1\setminus S')$ for any subset $S'$ of $ S$ and there exists $\widetilde{S'}\subseteq S$ such that
$$
\begin{equation*}
z(H_2\setminus \widetilde{S'})>z(H_1\setminus \widetilde{S'})\quad\text{and}\quad z(G^1_S,\widetilde{S'},S\setminus \widetilde{S'})\neq 0,
\end{equation*}
\notag
$$
then it follows from Lemma 2.1 that $z(G^2)>z(G^1)$. This observation turns out to be useful in proving that some graph transformations increase the Hosoya index. This remark and some related concepts are put into use below.
§ 3. Formulation of the main resultsConsider a diameter 5 tree shown in Figure 1. To be clear, we mean $l_i\in \{0,1\}$, where $l_i=1$ if and only if the corresponding leaf is contained in the tree. By $a_i$ and $b_i$ we denote the number of the corresponding occurrences of 2-paths and 3-paths in the tree. 3.1. A description of maximal trees for $n\geqslant 105$For $n\geqslant 105$ the following assertion holds. Theorem 3.1. Let $n=6k+(3l+m)$, where $l \in \{0, 1\}$ and $ m \in \{0, 1, 2\}$. If ${n \,{\geqslant}\, 105}$, then the maximal $n$-vertex tree of diameter 5 is unique and has the form shown in Figure 1, where 3.2. A description of maximal trees for $n\leqslant 104$For $n \leqslant 5$ there exist no trees of diameter 5. To identify maximal trees for $6 \leqslant n\leqslant 104$ we have conducted a computational experiment and established the optimal integer values of $l_1$, $l_2$, $a_1$, $a_2$, $b_1$ and $b_2$. It was found out that the central leaf in a maximal tree can only appear for $6 \leqslant n \leqslant 13$; the corresponding values of the parameters are presented in Table 1. Table 1.The values of the parameters corresponding to maximal trees for $6\leqslant n\leqslant 13$ For $14 \leqslant n \leqslant 104$ there are no central leaves in the tree; in other words, ${l_1=l_2=0}$. The corresponding optimal values of the parameters are presented in Table 2. Table 2.The values of the parameters corresponding to maximal trees for $14\leqslant n\leqslant 104$ § 4. Some known graph transformations that increase the Hosoya indexIn [5] the following graph transformations were proposed and the corresponding results were established (see [5], Lemmas 3.1, 3.4, and 3.5). Assume that the graph $G_1$ consists of subgraphs $G'_S$, $G''_S$ and a 3-path $H_1=(v,s_2,s_1)$ separated by vertices $s_1$ and $s_2$ from these subgraphs, and the graph $G_2$ consists of subgraphs $G'_S$, $G''_S$ and a 3-path $H_2=(s_2,v,s_1)$ separated by vertices $s_1$ and $s_2$ from these subgraphs, as shown in Figure 2. Let the graph $G_1$ consist of a subgraph $G_S$ and a star $H_1$ with $q+1$ leaves separated by a vertex $s_1$ from this subgraph (Figure 3). In the case of an even value of $q$ the graph $G_2$ consists of a subgraph $G_S$ and a subgraph $H_2$ separated from $G_S$ by a vertex $s_1$, as shown in Figure 4. In the case of an odd value of $q$ the graph $G_2$ consists of a subgraph $G_S$ and a subgraph $H_2$ separated from $G_S$ by a vertex $s_1$, as shown in Figure 5. § 5. Some new graph transformations that increase the Hosoya indexAssume that the graph $G_1$ consists of a subgraph $G_s$ and a 4-path $H_1$ separated by vertices $s_1$ and $s_2$ from this subgraph, and the graph $G_2$ consists of a subgraph $G_s$ and a 4-path $H_2$ separated by vertices $s_1$ and $s_2$ from the subgraph, as is shown in Figure 6. Proof. It is easily verified that
$$
\begin{equation*}
\begin{gathered} \, z(H_1)=z(H_2)=5, \qquad z(H_1 \setminus s_2) =z(H_1 \setminus s_1)=z(H_2 \setminus s_2)=2, \\ z(H_2 \setminus s_1)=3, \qquad z(H_1 \setminus \{s_1, s_2\})=1\quad\text{and} \quad z(H_2 \setminus \{s_1, s_2\})=2. \end{gathered}
\end{equation*}
\notag
$$
Then by Lemma 2.1 The proof is complete. Assume that the graph $G_1$ consists of a subgraph $G_s$ and a fork $H_1$ separated by a vertex $s_1$ from the subgraph, and the graph $G_2$ consists of a subgraph $G_s$ and a 5-path $H_2$ separated by a vertex $s_1$ from the subgraph, as shown in Figure 7. Proof. It is easily verified that
$$
\begin{equation*}
z(H_1)=7, \qquad z(H_2)=8, \qquad z(H_1 \setminus s_1)=3\quad\text{and} \quad z(H_2 \setminus s_1)= 4.
\end{equation*}
\notag
$$
Then by Lemma 2.1
The proof is complete. Assume that the graph $G_1$ consists of a subgraph $G_s$ and a subgraph $H_1$ separated from $G_s$ by vertices $s_1$ and $s_2$, and the graph $G_2$ consists of a subgraph $G_s$ and a subgraph $H_2$ separated from $G_s$ by vertices $s_1$ and $s_2$, as shown in Figure 8. Proof. It is easily verified that
$$
\begin{equation*}
\begin{gathered} \, z(H_1)=11, \quad z(H_2)=13, \quad z(H_1 \setminus s_1)=z(H_2 \setminus s_1)=6, \quad z(H_1 \setminus s_2)=4, \\ z(H_2 \setminus s_2)=6,\quad z(H_1 \setminus \{s_1, s_2\})=3\quad\text{and} \quad z(H_2 \setminus \{s_1, s_2\})=4. \end{gathered}
\end{equation*}
\notag
$$
Then by Lemma 2.1 we have The proof of the lemma is complete. § 6. Properties of maximal trees of diameter 56.1. The structure of maximal trees of diameter 5 and some of its propertiesIt follows from Lemmas 4.1–4.3 that each maximal tree of diameter 5 has the form presented in Figure 1. Denote the Hosoya index of such tree by $f(l_1,l_2,a_1,a_2,b_1,b_2)$. It is obvious that if such a tree has $n$ vertices, then Lemma 6.1. Any maximal tree possesses the following properties. 1. If the tree contains a central leaf, then this leaf is unique and $b_1=b_2=0$. 2. If $n$ is even, then the tree contains no central leaves. Proof. It follows from Lemma 5.1 that for any maximal tree either $l_1=0$ or $l_2=0$. If the tree does have a central leaf, then it can be assumed that $l_1=1$. It follows from Lemmas 5.2 and 5.3 that $b_1=b_2=0$. Substituting these values into (6.1) we obtain $2a_1+2a_2=n-3$, which is impossible in the case of an even value of $n$. The proof is complete. 6.2. The case of a central leafAssume that $l_1=1$. Then by Lemma 8 we have $l_2=0$, $b_1=b_2=0$ and $n$ is odd. Let $n=4k+r$, where $r \in \{1, 3\}$, and let $g(a_1, a_2)=f(1, 0, a_1, a_2, 0, 0)$. Then the problem of identifying maximal trees that contain a central leaf (provided that such trees exist) reduces to searching for the maximum value of the function $g$ under the constraint It is easily verified that the following relation is valid: Substituting $a_1=(n-3)/{2}-a_2$ into the expression for $g$ gives
$$
\begin{equation*}
g(a_2)=2^{(n-3)/2-2}\biggl (-a_2^2+\biggl (2+\frac{n-3}{2}\biggr) a_2+ (n+9)\biggr).
\end{equation*}
\notag
$$
Obviously, this function attains its maximum for $a_2=1+(n-3)/4$. The direct substitution of this value into the function proves the following assertion. Lemma 6.2. Under the constraint (6.2) the following inequality holds: 6.3. The case of no central leavesLet $g(a_1, a_2, b_1, b_2)=f(0, 0, a_1, a_2, b_1, b_2)$. Then the problem of identifying maximal trees that contain no central leaves (provided that such trees exist) reduces to searching for the maximum of the function $g$ under the constraint Without loss of generality it can be assumed that $a_1 \geqslant a_2$. Therefore, this inequality is assumed to hold throughout this subsection. It is easily seen that the following relation holds:
$$
\begin{equation*}
g(a_1, a_2, b_1, b_2)=2^{a_1+a_2-2} 3^{b_1+b_2-2}\bigl((3a_1+2b_1+6) (3a_2+2b_2+6)+36\bigr).
\end{equation*}
\notag
$$
Proof. It is easily verified that As $a_1 \geqslant a_2$ and $b_1 \geqslant b_2$, we have This yields the inequality $g(a_1, a_2, b_2, b_1)-g(a_1, a_2, b_1, b_2) \geqslant 0$. The proof of the lemma is complete. We assume below that $b_2 \geqslant b_1$. We also introduce the notation $c_1=a_1-a_2$ and $c_2=b_2-b_1$. Lemma 6.4. The following assertions hold. 1. If $c_1 >(2/3)c_2+1$, then $g(a_1-1, a_2+1, b_1, b_2) > g(a_1, a_2, b_1, b_2)$. 2. If $c_1 < (2/3)c_2-1$, then $g(a_1+1, a_2-1, b_1, b_2) > g(a_1, a_2, b_1, b_2)$. 3. If $c_1 > (2/3)(c_2+1)$, then $g(a_1, a_2, b_1-1, b_2+1) > g(a_1, a_2, b_1, b_2)$. 4. If $c_1 < (2/3)(c_2-1)$, then $g(a_1, a_2, b_1+1, b_2-1) > g(a_1, a_2, b_1, b_2)$. Proof. It is easily verified that Obviously, $3(a_1-a_2-1)-2(b_2-b_1)=3(c_1-1)-2c_2 > 0$. Assertions 2–4 are established in the same way. The proof of the lemma is complete. Let $x_k=(a_1-k, a_2+k, b_1, b_2)$, $c_1(x_k)=(a_1-k)-(a_2+k)$. It is obvious that $c_1(x_{k-1})- 2=c_1(x_k)$. If $c_1(x_0) > \frac{2}{3}c_2+1$, then by part 1 of Lemma 6.4 there exists $k$ such that $\frac{2}{3}c_2-1 \leqslant c_1(x_k) \leqslant \frac{2}{3}c_2+1$ and $g(x_k) > g(x_0)$. At the same time, let $y_k=(a_1+k, a_2-k, b_1, b_2)$ and $c_1(y_k)=(a_1+k)-(a_2-k)$. Clearly, $c_1(y_{k-1})+2=c_1(y_k)$. If $c_1(y_0) < \frac{2}{3}c_2-1$, then by part 2 of Lemma 6.4 there exists $k$ such that $\frac{2}{3}c_2-1 \leqslant c_1(y_k) \leqslant \frac{2}{3}c_2+1$ and $g(y_k) > g(y_0)$. Thus we have shown that for any tuple of parameters $x=(a_1, a_2, b_1, b_2)$ such that $c_1 \notin [\frac{2}{3}c_2-1, \frac{2}{3}c_2+1]$ there exists another tuple $x'=(a'_1, a'_2, b'_1, b'_2)$ such that $c'_1 \in [\frac{2}{3}c'_2-1, \frac{2}{3}c'_2+1]$ and $g(x') > g(x)$. This means that for any optimal tuple of parameters $(a_1, a_2, b_1, b_2)$
$$
\begin{equation}
\frac{2}{3}\, c_2-1 \leqslant c_1 \leqslant \frac{2}{3}\, c_2+1.
\end{equation}
\tag{6.3}
$$
Similarly, using parts 3 and 4 of Lemma 6.4 it can be shown that for any such tuple the following inequality is also satisfied:
$$
\begin{equation}
\frac{2}{3}(c_2-1) \leqslant c_1 \leqslant \frac{2}{3}(c_2+1).
\end{equation}
\tag{6.4}
$$
It is clear that (6.4) implies (6.3). By the definition of $c_1$ and $c_2$ inequality (6.4) is equivalent to the relation
$$
\begin{equation*}
3a_2+2b_2-2 \leqslant 3a_1+2b_1 \leqslant 3a_2+2b_2+2 .
\end{equation*}
\notag
$$
Proof. It is obvious that Since $n-2=2a_1+2a_2+3b_1+3b_2$, we obtain The proof of the lemma is complete. Lemma 6.7. If $n \geqslant 122$, $a_1 \geqslant 2$, $a_2 \geqslant 1$ and inequality (6.5) is satisfied, then Proof. It is easily verified that
$$
\begin{equation*}
\begin{aligned} \, &\frac{g(a_1-2, a_2-1, b_1+1, b_2+1)-g(a_1, a_2, b_1, b_2)}{2^{a_1+a_2-5}\, 3^{b_1+b_2- 2}} \\ &\qquad=(3a_1+2b_1-3) (3a_2+2b_2-30)-252. \end{aligned}
\end{equation*}
\notag
$$
By Lemma 6.6 we have $(3a_1+2b_1)+(3a_2+2b_2)\geqslant 80$. Then (6.5) yields ${(3a_1+2b_1)\geqslant 39}$, $(3a_2+2b_2) \geqslant 38$. Thus, we have the inequality $(3a_1+2b_1-3) (3a_2+2b_2-30) \geqslant 280$. The proof is complete. Lemma 6.8. If $n \geqslant 137$, $a_1 \geqslant 3$ and inequality (6.5) is satisfied, then Proof. It is easily verified that
$$
\begin{equation*}
\frac{g(a_1-3, 0, b_1+1, b_2+1)-g(a_1, 0, b_1, b_2)}{2^{a_1-5}\, 3^{b_1+b_2-2}} = (3a_1+2b_1- 57) (2b_2+24)+1044.
\end{equation*}
\notag
$$
By Lemma 6.6 we have $(3a_1+2b_1)+2b_2 \geqslant 90$. Then (6.5) yields ${(3a_1+2b_1-57)\geqslant -14}$. Then $(3a_1+2b_1-57) (2b_2+24) \geqslant-994$. The proof is complete. § 7. Proof of Theorem 3.1Assume that a maximal tree contains no central leaves and $a_1 \geqslant a_2$. Then by Lemmas 6.7 and 6.8 we have $(a_1, a_2) \in \{(0, 0), (1, 0), (1, 1), (2, 0)\}$, and therefore $c_1 \in \{0, 1, 2\}$. It follows from (6.5) that if $c_1=0$, then $c_2 \in \{0, 1\}$, if $c_1=1$, then $c_2 \in \{1, 2\}$, and if $c_1=2$, then $c_2 \in \{2, 3, 4\}$. Let $n=6k+r$, where $r \in \{0, 1, 2, 3, 4, 5\}$; then $2a_1+2a_2+3b_1+3b_2=6k+r-2$. If $r=0$, then with regard to the fact that $b_1$ and $b_2$ are integers, we have either $a_1=a_2=1$, and then $b_1=b_2=k- 1$, or $a_1=2$, $a_2=0$, and then by Lemma 6.3 either $b_1=k-2$ and $b_2=k$, or $b_1=k-3$ and $b_2=k+1$. It is easily verified that
$$
\begin{equation*}
\begin{gathered} \, g(2, 0, k-2, k)=g(2, 0, k-3, k+1)=3^{2k-4} \bigl((2k+8) (2k+6)+36\bigr), \\ g(1, 1, k-2, k)=3^{2k-4} ((2k+7)^2+36). \end{gathered}
\end{equation*}
\notag
$$
It is obvious that If $r=1$, then with regard to the fact that $b_1$ and $b_2$ are integers we obtain $a_1=1$ and $a_2=0$, and by Lemma 6.3 we have $b_1=k-1$ and $b_2=k$. If $r=2$, then with regard to the fact that $b_1$ and $b_2$ are integers we obtain $a_1=a_2=0$, and then $b_1=b_2=k$. If $r=3$, then with regard to the fact that $b_1$ and $b_2$ are integers we have either $a_1=a_2=1$, and then $b_1=b_2=k- 1$, or $a_1=2$ and $a_2=0$, and then $b_1=k-2$ and $b_2=k+1$ by Lemma 6.3. It is easily verified that and
$$
\begin{equation*}
g(1, 1, k-2, k)=3^{2k-4}\bigl((2k+7) (2k+9)+36\bigr).
\end{equation*}
\notag
$$
This yields the inequality If $r=4$, then with regard to the fact that $b_1$ and $b_2$ are integers we obtain $a_1=1$ and $a_2=0$, and then $b_1=k-1$ and $b_2=k+1$ by Lemma 6.3. If $r=5$, then with regard to the fact that $b_1$ and $b_2$ are integers we obtain $a_1=a_2=0$, and then $b_1=k$ and $b_2=k+1$ by Lemma 6.3. Now by Lemma 8 and the above we obtain the result of the theorem for $r\,{\in}\, \{0, 2, 4\}$. If $r \in \{1, 3, 5\}$, then by Lemma 8 a maximal tree can contain at most one central leaf, so we compare the corresponding maximum values of the function $g$. Recall that by Lemma 6.2 If $r=1$, then by what we proved above the maximum value of $g$ is
$$
\begin{equation*}
g(1, 0, k-1, k)=\frac{1}{2}\, 3^{(n-16)/3} (n^2+37n+664).
\end{equation*}
\notag
$$
If $r=3$, then by what we proved above the maximum value of $g$ is If $r=5$, then by what we proved above the maximum value of $g$ is
$$
\begin{equation*}
g(0, 0, k, k+1)=\frac{1}{4}\, 3^{(n-14)/3} (n^2+32n+521).
\end{equation*}
\notag
$$
It is easily verified that for $n \geqslant 127$ we have
$$
\begin{equation*}
g_l(a_1, a_2)< g(1, 0, k-1, k), g(2, 0, k-2, k), g(0, 0, k, k+1).
\end{equation*}
\notag
$$
Thus, the theorem has been proved for $n \geqslant 137$. Computer calculations show that the theorem is even true for $n \geqslant 105$. The proof is complete.
Citation in format AMSBIB
\Bibitem{KuzMal23} |
|
||||||||||||||||||||
|
Contact us: |
Terms of Use
|
Registration to the website |
Logotypes |
|