A spanning spider for a graph G is a spanning tree T of G with at most one vertex having degree three or more in T. In this paper we give densitycriteria for the existence of spanning spiders in graphs. We constructivelypro ve the following result: Given a graph G with n vertices, if the degree sum of anyindep endent triple of vertices is at least n − 1, then there exists a spanning spider in G. We also studythe case of bipartite graphs and give densityconditions for the existence of a spanning spider in a bipartite graph. All our proofs are constructive and implythe existence of polynomial time algorithms to construct the spanning spiders. The interest in the existence of spanning spiders originallyarises in the realm of multicasting in optical networks. However, the graph theoretical problems discussed here are interesting in their own right.
There are Spanning Spiders in Dense Graphs (and we know how to find them)
GARGANO, Luisa;
2003-01-01
Abstract
A spanning spider for a graph G is a spanning tree T of G with at most one vertex having degree three or more in T. In this paper we give densitycriteria for the existence of spanning spiders in graphs. We constructivelypro ve the following result: Given a graph G with n vertices, if the degree sum of anyindep endent triple of vertices is at least n − 1, then there exists a spanning spider in G. We also studythe case of bipartite graphs and give densityconditions for the existence of a spanning spider in a bipartite graph. All our proofs are constructive and implythe existence of polynomial time algorithms to construct the spanning spiders. The interest in the existence of spanning spiders originallyarises in the realm of multicasting in optical networks. However, the graph theoretical problems discussed here are interesting in their own right.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.