ترغب بنشر مسار تعليمي؟ اضغط هنا

The Steiner Wiener index of trees with a given segment sequence

154   0   0.0 ( 0 )
 نشر من قبل Xiao-Dong Zhang Prof.
 تاريخ النشر 2020
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

The Steiner distance of vertices in a set $S$ is the minimum size of a connected subgraph that contain these vertices. The sum of the Steiner distances over all sets $S$ of cardinality $k$ is called the Steiner $k$-Wiener index and studied as the natural generalization of the famous Wiener index in chemical graph theory. In this paper we study the extremal structures, among trees with a given segment sequence, that maximize or minimize the Steiner $k$-Wiener index. The same extremal problems are also considered for trees with a given number of segments.



قيم البحث

اقرأ أيضاً

170 - Heesung Shin , Jiang Zeng 2010
For a labeled tree on the vertex set $set{1,2,ldots,n}$, the local direction of each edge $(i,j)$ is from $i$ to $j$ if $i<j$. For a rooted tree, there is also a natural global direction of edges towards the root. The number of edges pointing to a ve rtex is called its indegree. Thus the local (resp. global) indegree sequence $lambda = 1^{e_1}2^{e_2} ldots$ of a tree on the vertex set $set{1,2,ldots,n}$ is a partition of $n-1$. We construct a bijection from (unrooted) trees to rooted trees such that the local indegree sequence of a (unrooted) tree equals the global indegree sequence of the corresponding rooted tree. Combining with a Prufer-like code for rooted labeled trees, we obtain a bijective proof of a recent conjecture by Cotterill and also solve two open problems proposed by Du and Yin. We also prove a $q$-multisum binomial coefficient identity which confirms another conjecture of Cotterill in a very special case.
A graph is called integral if all eigenvalues of its adjacency matrix consist entirely of integers. We prove that for a given nullity more than 1, there are only finitely many integral trees. It is also shown that integral trees with nullity 2 and 3 are unique.
The Wiener index of a graph $G$, denoted $W(G)$, is the sum of the distances between all pairs of vertices in $G$. E. Czabarka, et al. conjectured that for an $n$-vertex, $ngeq 4$, simple quadrangulation graph $G$, begin{equation*}W(G)leq begin{cas es} frac{1}{12}n^3+frac{7}{6}n-2, &text{ $nequiv 0~(mod 2)$,} frac{1}{12}n^3+frac{11}{12}n-1, &text{ $nequiv 1~(mod 2)$}. end{cases} end{equation*} In this paper, we confirm this conjecture.
Let $Sz(G),Sz^*(G)$ and $W(G)$ be the Szeged index, revised Szeged index and Wiener index of a graph $G.$ In this paper, the graphs with the fourth, fifth, sixth and seventh largest Wiener indices among all unicyclic graphs of order $ngeqslant 10$ ar e characterized; as well the graphs with the first, second, third, and fourth largest Wiener indices among all bicyclic graphs are identified. Based on these results, further relation on the quotients between the (revised) Szeged index and the Wiener index are studied. Sharp lower bound on $Sz(G)/W(G)$ is determined for all connected graphs each of which contains at least one non-complete block. As well the connected graph with the second smallest value on $Sz^*(G)/W(G)$ is identified for $G$ containing at least one cycle.
The Wiener index of a connected graph is the summation of all distances between unordered pairs of vertices of the graph. In this paper, we give an upper bound on the Wiener index of a $k$-connected graph $G$ of order $n$ for integers $n-1>k ge 1$: [W(G) le frac{1}{4} n lfloor frac{n+k-2}{k} rfloor (2n+k-2-klfloor frac{n+k-2}{k} rfloor).] Moreover, we show that this upper bound is sharp when $k ge 2$ is even, and can be obtained by the Wiener index of Harary graph $H_{k,n}$.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا