Name
Title | ||
|---|---|---|
Balanced caterpillars of maximum degree 3 and with hairs of arbitrary length are subgraphs of their optimal hypercube. |
Abstract | ||
|---|---|---|
A caterpillar C is a tree having a path that contains all vertices of C of degree at least 3. We show in this article that every balanced caterpillar with maximum degree 3 and 2(n) vertices is a subgraph of the n-dimensional hypercube. This solves a long-standing open problem and generalizes a result of Havel and Liebl (1986), who considered only such caterpillars that have a path containing all vertices of degree at least 2. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1002/jgt.22175 | JOURNAL OF GRAPH THEORY |
Keywords | Field | DocType |
caterpillar,graph embeddings,hypercubes | Discrete mathematics,Topology,Combinatorics,Degree (graph theory),Mathematics,Hypercube | Journal |
Volume | Issue | ISSN |
87.0 | 4.0 | 0364-9024 |
Citations | PageRank | References |
0 | 0.34 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Burkhard Monien | 1 | 2199 | 279.35 |
| Gerd Wechsung | 2 | 389 | 36.52 |