Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Steiner Wiener index of trees with a given segment sequence
154
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 vertex 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{cases} 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$ are 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}$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
