✦ LIBER ✦

A characterization of 3-Steiner distance hereditary graphs

✍ Scribed by Day, D. P.; Oellermann, Ortrud R.; Swart, Henda C.

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 174 KB
Volume: 30
Category: Article
ISSN: 0028-3045
DOI: 10.1002/(sici)1097-0037(199712)30:4<243::aid-net2>3.0.co;2-j

No coin nor oath required. For personal study only.

✦ Synopsis

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 used to characterize 3-Steiner distance hereditary graphs.

📜 SIMILAR VOLUMES

The average Steiner distance of a graph

✍ Dankelmann, Peter; Oellermann, Ortrud R.; Swart, Henda C. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 384 KB 👁 2 views

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,

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

Homogeneous sets and domination: A linea

Homogeneous sets and domination: A linear time algorithm for distance—hereditary graphs

✍ Falk Nicolai; Thomas Szymczak 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 210 KB

A Characterization in Zn of Finite Unit-

A Characterization in Zn of Finite Unit-Distance Graphs in Rn

✍ K.B. Chilakamarri 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 173 KB

Packing the Steiner trees of a graph

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

Circular chromatic number of distance gr

Circular chromatic number of distance graphs with distance sets of cardinality 3

✍ Xuding Zhu 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 104 KB

## Abstract Suppose __D__ is a subset of __R__^+^. The distance graph __G__(__R, D__) is the graph with vertex set __R__ in which two vertices __x__,__y__ are adjacent if |__x__−__y__| ∈ __D__. This study investigates the circular chromatic number and the fractional chromatic number of distance gra