Let $G$ be a connected graph of order $n$.The Wiener index $W(G)$ of $G$ is
the sum of the distances between all unordered pairs of vertices of $G$. In
this paper we show that the well-known upper ...bound $\big(
\frac{n}{\delta+1}+2\big) {n \choose 2}$ on the Wiener index of a graph of
order $n$ and minimum degree $\delta$ M. Kouider, P. Winkler, Mean distance
and minimum degree. J. Graph Theory 25 no. 1 (1997) can be improved
significantly if the graph contains also a vertex of large degree.
Specifically, we give the asymptotically sharp bound $W(G) \leq
{n-\Delta+\delta \choose 2} \frac{n+2\Delta}{\delta+1}+ 2n(n-1)$ on the Wiener
index of a graph $G$ of order $n$, minimum degree $\delta$ and maximum degree
$\Delta$. We prove a similar result for triangle-free graphs, and we determine
a bound on the Wiener index of $C_4$-free graphs of given order, minimum and
maximum degree and show that it is, in some sense, best possible.
The Wiener index of a strong digraph D is defined as the sum of the shortest path distances between all ordered pairs of vertices. This definition has been extended to digraphs that are not ...necessarily strong by defining the distance from a vertex a to a vertex b as 0 if there is no path from a to b in D.
Knor et al. (2016) 9 considered (not necessarily strong) orientations of graphs with maximum Wiener index. The authors conjectured that for a given tree T, an orientation D of T of maximum Wiener index always contains a vertex v such that for every vertex u, there is either a (u,v)-path or a (v,u)-path in D. In this paper we disprove the conjecture.
We also show that the problem of finding an orientation of maximum Wiener index of a given graph is NP-complete, thus answering a question by Knor et al. (2016) 8.
We briefly discuss the corresponding problem of finding an orientation of minimum Wiener index of a given graph, and show that the special case of deciding if a given graph on m edges has an orientation of Wiener index m can be solved in time quadratic in the order of the graph.
The Wiener index of a connected graph is the sum of the distances between all unordered pairs of vertices. A connected graph is Eulerian if its vertex degrees are all even. In Gutman et al. (2014) ...the authors proved that the cycle is the unique graph maximising the Wiener index among all Eulerian graphs of given order. They also conjectured that for Eulerian graphs of order n≥26 the graph consisting of a cycle on n−2 vertices and a triangle that share a vertex is the unique Eulerian graph with second largest Wiener index. The conjecture is known to hold for all n≤25 with exception of six values. In this paper we prove the conjecture.
Proximity, remoteness and maximum degree in graphs Dankelmann, Peter; Mafunda, Sonwabile; Mallu, Sufiyan
Discrete mathematics and theoretical computer science,
01/2022, Letnik:
24, no 2, Številka:
Graph Theory
Journal Article
Recenzirano
Odprti dostop
The average distance of a vertex $v$ of a connected graph $G$ is the
arithmetic mean of the distances from $v$ to all other vertices of $G$. The
proximity $\pi(G)$ and the remoteness $\rho(G)$ of $G$ ...are the minimum and the
maximum of the average distances of the vertices of $G$, respectively.
In this paper, we give upper bounds on the remoteness and proximity for
graphs of given order, minimum degree and maximum degree. Our bounds are sharp
apart from an additive constant.
Let G be a connected graph. The Steiner distance d(S) of a set S of vertices is the minimum size of a connected subgraph of G containing all vertices of S. For k∈N, the Steiner k-Wiener index SWk(G) ...is defined as ∑Sd(S), where the sum is over all k-element subsets of the vertex set of G. The average Steiner k-distance μk(G) of G is defined as nk−1SWk(G).
In this paper we prove upper bounds on the Steiner Wiener index and the average Steiner distance of graphs with given order n and minimum degree δ. Specifically we show that SWk(G)≤k−1k+13nδ+1nk+O(nk), and that μk(G)≤k−1k+13nδ+1+O(1). We improve this bound for triangle-free graphs to SWk(G)≤k−1k+12nδnk+O(nk), and μk(G)≤k−1k+12nδ+O(1). All bounds are best possible.
Let $G$ be a a connected graph. The Wiener index of a connected graph is the
sum of the distances between all unordered pairs of vertices. We provide
asymptotic formulae for the maximum Wiener index ...of simple triangulations and
quadrangulations with given connectivity, as the order increases, and make
conjectures for the extremal triangulations and quadrangulations based on
computational evidence. If $\overline{\sigma}(v)$ denotes the arithmetic mean
of the distances from $v$ to all other vertices of $G$, then the remoteness of
$G$ is defined as the largest value of $\overline{\sigma}(v)$ over all vertices
$v$ of $G$. We give sharp upper bounds on the remoteness of simple
triangulations and quadrangulations of given order and connectivity.
Edge-fault diameter of C4-free graphs Alochukwu, Alex; Dankelmann, Peter
Discrete mathematics,
January 2024, 2024-01-00, Letnik:
347, Številka:
1
Journal Article
Recenzirano
Odprti dostop
Let G be a connected graph and k∈N. The k-edge-fault diameter of G is defined as the largest diameter of the graphs arising from G by deleting k edges. In this paper we show that the k-edge-fault ...diameter of a (k+1)-edge connected graph of order n not containing a 4-cycle cannot exceed 5k2+k+1n+9, and we construct graphs that show that for k+1 a prime power this bound is close to optimal if k is large. For the special case k=2 we improve the above bound and obtain the sharp bound n2 on the 2-edge-fault diameter of 3-edge-connected graphs of order n not containing a 4-cycle.
We present upper bounds on the average distance for two important classes of digraphs, viz., tournaments and Eulerian digraphs. We first show that the average distance of Eulerian digraphs of order n ...and minimum degree δ is bounded from above by 32(δ+1)n+32+1n−1. The coefficient 32(δ+1) is close to being optimal. We also give an improved bound for Eulerian bipartite digraphs. We then give upper bounds on the average distance of tournaments in terms of order and edge-connectivity, and in terms of diameter only. Both bounds are sharp apart from an additive constant.
PDF
