×
Gargano, Luisa; Hammar, Mikael; Hell, Pavol; Stacho, Ladislav; Vaccaro, Ugo

Spanning spiders and light-splitting switches. (English) Zbl 1044.05048

Discrete Math. 285, No. 1-3, 83-95 (2004).
Summary: Motivated by a problem in the design of optical networks, we ask when a graph has a spanning spider (subdivision of a star), or, more generally, a spanning tree with a bounded number of branch vertices. We investigate the existence of these spanning subgraphs in analogy to classical studies of Hamiltonicity.

Cited in 4 Reviews
Cited in 29 Documents

MSC:

05C45 Eulerian and Hamiltonian graphs
05C90 Applications of graph theory
05C05 Trees

Keywords:

Spanning tree; Branch vertex; Hamilton path
PDF BibTeX XML Cite
\textit{L. Gargano} et al., Discrete Math. 285, No. 1--3, 83--95 (2004; Zbl 1044.05048)
Full Text: DOI

References:

[1] Aung, M.; Kyaw, A., Maximal trees with bounded maximum degree in a graph, Graphs Combin., 14, 209-221 (1998) · Zbl 0911.05029
[2] Bazgan, C.; Santha, M.; Tuza, Z., On the approximation of finding a(nother) Hamiltonian cycle in cubic Hamiltonian graphs, J. Algorithms, 31, 1, 249-268 (1999) · Zbl 0919.05039
[4] Chen, G.; Schelp, R. H., Hamiltonicity for \(K_{1,r}\)-free graphs, J. Graph Theory, 20, 4, 423-439 (1995) · Zbl 0843.05072
[5] Chvátal, V.; Erdős, P., A note on Hamiltonian circuits, Discrete Math., 2, 111-113 (1972) · Zbl 0233.05123
[6] Dirac, G. A., Some theorems on abstract graphs, Proc. London Math. Soc. (3), 2, 69-81 (1952) · Zbl 0047.17001
[10] Gargano, L.; Vaccaro, U., Routing in all-optical networks: algorithmic and graph-theoretic problems, (Althofer, I.; etal., Numbers, Information and Complexity (2000), Kluwer Academic Publisher: Kluwer Academic Publisher Dordrecht), 555-578 · Zbl 0980.05046
[13] Krager, D.; Motwani, R.; Ramkumar, D. S., On approximating the longest path in a graph, Algorithmica, 18, 82-98 (1997) · Zbl 0876.68083
[14] Kyaw, A., A sufficient condition for a graph to have a \(k\) tree, Graphs Combin., 17, 113-121 (2001) · Zbl 0991.05032
[15] Las Vergnas, M., Sur une proprieté des arbres maximaux dans un graphe, C. R. Acad. Sci. Paris, Ser. A, 271, 1297-1300 (1971) · Zbl 0221.05053
[16] Liu, Y.; Tian, F.; Wu, Z., Some results on longest paths and cycles in \(K_{1,3}\)-free graphs, J. Changsha Railway Inst., 4, 105-106 (1986)
[18] Matthews, M. M.; Sumner, D. P., Longest paths and cycles in \(K_{1,3}\)-free graphs, J. Graph Theory, 9, 2, 269-277 (1985) · Zbl 0591.05041
[19] Ore, O., A note on Hamilton circuits, Am. Math. Monthly, 67, 55 (1960) · Zbl 0089.39505
[20] Raghavachari, B., Algorithms for finding low-degree structures, (Hochbaum, D. S., Approximation Algorithms for NP-Hard Problems (1997), PWS Publishing Company: PWS Publishing Company Boston), 266-295
[21] Thomassen, C., Hypohamiltonian and hypotraceable graphs, Discrete Math., 9, 91-96 (1974) · Zbl 0278.05110
[22] Thomassen, C., Planar cubic hypo-Hamiltonian and hypotraceable graphs, J. Combin. Theory Ser. B, 30, 1, 36-44 (1981) · Zbl 0388.05033
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.