Published July 2009
| Version Published
Book Section - Chapter
Open
On the graph of trees
-
1.
University of Pennsylvania
-
2.
Johns Hopkins University
-
3.
California Institute of Technology
Abstract
We consider an ldquon-graph of treesrdquo whose nodes are the set of trees of fixed order n, and in which two nodes are adjacent if one tree can be derived from the other through a single application of a local edge transformation rule. We derive an exact formula for the length of the shortest path from any node to any ldquocanonicalrdquo node in the n-graph of trees. We use this result to derive upper and lower bounds on the diameter of the n-graph of trees. We then propose a coordinate system that is convenient for studying the structure of the n-graph of trees, and in which trees having the same degree sequence are projected onto a single point.
Additional Information
© 2009 IEEE. C. K. Enyioha was supported by a Moore Foundation MURF during his stay at Caltech. D. C. Tarraf was supported by an internal grant from the Caltech Lee Center for Networking, AFOSR MURI grant number FA9550–06-1-0303 and NIH grant number R01 GM078992 while at Caltech.Attached Files
Published - 05281136.pdf
Files
05281136.pdf
Additional details
Identifiers
- Eprint ID
- 93262
- Resolver ID
- CaltechAUTHORS:20190226-100827411
Funding
- Gordon and Betty Moore Foundation
- Caltech Lee Center for Advanced Networking
- Air Force Office of Scientific Research (AFOSR)
- FA9550–06-1-0303
- NIH
- R01 GM078992
- Caltech Minorities Undergraduate Research Fellowship (MURF)
Dates
- Created
-
2019-02-26Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field