Opuscula Mathematica
Opuscula Math. 39, no. 6 (2019), 829-837

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