𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Embedding k(n−k) edge-disjoint spanning trees in arrangement graphs

✍ Scribed by Chin-Tsai Lin

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
278 KB
Volume
63
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

✦ Synopsis

The arrangement graphs are a class of generalized star graphs. In this paper we construct a graph that consists of the maximum number of directed edge-disjoint spanning trees in an arrangement graph. The paths that connect the common root node to any given node through different spanning trees are node-disjoint, and the lengths of these paths differ from the shortest possible lengths by a small additive constant. This graph can be used to derive fault-tolerant algorithms for broadcasting and scattering problems without prior knowledge of the faulty elements of the network.

📜 SIMILAR VOLUMES

Congestion-free embedding of 2(n−k) span
Congestion-free embedding of 2(n−k) spanning trees in an arrangement graph
✍ Yuh-Shyan Chen; Tong-Ying Juang; Ying-Ying Shen 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 912 KB

The arrangement graph A nYk is not only a generalization of star graph (n À k 1), but also more ¯exible. In this investigation, we elucidate the problem of embedding of multiple spanning trees in an arrangement graph with the objective of congestion-free. This result is to report how to exploit 2n À

Packing k-edge trees in graphs of restri
Packing k-edge trees in graphs of restricted vertex degrees
✍ A.K. Kelmans 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 368 KB 👁 1 views

## Abstract Let ${\cal G}^{s}\_{r}$ denote the set of graphs with each vertex of degree at least __r__ and at most __s__, __v__(__G__) the number of vertices, and τ~__k__~ (__G__) the maximum number of disjoint __k__‐edge trees in __G__. In this paper we show that if __G__ ∈ ${\cal G}^{s}\_{2}$ a

On the number of edge-disjoint one facto
On the number of edge-disjoint one factors and the existence of k-factors in complete multipartite graphs
✍ D.G. Hoffman; C.A. Rodger 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 503 KB

In this paper we use Tutte's f-factor theorem and the method of amalgamations to find necessary and sufficient conditions for the existence of a k-factor in the complete multipartite graph K(p(1 ) ..... p(n)), conditions that are reminiscent of the Erd6s-Gallai conditions for the existence of simple

The existence of a 2-factor in K1, n-fre
The existence of a 2-factor in K1, n-free graphs with large connectivity and large edge-connectivity
✍ R. E. L. Aldred; Yoshimi Egawa; Jun Fujisawa; Katsuhiro Ota; Akira Saito 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 130 KB 👁 1 views

In this article, we study the existence of a 2-factor in a K 1,nfree graph. Sumner [J London Math Soc 13 (1976), 351-359] proved that for n ≥ 4, an (n-1)-connected K 1,n -free graph of even order has a 1-factor.