ARTICLE DOWNLOAD

A note on spanning trees with a specified degree sequence

10$
ARTICLE DOWNLOAD

A note on spanning trees with a specified degree sequence

10$

María Elena Martínez-Cuero & Eduardo Rivera-Campo 

Introduction

Ore proved that if G is a graph with n vertices such that d(u)+d(v)≥n−1d(u)+d(v)≥n−1 for each pair u, v of non-adjacent vertices, then G contains a Hamiltonian path. This result has been generalized in many directions.

Win showed that if r≥2r≥2 is an integer and G is a connected graph with n vertices such that d(u1)+d(u2)+⋯+d(ur)≥n−1d(u1)+d(u2)+⋯+d(ur)≥n−1 for each set of r independent vertices of G, then G has a spanning tree with maximum degree at most r.

Years later, Broersma and Tuinstra showed that if s≥2s≥2 is an integer and G is a connected graph with n vertices such that d(u)+d(v)≥n−s+1d(u)+d(v)≥n−s+1 for each pair u, v of non-adjacent vertices, then G contains a spanning tree with at most s vertices with degree 1.

Rivera-Campo gave a condition on the graph G that bounds the degree of each vertex in a certain spanning tree T of G and the number of vertices of T with degree 1.

Only units of this product remain
Year 2020
Language English
Format PDF
DOI 10.1007/s40590-019-00250-6