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.
2003
3540404937
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11386/1000152
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 11
social impact