Search

Vehicular ad hoc networks (VANETs) represent a critical component of intelligent transportation systems, with substantial research dedicated to developing reliable, scalable, and efficient routing protocols. The integration of the Internet of Things with VANETs significantly enhances vehicular communication, safety, and traffic management by enabling real-time data exchange and improving connectivity between vehicles and infrastructure. This paper proposes a novel protocol that integrates several key technologies, including software-defined networking (SDN), which offers scalability, programmability, and global network information, and fog computing, which supports location-based services in compliance with VANET standards. Additionally, we introduce a novel cluster head (CH) selection algorithm aimed at improving protocol efficiency. This algorithm considers three dimensions: network lifetime, average distance, and signal-to-interference noise ratio, reducing control overhead, long-distance communication, and packet loss due to collisions within clusters, respectively. The algorithm elects CHs based on a weighted value to improve network performance. Furthermore, a dual-phase strategy is implemented, where the classic AODV protocol serves as a fallback mechanism when SDN encounters complex packet processing challenges. Interestingly, we assess our protocol’s performance in terms of throughput and end-to-end delay and compare it to five closely related routing protocols, namely IDVR, VDLA, IRTIV, GPCR, and ICDRP. We consider further control overhead in the evaluation and comparisons. The comparison, in this perspective, is conducted with CBDRP, BRAVE, MoZo, CORA, and ICDRP. Our proposed protocol has produced outstanding simulation results. Specifically, across IDVR, VDLA, IRTIV, GPCR, and ICDRP, respectively, the throughput is improved by 21,969%, 172,425%, 187,727%, 249,867%, and 65.2%, respectively, while the end-to-end delay is decreased by 91.6%, 93.5%, 95%, 98%, and 14.41%, respectively. Compared to CBDRP, BRAVE, MoZo, and CORA, Hello messages are reduced by 99.5%, 98.92%, 97.81%, and 87.3%, respectively. When compared to ICDRP, our protocol control overhead messages are reduced by 21.2%. [ABSTRACT FROM AUTHOR]

Graph theory serves as a valuable tool across numerous scientific disciplines, offering the means to model and analyze intricate networks. In this study, we explore the application of distance‐based topological indices to a variety of graphs, including the total graph of paths, cycles, complete graphs, wheel graphs, helm graphs, and the Cartesian product of K1 and Kn. We investigate five distance‐based indices: the Wiener index, multiplicative Wiener index, hyper‐Wiener index, Harary index, and average distance. Through detailed analysis, we derive general formulas for these indices and test them on the specified graphs. Using MATLAB for numerical comparisons, we demonstrate the effectiveness of these indices in capturing the structural properties of different graph types. The findings from this study enhance our understanding of topological indices and their applications within the field of graph theory. [ABSTRACT FROM AUTHOR]

The purpose of the paper was to introduce the basic concepts， calculation methods， two examples and the calculation methods using SAS related to the cluster analysis of disordered samples. Basic concepts included R² statistic， semi-partial R² statistic， pseudo F statistic and pseudo t ² statistic. The calculation methods involved the oblique intersection space distance calculation formula and the average distance calculation formula. The data in the two examples were "population growth and decline data of stem borer in a certain area from 1962 to 1988" and "scores of 10 types of red wines on 6 indicators". With the help of SAS software， cluster analysis of disordered samples was performed on the data in the two examples， and the explanation of the SAS output results was given. [ABSTRACT FROM AUTHOR]

Recognition of the boundaries of farmland plow areas has an important guiding role in the operation of intelligent agricultural equipment. To precisely recognize these boundaries, a detection method for unmanned tractor plow areas based on RGB-Depth (RGB-D) cameras was proposed, and the feasibility of the detection method was analyzed. This method applied advanced computer vision technology to the field of agricultural automation. Adopting and improving the YOLOv5-seg object segmentation algorithm, first, the Convolutional Block Attention Module (CBAM) was integrated into Concentrated-Comprehensive Convolution Block (C3) to form C3CBAM, thereby enhancing the ability of the network to extract features from plow areas. The GhostConv module was also utilized to reduce parameter and computational complexity. Second, using the depth image information provided by the RGB-D camera combined with the results recognized by the YOLOv5-seg model, the mask image was processed to extract contour boundaries, align the contours with the depth map, and obtain the boundary distance information of the plowed area. Last, based on farmland information, the calculated average boundary distance was corrected, further improving the accuracy of the distance measurements. The experiment results showed that the YOLOv5-seg object segmentation algorithm achieved a recognition accuracy of 99% for plowed areas and that the ranging accuracy improved with decreasing detection distance. The ranging error at 5.5 m was approximately 0.056 m, and the average detection time per frame is 29 ms, which can meet the real-time operational requirements. The results of this study can provide precise guarantees for the autonomous operation of unmanned plowing units. [ABSTRACT FROM AUTHOR]

