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 metric dimension of a graph is the minimum size of a set of vertices such that each vertex is uniquely determined by the distances to the vertices of that set. Our aim is to upper-bound the order $n$ of a graph in terms of its diameter $d$ and metric dimension $k$. In general, the bound $n\leq d^k+k$ is known to hold. We prove a bound of the form $n=\mathcal{O}(kd^2)$ for trees and outerplanar graphs (for trees we determine the best possible bound and the corresponding extremal examples). More generally, for graphs having a tree decomposition of width $w$ and length $\ell$, we obtain a bound of the form $n=\mathcal{O}(kd^2(2\ell+1)^{3w+1})$. This implies in particular that $n=\mathcal{O}(kd^{\mathcal{O}(1)})$ for graphs of constant treewidth and $n=\mathcal{O}(f(k)d^2)$ for chordal graphs, where $f$ is a doubly exponential function. Using the notion of distance-VC dimension (introduced in 2014 by Bousquet and Thomassé) as a tool, we prove the bounds $n\leq (dk+1)^{t-1}+1$ for $K_t$-minor-free graphs and $n\leq (dk+1)^{d(3\cdot 2^{r}+2)}+1$ for graphs of rankwidth at most $r$.

Let G be a ‐connected or ‐edge‐connected graph, where . The k‐fault‐diameter and k‐edge‐fault‐diameter of G is the largest diameter of the subgraphs obtained from G by removing up to k vertices and edges, respectively. In this paper we give upper bounds on the k‐fault‐diameter and k‐edge‐fault‐diameter of graphs in terms of order. We show that the k‐fault‐diameter of a ‐connected graph G of order n is bounded from above by , and by approximately if G is also triangle‐free. If G does not contain 4‐cycles then this bound can be improved further to approximately . We further show that the k‐edge‐fault‐diameter of a ‐edge‐connected graph of order n is bounded by n – 1 if k = 1, by if k = 2, and by approximately if , and give improved bounds for triangle‐free graphs. Some of the latter bounds strengthen, in some sense, bounds by Erdös, Pach, Pollack, and Tuza (J Combin Theory B 47 (1989) 73–79) on the diameter. All bounds presented are sharp or at least close to being optimal. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 70(2), 132–140 2017

The average distance $\mu(G)$ of a connected graph G of order n is the average of the distances between all pairs of vertices of G. We prove that for a 3-edge-connected graph G of order n the inequality $\mu(G)\le{n}/{6}+24$ on the average distance holds. Our bound is shown to be best possible even if G is 4-edge-connected, and our results answer, in part, a question of Plesník [J. Graph Theory, 8 (1984), pp. 1–24].

The average distance $\mu(G)$ of a connected graph G of order n is the average of the distances between all pairs of vertices of G. We prove that if G is a $\lambda$-edge-connected graph of order n, then the bounds $\mu(G) \le 2n/15+9$ if $\lambda=5,6$, $\mu(G) \le n/9+10$ if $\lambda=7$, and $\mu(G) \le n/(\lambda+1)+5$ if $\lambda \ge 8$ hold. Our bounds are shown to be best possible, and our results solve a problem of Plesník [J. Graph Theory, 8 (1984), pp. 1–24].

For a vertex v and a (k − 1)-element subset P of vertices of a graph, one can define the distance from v to P in various ways, including the minimum, average, and maximum distance from v to P. Associated with each of these distances, one can define the k-eccentricity of the vertex v as the maximum distance over all P and the k-eccentricity of the set P as the maximum distance over all v. If k = 2, one is back with the normal eccentricity. We study here the properties of these eccentricity measures, especially bounds on the associated radius (minimum k-eccentricity) and diameter (maximum k-eccentricity). © 1999 John Wiley & Sons, Inc. Networks 34: 312–319, 1999

A graph G is called path-tough, if, for each nonempty set S of vertices, the graph $G - S$ can be covered by at most $|S|$ vertex disjoint paths. The authors prove that every graph of order n and minimum degree at least $[ 3/( 6 + \sqrt{3} ) ]n$ is Hamiltonian if and only if it is path-tough. Similar results involving the degree sum of two or three independent vertices, respectively, are given. Moreover, it is shown that every path-tough graph without three independent vertices of degree 2 contains a 2-factor. The authors also consider complexity aspects and prove that the decision problem of whether a given graph is path-tough is NP-complete.