Balanced caterpillars of maximum degree 3 and with hairs of arbitrary length are subgraphs of their optimal hypercube

Publisher： John Wiley & Sons Inc

E-ISSN： 1097-0118|87|4|561-580

ISSN： 0364-9024

Source： JOURNAL OF GRAPH THEORY, Vol.87, Iss.4, 2018-04, pp. : 561-580

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

AbstractA 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 2n 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.

Related content

Long cycles in random subgraphs of graphs with large minimum degree

By  

RANDOM STRUCTURES AND ALGORITHMS, Vol. 45, Iss. 4, 2014-12 ,pp. : 764-767 (4)

John Wiley & Sons Inc

Access to resources Recommend Favorite

Computing maximum upward planar subgraphs of single-source embedded digraphs

By Rextin Aimal  

Journal of Combinatorial Optimization, Vol. 25, Iss. 3, 2013-04 ,pp. : 368-392 (25)

Springer Publishing Company

Access to resources Recommend Favorite

A self-stabilizing 3-approximation for the maximum leaf spanning tree problem in arbitrary networks

By Kamei Sayaka  

Journal of Combinatorial Optimization, Vol. 25, Iss. 3, 2013-04 ,pp. : 430-459 (30)

Springer Publishing Company

Access to resources Recommend Favorite

On the Maximum Arc Length of Monotonic Functions

By Deĺeglise Marc   Markoe Andrew  

American Mathematical Monthly, Vol. 121, Iss. 8, 2014-10 ,pp. : 689-699 (11)

Mathematical Association of America

Access to resources Recommend Favorite

A 3-Approximation Algorithm for Finding Optimum 4,5-Vertex-Connected Spanning Subgraphs

By Dinitz Y.   Nutov Z.  

Journal of Algorithms, Vol. 32, Iss. 1, 1999-07 ,pp. : 31-40 (10)

Academic Press

Access to resources Recommend Favorite