Extremal problems for degree-based topological indices

详细信息    查看全文

• 作者：Yunfang Tang^a ; ^{tangyunfang8530@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Douglas B. West^b ; ^c ; ^{dwest@math.uiuc.edu" class="auth_mail" title="E-mail the corresponding author} ; Bo Zhou^d ; ^{zhoubo@scnu.edu.cn" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Sum-connectivity index ; Quasi-tree ; Topological index
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：20 April 2016
• 年：2016
• 卷：203
• 期：Complete
• 页码：134-143
• 全文大小：418 K

文摘

For a graph G$G$, let $\sigma \left(G\right)={\sum }_{uv\in E\left(G\right)}\frac{1}{\sqrt{d_G\left(u\right)+d_G\left(v\right)}}$; this defines the sum-connectivity index  σ(G)$\sigma \left(G\right)$. More generally, given a positive function t$t$, the edge-weight  t$t$-index  t(G)$t\left(G\right)$ is given by t(G)=∑_uv∈E(G)t(ω(uv))$t\left(G\right)={\sum }_{uv\in E\left(G\right)}t\left(\omega \left(uv\right)\right)$, where ω(uv)=d_G(u)+d_G(v)$\omega \left(uv\right)=d_G\left(u\right)+d_G\left(v\right)$. We consider extremal problems for the t$t$-index over various families of graphs. The sum-connectivity index satisfies the conditions imposed on t$t$ in each extremal problem, with a small exception.

Minimization:   When t$t$ is decreasing, and (z−1)t(z)$(z-1)t\left(z\right)$ is increasing and subadditive, the star is the unique graph minimizing the t$t$-index over a62b5a946ef9c245888a" title="Click to view the MathML source">n$n$-vertex graphs with no isolated vertices. When also t$t$ has positive second derivative and negative third derivative, and (z−1)t(z)$(z-1)t\left(z\right)$ is strictly concave, the connected a62b5a946ef9c245888a" title="Click to view the MathML source">n$n$-vertex non-tree with least t$t$-index is obtained from the star by adding one edge.

Maximization:   When t$t$ is decreasing, convex, and satisfies t(3)−t(4)<t(4)−t(6)$t\left(3\right)-t\left(4\right)<t\left(4\right)-t\left(6\right)$, the path and cycle are the unique a62b5a946ef9c245888a" title="Click to view the MathML source">n$n$-vertex tree and unicyclic graph with largest t$t$-index. When also t(4)−t(5)≤2[t(6)−t(7)]$t\left(4\right)-t\left(5\right)\le 2[t\left(6\right)-t\left(7\right)]$, and t(k+1)−t(k+2)−t(k+j)$t(k+1)-t(k+2)-t(k+j)$ increases with 47a50e6f5" title="Click to view the MathML source">k$k$ for j≤3$j\le 3$, we determine the a62b5a946ef9c245888a" title="Click to view the MathML source">n$n$-vertex quasi-trees with largest t$t$-index, where a quasi-tree   is a graph yielding a tree by deleting one vertex. The maximizing quasi-trees consist of an a62b5a946ef9c245888a" title="Click to view the MathML source">n$n$-cycle plus chords from one vertex to some number c$c$ of consecutive vertices (for the sum-connectivity index, c=min{30,n−3}$c=min\{30,n-3\}$). Finally, we show that whenever t$t$ is decreasing and zt(z)$zt\left(z\right)$ is strictly increasing, an a62b5a946ef9c245888a" title="Click to view the MathML source">n$n$-vertex graph with maximum degree 47a50e6f5" title="Click to view the MathML source">k$k$ has t$t$-index at most $\frac{1}{2}nkt\left(2k\right)$, with equality only for 47a50e6f5" title="Click to view the MathML source">k$k$-regular graphs.