×

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.

MSC:

05C45 Eulerian and Hamiltonian graphs
05C90 Applications of graph theory
05C05 Trees
PDFBibTeX XMLCite
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
[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.; 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 \(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
[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.; 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.; 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.; 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, (Althofer, I.; etal., Numbers, Information and Complexity (2000), Kluwer Academic Publisher: Kluwer Academic Publisher Dordrecht), 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.; 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.; 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 \(K_{1,3}\)-free graphs, J. Changsha Railway Inst., 4, 105-106 (1986)
[17] L.R. Markus, Hamiltonian results in \(K_{1,r}\); L.R. Markus, Hamiltonian results in \(K_{1,r}\) · Zbl 0801.05049
[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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.