On the relation between connectivity, independence and generalized caterpillars

2013/02/20 by M. Pedramfar, Pedramfar, M., M. Shokrian +3
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1302.5038

arxiv created 2013/02/20 · arxiv updated 2013/02/21

Abstract

A spanning generalized caterpillar is a spanning tree in which all vertices of degree more than two are on a path. In this note, we find a relation between the existence of spanning generalized caterpillar and the independence and connectivity number in a graph. We also point out to an error in a "theorem" in the paper "Spanning spiders and light-splitting switches", by L. Gargano et al. in Discrete Math. (2004), and find out a relation between another mentioned theorem and the existence of spanning generalized caterpillar.

Related

• Balanced Spanning Caterpillars
• Connectivity keeping caterpillars and spiders in bipartite graphs with connectivity at most three
• Caterpillars in Erdős-Hajnal
• Another Enumeration of Caterpillar Trees
• Caterpillars with n vertices are reconstructible from subgraphs with at most n/2+1 vertices