zbMATH — the first resource for mathematics

Spanning spiders and light-splitting switches. (English) Zbl 1044.05048
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.

05C45 Eulerian and Hamiltonian graphs
05C90 Applications of graph theory
05C05 Trees
Full Text: DOI
[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
[3] B. Beauquier, J.-C. Bermond, L. Gargano, P. Hell, S. Perennes, U. Vaccaro, Graph problems arising from wavelength-routing in all-optical networks, Proceedings of WOCS, Geneve, Switzerland, 1997.
[4] Chen, G; Schelp, R.H, Hamiltonicity for K1,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
[7] T. Feder, R. Motwani, C. Subi, Finding long paths and cycles in sparse Hamiltonian graphs, Proceedings of the ACM Symposium on Theory of Computing, STOC’00, 2000. · Zbl 1296.05114
[8] L. Gargano, M. Hammar, There are spanning spiders in dense graphs (and we know how to find them), ICALP’03, June 30-July 04, 2002, Eindhoven, The Netherlands. · Zbl 1039.68095
[9] L. Gargano, P. Hell, L. Stacho, U. Vaccaro, Spanning trees with bounded number of branch vertices, ICALP’02, July 8-13, Málaga, Spain, 2002. · Zbl 1056.68587
[10] Gargano, L; Vaccaro, U, Routing in all-optical networks: algorithmic and graph-theoretic problems, (), 555-578 · Zbl 0980.05046
[11] R.M. Karp, Reducibility among combinatorial problems, in: Complexity of Computer Computations (Proceedings of the Symposium, IBM Thomas J. Watson Research Center, Yorktown Heights, N.Y., 1972), Plenum, New York, 1972, pp. 85-103.
[12] J. Könemann, R. Ravi, A matter of degree: improved approximation algorithms for degree-bounded minimum spanning trees, Proceedings of ACM Symposium on Theory of Computing, STOC’00, 2000.
[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 K1,3-free graphs, J. Changsha railway inst., 4, 105-106, (1986)
[17] L.R. Markus, Hamiltonian results in K1,r-free graphs, in: Proceedings of the 24th Southeastern International Conference on Combinatorics, Graph Theory, and Computing, Vol. 98, Boca Raton, Florida, 1993, pp. 143-149. · Zbl 0801.05049
[18] Matthews, M.M; Sumner, D.P, Longest paths and cycles in K1,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, (), 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.