Packing two copies of a tree into its fourth power

It is well known that if a tree T of order n is not a star, then there exists an edge-disjoint placement of two copies of this tree into the complete graph K n . We improve this result by proving that actually two copies of T can be edge-disjointly packed in a much smaller graph, namely in T 4, the...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2000-02, Vol.213 (1), p.169-178
Main Authors: Kheddouci, Hamamache, Saclé, Jean-François, Woźniak, Mariusz
Format: Article
Language:English
Subjects:
Computer Science
Data Structures and Algorithms
Discrete Mathematics
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:It is well known that if a tree T of order n is not a star, then there exists an edge-disjoint placement of two copies of this tree into the complete graph K n . We improve this result by proving that actually two copies of T can be edge-disjointly packed in a much smaller graph, namely in T 4, the 4th power of T.
ISSN:0012-365X
1872-681X
DOI:10.1016/S0012-365X(99)00177-6