✦ LIBER ✦

Packing almost stars into the complete graph

✍ Scribed by Dobson, Edward

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 79 KB
Volume: 25
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199706)25:2<169::aid-jgt9>3.0.co;2-k

No coin nor oath required. For personal study only.

✦ Synopsis

We verify that the Tree Packing Conjecture is true for all sequences of trees T 1 , . . . , T n such that there exists x i ∈ V (T i ) and T i -x i has at least i -6(i -1)/4 isolated vertices.

📜 SIMILAR VOLUMES

Packing two bipartite graphs into a comp

Packing two bipartite graphs into a complete bipartite graph

✍ Wang, Hong 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 131 KB 👁 2 views

For two integers a and b, we say that a bipartite graph G admits an (a, b)bipartition if G has a bipartition (X, Y ) such that |X| = a and |Y | = b. We say that two bipartite graphs G and H are compatible if, for some integers a and b, both G and H admit (a, b)-bipartitions. In this paper, we prove

Congestion-free, dilation-2 embedding of

Congestion-free, dilation-2 embedding of complete binary trees into star graphs

✍ Tseng, Yu-Chee; Chen, Yuh-Shyan; Juang, Tong-Ying; Chang, Chiou-Jyu 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 291 KB 👁 2 views

Trees are a common structure to represent the intertask communication pattern of a parallel algorithm. In this paper, we consider the embedding of a complete binary tree in a star graph with the objective of minimizing congestion and dilation. We develop two embeddings: (i) a congestion-free, dilati

A necessary and sufficient condition for

A necessary and sufficient condition for the star decomposition of complete graphs

✍ Lin, Chiang; Shyu, Tay-Woei 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 130 KB 👁 2 views

In this paper w e prove the following result. Let ml 2 m2 2 ... 2 ml be nonnegative integers. A necessary and sufficient condition for the complete graph K,, to be decomposed into stars S,,, , S