For a graph G with n vertices, average distance µ(G) is the ratio of sum of the lengths of the shortest paths between all pairs of vertices to the number of edges in a complete graph on n vertices. In this paper, we introduce average distance colouring and find the average distance colouring number of certain classes of graphs.

To study the screening process and explore the segregation mechanism of wet sand and gravel particles, the screening of wet particles is carried out by discrete element method. The accurate parameter settings of wet particles are obtained by parameter calibration of the cylinder lifting. Then, the distribution of wet particles shows the triangular cone and ellipsoid particles have been screened in feeding and screening area. Moreover, there is obvious splash of particles in dry screening while there is no splash in wet screening, which explains the serious dust pollution in dry screening process. Meanwhile, the number of triangular cone and ellipsoid particles in feeding and screening area in wet screening process is more than that in dry screening process, which indicates wet screening process has higher screening efficiency. By comparing the average distances of different particles to the screen surface, the segregation mechanism of different particles is obtained. Furthermore, the square of velocity trends are in good agreement with the average distances of particles, which indicates that square of velocity can also be used as the evaluation index for particle segregation. The above researches provide a reference for optimization of the wet screening process parameters. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

The average distance μ(G) $\mu (G)$ of a simple connected graph G $G$ is the average of the distances between all pairs of vertices in G $G$. We prove that for a connected cubic graph G $G$ on n $n$ vertices, μ(G)≤n3−16n+484(n2−n) $\mu (G)\le \frac{{n}^{3}-16n+48}{4({n}^{2}-n)}$, if n=4k+2 $n=4k+2$; and μ(G)≤n3−32n+1284(n2−n) $\mu (G)\le \frac{{n}^{3}-32n+128}{4({n}^{2}-n)}$, if n=4k+4 $n=4k+4$. Furthermore, all extremal graphs attaining the upper bounds are characterized, and they have the maximum possible diameter. The result solves a question of Plesník and proves a conjecture of Knor, Škrekovski, and Tepeh on the average distance of cubic graphs. The proofs use graph transformations and structural graph analysis. [ABSTRACT FROM AUTHOR]

AbstractWe give a tight upper bound on the average distance of a connected graph of given order in terms of its connected domination number. Our results are a strengthening of a result by DeLaViña, Pepper, and Waller [A note on dominating sets and average distance, Discrete Mathematics 309 (2009) 2615–2619] on average distance and connected domination number.

Let G be a finite, connected graph. The eccentricity of a vertex v of G is the distance from v to a vertex farthest from v. The average eccentricity avec (G) of G is the arithmetic mean of the eccentricities of the vertices of G. The Wiener index W (G) of G is the sum of the distances between all unordered pairs of vertices of G. For these two distance measures we give upper bounds in terms of order n , minimum degree δ and maximum degree Δ for graphs of girth at least six, and for graphs containing neither 4-cycles nor 5-cycles as subgraphs. For graphs of girth at least six we show that the average eccentricity is bounded above by n − Δ ∗ n 9 n + 3 Δ ∗ 4 (δ 2 − δ + 1) + 21 , where Δ ∗ = Δ δ + (δ − 1) Δ (δ − 2) + 3 2 . We construct graphs that show that for δ − 1 a prime power this bound is sharp apart from a term O (Δ). We further show that if the girth condition on G is relaxed to G having neither a 4-cycle nor a 5-cycle as a subgraph, then similar and only slightly weaker bounds hold. For such graphs we also show that the average eccentricity is bounded from above by 9 2 ⌈ n 4 δ 2 − 10 δ + 14 ⌉ + 8 , which in some sense is close to being optimal. We obtain similar upper bounds for the Wiener index of graphs of girth at least 6 and for graphs containing neither a 4-cycle nor a 5-cycle as a subgraph. [ABSTRACT FROM AUTHOR]

