Opuscula Math. 39, no. 6 (2019), 829-837
https://doi.org/10.7494/OpMath.2019.39.6.829
Opuscula Mathematica
Lightweight paths in graphs
Jochen Harant
Stanislav Jendrol'
Abstract. Let \(k\) be a positive integer, \(G\) be a graph on \(V(G)\) containing a path on \(k\) vertices, and \(w\) be a weight function assigning each vertex \(v\in V(G)\) a real weight \(w(v)\). Upper bounds on the weight \(w(P)=\sum_{v\in V(P)}w(v)\) of \(P\) are presented, where \(P\) is chosen among all paths of \(G\) on \(k\) vertices with smallest weight.
Keywords: weighted graph, lightweight path.
Mathematics Subject Classification: 05C22, 05C3.
- J.C. Bermond, B. Jackson, F. Jaeger, Shortest coverings of graphs with cycles, Journal of Combinatorial Theory B 35 (1983), 297-308.
- M. Behrens, Leichteste Wege in Graphen, Bachelor Thesis, Technische Universität Ilmenau, 2018.
- I. Fabrici, J. Harant, S. Jendrol', Paths of low weight in planar graphs, Discuss. Math. Graph Theory 28 (2008), 121-135.
- I. Fabrici, S. Jendrol', Subgraphs with restricted degrees of their vertices in planar 3-connected graphs, Graphs Combin. 13 (1997), 245-250.
- A.V. Karzanov, Minimum mean weight cuts and cycles in directed graphs, [in:] Qualitative and Approximate Methods for Studying Operator Equations, Yaroslavl State University, Yaroslavl, 1985, pp. 72-83 [in Russian]; English translation in Amer. Math. Soc. Translations, Ser. 2, 158 (1994), 47-55.
- B. Korte, J. Vygen, Combinatorial Optimization, Springer, 2006.
- A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat. Cas. SAV (Math. Slovaca) 5 (1955), 101-113.
- A. Kotzig, Extremal polyhedral graphs, Ann. New York Acad. Sci. 319 (1979), 565-570.
- B. Mohar, Light paths in 4-connected graphs in the plane and other surfaces, J. Graph Theory 34 (2000), 170-179.
- W.T. Tutte, A theorem on planar graphs, Trans. Amer. Math. Soc. 82 (1956), 99-116.
- Jochen Harant
https://orcid.org/0000-0003-0456-624X- University of Technology, Department of Mathematics, Ilmenau, Germany
- Stanislav Jendrol'
- https://orcid.org/0000-0001-6869-2793
- Pavol Jozef Šafárik University, Institute of Mathematics, Košice, Slovakia
- Communicated by Adam Paweł Wojda.
- Received: 2019-06-27.
- Revised: 2019-09-12.
- Accepted: 2019-09-12.
- Published online: 2019-11-22.
