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.

Full text (pdf)

1. J.C. Bermond, B. Jackson, F. Jaeger, Shortest coverings of graphs with cycles, Journal of Combinatorial Theory B 35 (1983), 297-308.
2. M. Behrens, Leichteste Wege in Graphen, Bachelor Thesis, Technische Universität Ilmenau, 2018.
3. I. Fabrici, J. Harant, S. Jendrol', Paths of low weight in planar graphs, Discuss. Math. Graph Theory 28 (2008), 121-135.
4. I. Fabrici, S. Jendrol', Subgraphs with restricted degrees of their vertices in planar 3-connected graphs, Graphs Combin. 13 (1997), 245-250.
5. 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.
6. B. Korte, J. Vygen, Combinatorial Optimization, Springer, 2006.
7. A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat. Cas. SAV (Math. Slovaca) 5 (1955), 101-113.
8. A. Kotzig, Extremal polyhedral graphs, Ann. New York Acad. Sci. 319 (1979), 565-570.
9. B. Mohar, Light paths in 4-connected graphs in the plane and other surfaces, J. Graph Theory 34 (2000), 170-179.
10. W.T. Tutte, A theorem on planar graphs, Trans. Amer. Math. Soc. 82 (1956), 99-116.
• Communicated by Adam Paweł Wojda.
• Revised: 2019-09-12.
• Accepted: 2019-09-12.
• Published online: 2019-11-22.