In this work, we have performed simulation using single particles, such as pions and photons, incident on the photon multiplicity detector (PMD). We have obtained the average analog to digital converter channels (ADC), average number of cells (Ncell) and average distance from the actual incident particle position to the centroid of the clusters for both pion clusters and photon clusters. We compared the results using the pion and electron beams at CERN SPS. The electron beam is taken instead of photon beam as it is impossible to have a photon beam. The goal of this study is to define the criteria to distinguish the photon clusters from the hadron clusters more efficiently by directly studying the photons instead of electron beam incident on PMD. Also studying the additional parameter of average distance from the centroid of the photon and pion clusters will make the discrimination criteria more robust which is missing from the test beam results. [ABSTRACT FROM AUTHOR]

An added edge to a graph is called an inset edge. Predicting k inset edges, which minimize the average distance of a graph, is known to be NP-Hard. However, when k = 1 , the complexity of the problem is polynomial. In this paper, some tools for a precise analysis of the effect of inset edges on the tree's average distance are established. Using the tools, one can avoid using the distance matrix for better performance of algorithms. Here, some applications of the tools and a tight bound for the change of average distance when an inset edge is added to a tree are presented. [ABSTRACT FROM AUTHOR]

The classification performance of a k-nearest neighbour (KNN) method is dependent on the choice of the k neighbours of a query. However, it is difficult to optimise the performance of KNN by choosing appropriate neighbours and an appropriate value of k. Moreover, the performance of KNN suffers from the use of a simple majority voting method. To address these three issues, we propose a new locally adaptive k-nearest centroid neighbour classification based on the average distance (AD-LAKNCN) in this paper. First, the k neighbours of the query based on the nearest centroid neighbour (NCN) are found, and the discrimination classes with different k values are derived from the number and distribution of each class of neighbours considered in the query. Then, based on the distribution information in the discrimination class for each k, the adaptive k and the final classification result are obtained. The experimental results based on 24 real-world datasets show that the new method achieves better classification performance than nine other state-of-the-art KNN algorithms. [ABSTRACT FROM AUTHOR]

Bidirectional double-loop networks (BDLNs) are widely used in computer networks for their simplicity, symmetry and scalability. One common way to improve their performance is to decrease the diameter and average distance. Attempts have been made to find BDLNs with minimal diameters; however, such BDLNs will not necessarily have the minimum average distance. In this paper, we construct dual optimal BDLNs with minimum diameters and average distances using an efficient method based on coordinate embedding and transforming. First, we get the lower bounds of both the diameter and average distance by embedding a BDLN into Cartesian coordinates. Then, we construct tight optimal BDLNs that provide the aforementioned lower bounds based on an embedding graph. On the basis of node distribution regularity in tight optimal BDLNs, we construct dual optimal BDLNs with minimum diameters and average distances for any number of nodes. Finally, we present on-demand optimal message routing algorithms for the dual optimal BDLNs that we have constructed. The presented algorithms do not require routing tables and are efficient, requiring little computation. [ABSTRACT FROM AUTHOR]

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$. 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$ by Kouider and Winkler \cite{Kouider} was improved significantly by Alochukwu and Dankelmann \cite{Alex} for graphs containing a vertex of large degree $\Delta$ to $W(G) \leq {n-\Delta+\delta \choose 2} \big( \frac{n+2\Delta}{\delta+1}+4 \big)$. In this paper, we give upper bounds on the Wiener index of $G$ in terms of order $n$ and girth $g$, where $n$ is a function of both the minimum degree $\delta$ and maximum degree $\Delta$. Our result provides a generalisation for these previous bounds for any graph of girth $g$. In addition, we construct graphs to show that, if for given $g$, there exists a Moore graph of minimum degree $\delta$, maximum degree $\Delta$ and girth $g$, then the bounds are asymptotically sharp.

