Search

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]

Abstract: We consider the following generalisation of the average distance of a graph. Let be a connected, finite graph with a nonnegative vertex weight function . Let be the total weight of the vertices. If , then the weighted average distance of with respect to is defined by where denotes the usual distance between and in . If for all vertices of , then is the ordinary average distance. We present sharp bounds on for trees, cycles, and graphs with minimum degree at least . We show that some known results for the ordinary average distance also hold for the weighted average distance, provided that each vertex has weight at least . [Copyright &y& Elsevier]

Abstract: Let be a connected finite graph. The average distance of is the average of the distances between all pairs of vertices of . For a positive integer , a -packing of is a subset of the vertex set of such that the distance between any two vertices in is greater than . The -packing number of is the maximum cardinality of a -packing of . We prove upper bounds on the average distance in terms of and show that for fixed the bounds are, up to an additive constant, best possible. As a corollary, we obtain an upper bound on the average distance in terms of the -domination number, the smallest cardinality of a set of vertices of such that every vertex of is within distance of some vertex of . [Copyright &y& Elsevier]

Abstract: Brendan McKay gave the following formula relating the average distance between pairs of vertices in a tree and the eigenvalues of its Laplacian: By modifying Mohar’s proof of this result, we prove that for any graph , its average distance, , between pairs of vertices satisfies the following inequality: This solves a conjecture of Graffiti. We also present a generalization of this result to the average of suitably defined distances for subsets of a graph. [Copyright &y& Elsevier]

Abstract: We show that the total domination number of a simple connected graph is greater than the average distance of the graph minus one-half, and that this inequality is best possible. In addition, we show that the domination number of the graph is greater than two-thirds of the average distance minus one-third, and that this inequality is best possible. Although the latter inequality is a corollary to a result of P. Dankelmann, we present a short and direct proof. [Copyright &y& Elsevier]

Abstract: Let denote the minimum average Hamming distance of a binary constant weight code with length n, size M and weight . In this paper, we study the problem of determining . Using the methods from coding theory and linear programming, we derive several lower bounds on the average Hamming distance of a binary constant weight code. These lower bounds enable us to determine the exact value for in several cases. [Copyright &y& Elsevier]

The Randic´ index R(G) of a graph G=(V,E) is the sum of (d(u)d(v))−1/2 over all edges uv∈E of G. Bolloba´s and Erdo˝s (Ars Combin. 50 (1998) 225) proved that the Randic´ index of a graph of order n without isolated vertices is at least √ of n−1. They asked for the minimum value of R(G) for graphs G with given minimum degree δ(G). We answer their question for δ(G)=2 and propose a related conjecture. Furthermore, we prove a best-possible lower bound on the Randic´ index of a triangle-free graph G with given minimum degree δ(G). [Copyright &y& Elsevier]

Let G be a finite, connected graph. The average distance of a vertex v of G is the arithmetic mean of the distances from v to all other vertices of G. The remoteness ρ (G) and the proximity π (G) of G are the maximum and the minimum of the average distances of the vertices of G. In this paper, we present a sharp upper bound on the remoteness of a triangle-free graph of given order and minimum degree, and a corresponding bound on the proximity, which is sharp apart from an additive constant. We also present upper bounds on the remoteness and proximity of C 4 -free graphs of given order and minimum degree, and we demonstrate that these are close to being best possible. [ABSTRACT FROM AUTHOR]

Let D be a strongly connected digraph. The average distance σ ̄ (v) of a vertex v of D is the arithmetic mean of the distances from v to all other vertices of D. The remoteness ρ (D) and proximity π (D) of D are the maximum and the minimum of the average distances of the vertices of D , respectively. We obtain sharp upper and lower bounds on π (D) and ρ (D) as a function of the order n of D and describe the extreme digraphs for all the bounds. We also obtain such bounds for strong tournaments. We show that for a strong tournament T , we have π (T) = ρ (T) if and only if T is regular. Due to this result, one may conjecture that every strong digraph D with π (D) = ρ (D) is regular. We present an infinite family of non-regular strong digraphs D such that π (D) = ρ (D). We describe such a family for undirected graphs as well. [ABSTRACT FROM AUTHOR]