✦ LIBER ✦

Packing a tree with a graph of the same size

✍ Scribed by P. J. Slater; S. K. Teo; H. P. Yap

Publisher: John Wiley and Sons
Year: 1985
Tongue: English
Weight: 195 KB
Volume: 9
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190090203

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We prove that if T is a tree of order p ⩾ 5 and G is a graph of order p and size p ‐ 1 such that neither T nor G is a star, then T can be embedded in G, the complement of G.

📜 SIMILAR VOLUMES

Packing the Steiner trees of a graph

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

Packing Three Copies of a Tree into a Co

Packing Three Copies of a Tree into a Complete Graph

✍ Hong Wang; Norbert Sauer 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 161 KB

Packing two copies of a sparse graph int

Packing two copies of a sparse graph into a graph with restrained maximum degree

✍ Hong Wang 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 132 KB

## Abstract We show that if a tree __T__ is not a star, then there is an embedding σ of __T__ in the complement of __T__ such that the maximum degree of __T__∪σ(__T__) is at most Δ(__T__)+2. We also show that if __G__ is a graph of order __n__ with __n__−1 edges, then with several exceptions, there

The Size of Bipartite Graphs with a Give

The Size of Bipartite Graphs with a Given Girth

✍ Shlomo Hoory 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 90 KB

Covering the Edges of a Graph by a Presc

Covering the Edges of a Graph by a Prescribed Tree with Minimum Overlap

✍ Noga Alon; Yair Caro; Raphael Yuster 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 360 KB

Let H=(V H , E H ) be a graph, and let k be a positive integer. A graph G=(V G , E G ) is H-coverable with overlap k if there is a covering of the edges of G by copies of H such that no edge of G is covered more than k times. Denote by overlap(H, G) the minimum k for which G is H-coverable with over

A Self-Stabilizing Distributed Algorithm

A Self-Stabilizing Distributed Algorithm to Find the Median of a Tree Graph

✍ Gheorghe Antonoiu; Pradip K. Srimani 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 231 KB

We propose a self-stabilizing algorithm (protocol) for computing the median in a given tree graph. We show the correctness of the proposed algorithm by using a new technique involving induction.