We discuss the twist map, with a special interest in its use for the finite Frenkel–Kontorova model. We explain the meaning of the tensile force in some proposed models. We demonstrate that the application of the twist map for the finite FK model is not correct, because the procedure ignores the necessary boundary conditions. [ABSTRACT FROM AUTHOR]

Let G be a connected graph. If σ(v) denotes the arithmetic mean of the distances from v to all other vertices of G, then the proximity, π(G), of G is defined as the smallest value of σ(v) over all vertices v of G. We give upper bounds for the proximity of simple triangulations and quadrangulations of given order and connectivity. We also construct simple triangulations and quadrangulations of given order and connectivity that match the upper bounds asymptotically and are likely optimal. [ABSTRACT FROM AUTHOR]

Green computing is an important factor to ensure the eco-friendly use of computers and their resources. Electric power used in a computer converts into heat and thus, the system takes fewer watts ensuring less cooling. This lower energy consumption allows to be less costly to run as well as reduces the environmental impact of powering the computer. One of the most challenging problems for the modern green supercomputers is the reduction of current power consumptions. Consequently, regular conventional interconnection networks also show poor cost performance. On the other hand, hierarchical interconnection networks (like-3D-TTN) can be a possible solution to those issues. The main focus for this paper is the estimation of power usage at the on-chip level for 3D-TTN with the various other networks along with the analysis of static network performance. In our analysis, 3D-TTN requires about 32.48% less router power usage at the on-chip level and can also achieve near about 21% better diameter performance as well as 12% better average distance performance than the 5D-Torus network. Similarly, it also requires only about 14.43% higher router power usage; however, can achieve 23.21% better diameter performance and 26.3% better average distance than recent hierarchical interconnection network- 3D-TESH. The most attractive feature of this paper is the static hop distance parameter and per watt analysis (power-performance). According to our power-performance results, 3D-TTN can also show better result than the 3D-Mesh, 2D-Mesh, 2D-Torus and 3D-TESH network even at the lowest network level. Moreover, this paper is also featured with the static effectiveness analysis, which ensures cost and time efficiency of 3D-TTN. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

The composition, morphology, number, area, size and average distance of inclusions in Fe–23Mn–xAl–0.7C steels were evaluated through an inclusion automatic analysis system (INCA Feature). According to their composition and morphology, six types of inclusions are classified in the present steels: MnS(Se), AlN, Al2O3, AlN–MnS(Se), Al2O3–MnS(Se), and other inclusions (i.e. Al2O3–AlN and MgO–Al2O3). Thermodynamic calculation results show that AlN inclusions are formed in molten steel with Al contents of 3.28 and 6.76 wt-%. Irregularly shaped MnS(Se) inclusions precipitate during the solidification processe. AlN and Al2O3 generally serve as sites for the heterogeneous nucleation of MnS(Se). Sometimes, AlN particles can precipitate on the surfaces of Al2O3 and MnS(Se) inclusions in the solidification process. As the Al content increases to 6.76 wt-%, a large number of agglomerated AlN and AlN–MnS(Se) inclusions are observed. Agglomerated AlN inclusions normally form in the smelting process due to the combined effects of the cavity bridge force and viscous resistance. [ABSTRACT FROM AUTHOR]

In this paper, we establish the theory of finite geodesic patterns on limit space to calculate the average distances of touching networks. [ABSTRACT FROM AUTHOR]

Bidirectional double-loop networks (BDLNs) are widely used in computer networks for their simplicity, symmetry and scalability. One common way to improve their performance is to decrease the diameter and average distance. Attempts have been made to find BDLNs with minimal diameters; however, such BDLNs will not necessarily have the minimum average distance. In this paper, we construct dual optimal BDLNs with minimum diameters and average distances using an efficient method based on coordinate embedding and transforming. First, we get the lower bounds of both the diameter and average distance by embedding a BDLN into Cartesian coordinates. Then, we construct tight optimal BDLNs that provide the aforementioned lower bounds based on an embedding graph. On the basis of node distribution regularity in tight optimal BDLNs, we construct dual optimal BDLNs with minimum diameters and average distances for any number of nodes. Finally, we present on-demand optimal message routing algorithms for the dual optimal BDLNs that we have constructed. The presented algorithms do not require routing tables and are efficient, requiring little computation.

