✦ LIBER ✦

The average Steiner distance of a graph

✍ Scribed by Dankelmann, Peter; Oellermann, Ortrud R.; Swart, Henda C.

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 384 KB
Volume: 22
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199605)22:1<15::aid-jgt3>3.0.co;2-o

No coin nor oath required. For personal study only.

✦ Synopsis

The average distance p(G) of a graph G is the average among the distances between all pairs of vertices in G. For n 2 2, the average Steiner n-distance ,4G) of a connected graph G is the average Steiner distance over all sets of n vertices in G. It is shown that for a connected weighted graph G, pu,(G) I pk(G) + pu,+l-k(G) where 2 I k I n -1.

The range for the average Steiner n-distance of a connected graph G in terms of n and IV(G)l is established. Moreover, for a tree T and integer k, 2 I k I n -1, it is shown that p n ( T ) 5 (n/k)pk(T) and the range for p n ( T ) in terms of n and IV(T)I is established. Two efficient algorithms for finding the average Steiner n-distance of a tree are outlined.

📜 SIMILAR VOLUMES

A characterization of 3-Steiner distance

A characterization of 3-Steiner distance hereditary graphs

✍ Day, D. P.; Oellermann, Ortrud R.; Swart, Henda C. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 174 KB 👁 1 views

Let G be a connected graph and S ⊆ V (G). Then, the Steiner distance of S in G, denoted by d G (S), is the smallest number of edges in a connected subgraph of G that contains . Some general properties about the cycle structure of k-Steiner distance hereditary graphs are established. These are then

Packing the Steiner trees of a graph

✍ L. Petingi; M. Talafha 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB

On the distance matrix of a directed gra

On the distance matrix of a directed graph

✍ R. L. Graham; A. J. Hoffman; H. Hosoya 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB 👁 2 views

## Abstract In this note, we show how the determinant of the distance matrix __D(G__) of a weighted, directed graph __G__ can be explicitly expressed in terms of the corresponding determinants for the (strong) blocks __G~i~__ of __G__. In particular, when cof __D(G__), the sum of the cofactors of _

A linear-time algorithm for connectedr-d

A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs

✍ Brandst�dt, Andreas; Dragan, Feodor F. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 83 KB 👁 1 views

A distance-hereditary graph is a connected graph in which every induced path is isometric, i.e., the distance of any two vertices in an induced path equals their distance in the graph. We present a linear time labeling algorithm for the minimum cardinality connected r-dominating set and Steiner tree

On the editing distance of graphs

✍ Maria Axenovich; André Kézdy; Ryan Martin 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 169 KB 👁 2 views

## Abstract An edge‐operation on a graph __G__ is defined to be either the deletion of an existing edge or the addition of a nonexisting edge. Given a family of graphs $\cal G$, the editing distance from __G__ to $\cal G$ is the smallest number of edge‐operations needed to modify __G__ into a graph

The average degree of an edge-chromatic

The average degree of an edge-chromatic critical graph II

✍ Douglas R. Woodall 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 224 KB 👁 1 views

## Abstract A graph __G__ with maximum degree Δ and edge chromatic number $\chi\prime({G}) > \Delta$ is __edge__‐Δ‐__critical__ if $\chi\prime{(G-e)} = \Delta$ for every edge __e__ of __G__. It is proved that the average degree of an edge‐Δ‐critical graph is at least ${2\over 3}{(\Delta+1)}$ if $\D