✦ LIBER ✦

A Property on Edge-disjoint Spanning Trees

✍ Scribed by Hong-Jian Lai; Hongyuan Lai; Charles Payan

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 214 KB
Volume: 17
Category: Article
ISSN: 0195-6698
DOI: 10.1006/eujc.1996.0038

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a simple graph with n vertices and let G c denote the complement of G . Let ( G ) denote the number of components of G and G ( E ) the spanning subgraph of G with edge set E .

where the minimum is taken over all such partitions . In [ Europ . J . Combin . 7 (1986) , 263 -270] ,

Payan conjectures that if » ( G ) Ͼ 0 , then there exist edges e E ( G ) and e Ј E ( G c ) such that » ( G Ϫ e ϩ e Ј ) Ͻ » ( G ) . This conjecture will be proved in this note .

📜 SIMILAR VOLUMES

Edge-disjoint spanning trees: A connecte

Edge-disjoint spanning trees: A connectedness theorem

✍ M. Farber; B. Richter; H. Shank 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 268 KB

On Minimum Edge Ranking Spanning Trees

✍ Kazuhisa Makino; Yushi Uno; Toshihide Ibaraki 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 243 KB

In this paper, we introduce the problem of computing a minimum edge ranking spanning tree (MERST); i.e., find a spanning tree of a given graph G whose edge ranking is minimum. Although the minimum edge ranking of a given tree can be computed in polynomial time, we show that problem MERST is NP-hard.

Multicast in Wormhole-Switched Torus Net

Multicast in Wormhole-Switched Torus Networks Using Edge-Disjoint Spanning Trees

✍ Honge Wang; Douglas M. Blough 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 486 KB

A tree-based multicast algorithm for wormhole-switched networks which makes use of multiple edge-disjoint spanning trees is presented. The disjoint spanning-tree multicast, or DSTM, algorithm provides deadlock-free multicast routing that is fully compatible with unicast. The application of the DSTM

A note on bisecting minimum spanning tre

A note on bisecting minimum spanning trees

✍ W. M. Boyce; M. R. Garey; D. S. Johnson 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 281 KB

On low bound of degree sequences of span

On low bound of degree sequences of spanning trees inK-edge-connected graphs

✍ Zhenhong, Liu; Baoguang, Xu 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 257 KB 👁 3 views

[•] is a lower integer form and α depends on k. We show that every k-edge-connected graph with k ≥ 2, has a d k -tree, and α = 1 for k = 2, α = 2 for k ≥ 3.

A note on graphs with diameter-preservin

A note on graphs with diameter-preserving spanning trees

✍ Fred Buckley; Martin Lewinter 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 182 KB 👁 1 views

The distance between a pair of vertices u, u in a graph G is the length of a shortest path joining u and u. The diameter diam(G) of G is the maximum distance between all pairs of vertices in G. A spanning tree Tof G is diameter preserving if diam(T) = diam(G). In this note, we characterize graphs th