In this paper, we prove a collection of results on graphical indices. We determine the extremal graphs attaining the maximal generalized Wiener index (e.g. the hyper-Wiener index) among all graphs with given matching number or independence number. This generalizes some work of Dankelmann, as well as some work of Chung. We also show alternative proofs for two recent results on maximizing the Wiener index and external Wiener index by deriving it from earlier results. We end with proving two conjectures. We prove that the maximum for the difference of the Wiener index and the eccentricity is attained by the path if the order n is at least 9 and that the maximum weighted Szeged index of graphs of given order is attained by the balanced complete bipartite graphs. [ABSTRACT FROM AUTHOR]

The geodesic structures on self-similar fractals are interesting. One feature of geodesic structures is average distance on fractal. We investigate the Sierpinski-like carpet and obtain the average distance in terms of self-similar measure. [ABSTRACT FROM AUTHOR]

We leverage proof techniques from discrete Fourier analysis and an existing result in coding theory to derive new bounds for the problem of non-interactive simulation of binary random variables. Previous bounds in the literature were derived by applying data processing inequalities concerning maximal correlation or hypercontractivity. We show that our bounds are sharp in some regimes. Indeed, for a specific instance of the problem parameters, our main result resolves an open problem posed by E. Mossel in 2017. As by-products of our analyses, various new properties of the average distance and distance enumerator of binary block codes are established. [ABSTRACT FROM AUTHOR]

Let G be a connected graph. TheWiener index of a connected graph is the sum of the distances between all unordered pairs of vertices. We provide asymptotic formulas 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 σ(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 σ(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. [ABSTRACT FROM AUTHOR]

A bipartite graph is called a chain graph if the neighborhoods of the vertices in each partite set form a chain with respect to set inclusion. Chain graphs are discovered and re-discovered by various researchers in various contexts. Also, they were named differently according to the applications in which they arise. In the field of Spectral Graph Theory, chain graphs play a remarkable role. They are characterized as graphs with the largest spectral radius among all the connected bipartite graphs with prescribed number of edges and vertices. Even though chain graphs are significant in the field of Spectral Graph Theory, the area of graph parameters remains untouched. Wiener index is one of the oldest and most studied topological indices, both from theoretical point of view and applications. The Wiener index of a graph is defined as the sum of distances between every pair of vertices in it. In this article, we give bounds for Wiener index and hence for average distance of chain graphs. We also present a quadratic time algorithm that returns a realising chain graph G (if exists) whose Wiener index is the given integer w. The algorithm presented in this article contributes to the existing knowledge in the theory of inverse Wiener index problem. We conclude this article by exploring some more graph parameters called edge Wiener index, hyper Wiener index and Zagreb indices of chain graphs. [ABSTRACT FROM AUTHOR]

Fix d ≥ 3. We show the existence of a constant c > 0 such that any graph of diameter at most d has average distance at most d − c d 3 / 2 n , where n is the number of vertices. Moreover, we exhibit graphs certifying sharpness of this bound up to the choice of c. This constitutes an asymptotic solution to a longstanding open problem of Plesník. Furthermore we solve the problem exactly for digraphs if the order is large compared with the diameter. [ABSTRACT FROM AUTHOR]

The investigation on relationships between various graph invariants has received much attention over the past few decades, and some of these research are associated with Graffiti conjectures (Fajtlowicz and Waller in Congr Numer 60:187–197, 1987) or AutoGraphiX conjectures (Aouchiche et al. in: Liberti, Maculan (eds) Global optimization: from theory to implementation, Springer, New York, 2006). The reciprocal degree distance (RDD), the adjacent eccentric distance sum (AEDS), the average distance (AD) and the connective eccentricity index (CEI) are all distance-based graph invariants or topological indices, some of which found applications in Chemistry. In this paper, we investigate the relationship between RDD and other three graph invariants AEDS, CEI and AD. First, we prove that AEDS > RDD for any tree with at least three vertices. Then, we prove that RDD > CEI for all connected graphs with at least three vertices. Moreover, we prove that RDD > AD for all connected graphs with at least three vertices. As a consequence, we prove that AEDS > CEI and AEDS > AD for any tree with at least three vertices. [ABSTRACT FROM AUTHOR]

In this paper, we discuss a family of p.c.f. self-similar fractal networks which have reflection transformations. We obtain the average geodesic distance on the corresponding fractal in terms of finite pattern of integrals. With these results, we also obtain the asymptotic formula for average distances of the skeleton networks. [ABSTRACT FROM AUTHOR]

In this paper, we discuss a family of non-p.c.f. self-similar networks. Although the boundary of each fractal piece is not a finite set, we obtain the finite geometric patterns for the integral of geodesic distance on the self-similar measure, and then calculate its average distance. [ABSTRACT FROM AUTHOR]

This paper discusses the asymptotic formula of average distances on node-weighted Sierpinski skeleton networks by using the integral of geodesic distance in terms of self-similar measure on the Sierpinski gasket with respect to the weight vector. [ABSTRACT FROM AUTHOR]

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 S W k (G) is defined as ∑ S d (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 n k − 1 S W k (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 S W k (G) ≤ k − 1 k + 1 3 n δ + 1 n k + O (n k) , and that μ k (G) ≤ k − 1 k + 1 3 n δ + 1 + O (1). We improve this bound for triangle-free graphs to S W k (G) ≤ k − 1 k + 1 2 n δ n k + O (n k) , and μ k (G) ≤ k − 1 k + 1 2 n δ + O (1). All bounds are best possible. [ABSTRACT FROM AUTHOR]

The substitution network is a deterministic model of evolving self-similar networks. For normalized substitution networks, the limit of metric spaces with respect to networks is a self-similar fractal and the limit of average distances on networks is the integral of geodesic distance of the fractal on the self-similar measure. After some technical handles, we establish the finiteness of integrals and obtain a linear equation set to solve the average distance on the fractal. [ABSTRACT FROM AUTHOR]

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 3 2 (δ + 1) n + 3 2 + 1 n − 1. The coefficient 3 2 (δ + 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. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the average geodesic distance on the Sierpinski hexagon in terms of finite patterns on integrals. Applying this result, we also obtain the asymptotic formula for average distances of Sierpinski hexagon networks. [ABSTRACT FROM AUTHOR]

This paper is concerned with the strong product G ⊠ H of two graphs, G and H , and bounds on the Wiener index, Hosoya polynomial and the average eccentricity in this family of graphs. We first introduce the distance sequence of a connected graph. It is defined as the sequence of the distances between all unordered pairs of vertices. We prove that the distance sequence of any connected graph of given order and size is dominated by the distance sequence of the so-called path-complete graph. This is the main tool to prove general results as, among others, that, if G is a connected graph of given order and size, then the Wiener index of G ⊠ H , for every fixed connected graph H , and the Hosoya polynomial W (G , x) , for every x ∈ R with x ≥ 1 , are maximised if G is a path-complete graph. We also investigate the average eccentricity of G ⊠ H. We show that for fixed H , and G chosen from among all connected graphs of given order n , it is maximised if G is a path of the same order. We also determine a graph G n , δ of order n and minimum degree δ such that for every connected graph G of order n and minimum degree δ , the average eccentricity of G ⊠ H never exceeds the average eccentricity of G n , δ ⊠ H by more than 3. [ABSTRACT FROM AUTHOR]

Abstract The Wiener index of a connected graph is the summation of distances between all unordered pairs of vertices of the graph. The status of a vertex in a connected graph is the summation of distances between the vertex and all other vertices of the graph. A maximal planar graph is a graph that can be embedded in the plane such that the boundary of each face (including the exterior face) is a triangle. Let G be a maximal planar graph of order n ≥ 3. In this paper, we show that the diameter of G is at most ⌊ 1 3 (n + 1) ⌋ , and the status of a vertex of G is at most ⌊ 1 6 (n 2 + n) ⌋. Both of them are sharp bounds and can be realized by an Apollonian network, which is a chordal maximal planar graph. We also present a sharp upper bound ⌊ 1 18 (n 3 + 3 n 2) ⌋ on Wiener indices when graphs in consideration are Apollonian networks of order n ≥ 3. We further show that this sharp upper bound holds for maximal planar graphs of order 3 ≤ n ≤ 10 , and conjecture that it is valid for all n ≥ 3. [ABSTRACT FROM AUTHOR]

Three standard subtree transfer operations for binary trees, used in particular for phylogenetic trees, are: tree bisection and reconnection (TBR), subtree prune and regraft (SPR), and rooted subtree prune and regraft (rSPR). We show that for a pair of leaf-labelled binary trees with n leaves, the maximum number of such moves required to transform one into the other is n-Θ(n), extending a result of Ding, Grünewald, and Humphries, and this holds also if one of the trees is fixed arbitrarily. If the pair is chosen uniformly at random, then the expected number of moves required is n-Θ(n2/3). These results may be phrased in terms of agreement forests: we also give extensions for more than two binary trees. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a connected graph of order n. The distance, d G (x , y) , between vertices x and y in G is defined as the length of a shortest x - y path in G. The average distance, μ (G) , of G is defined as μ (G) = ( n 2 ) − 1 ∑ { x , y } ⊆ V d G (x , y). We give an upper bound on the average distance of a connected graph of given order and minimum degree where irregularity index is prescribed. Our results are a strengthening of the classical theorems by Kouider and Winkler (1997) [9] and by Dankelmann and Entringer (2000) [5] on average distance and minimum degree if the number of distinct terms in the degree sequence of the graph is prescribed. [ABSTRACT FROM AUTHOR]

There has been a great deal of interest in the computation of distances and shortest paths problem in graphs which is one of the central, and most studied, problems in (algorithmic) graph theory. In this paper, we survey the exact results of the static version of the all-pairs shortest paths problem and its variants namely, the Wiener index, the average distance, and the minimum average distance spanning tree (MAD tree in short) in graphs (focusing mainly on algorithmic results for such problems). Along the way we also mention some important open issues and further research directions in these areas.

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 defined as the minimum and maximum‎, ‎respectively‎, ‎average‎ ‎distance of the vertices of $G$‎. ‎In this paper we investigate the difference between proximity or remoteness and the classical distance‎ ‎parameters diameter and radius‎. ‎Among other results we show that in a graph of order‎ ‎$n$ and minimum degree $\delta$ the difference between‎ ‎diameter and proximity and the difference between‎ ‎radius and proximity cannot exceed‎ ‎$\frac{9n}{4(\delta+1)}+c_1$ and‎ ‎$\frac{3n}{4(\delta+1)}+c_2$‎, ‎respectively‎, ‎for‎ ‎constants $c_1$ and $c_2$ which depend on $\delta$‎ ‎but not on $n$‎. ‎These bounds improve bounds by‎ ‎Aouchiche and Hansen \cite{AouHan2011} in terms of‎ ‎order alone by about a factor of $\frac{3}{\delta+1}$‎. ‎We further give lower bounds on the remoteness in‎ ‎terms of diameter or radius‎. ‎Finally we show that‎ ‎the average distance of a graph‎, ‎i.e.‎, ‎the average of‎ ‎the distances between all pairs of vertices‎, ‎cannot‎ ‎exceed twice the proximity‎.

We study several distinct notions of average distances between points belonging to graph‐directed self‐similar subsets of R. In particular, we compute the average distance with respect to graph‐directed self‐similar measures, and with respect to the normalised Hausdorff measure. As an application of our main results, we compute the average distance between two points belonging to the Drobot–Turner set TN(c,m) with respect to the normalised Hausdorff measure, i.e. we compute 1Hs(TN(c,m))2∫TN(c,m)2|x−y|d(Hs×Hs)(x,y),where s denotes the Hausdorff dimension of TN(c,m) and Hs is the s‐dimensional Hausdorff measure; here the Drobot–Turner set (introduced by Drobot & Turner in 1989) is defined as follows, namely, for positive integers N and m and a positive real number c, the Drobot–Turner set TN(c,m) is the set of those real numbers x∈[0,1] for which any m consecutive base N digits in the N‐ary expansion of x sum up to at least c. For example, if N=2, m=3 and c=2, then our results show that 1Hs(T2(2,3))2∫T2(2,3)2|x−y|d(Hs×Hs)(x,y)=4444λ2+2071λ+303012141λ2+5650λ+8281=0.36610656...,where λ=1.465571232... is the unique positive real number such that λ3−λ2−1=0. [ABSTRACT FROM AUTHOR]