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

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.
  • Received: 2019-06-27.
  • Revised: 2019-09-12.
  • Accepted: 2019-09-12.
  • Published online: 2019-11-22.
Opuscula Mathematica - cover

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:
a .bib file (BibTeX),
a .ris file (RefMan),
a .enw file (EndNote)
or export to RefWorks.

In accordance with EU legislation we advise you this website uses cookies to allow us to see how the site is used. All data is anonymized.
All recent versions of popular browsers give users a level of control over cookies. Users can set their browsers to accept or reject all, or certain, cookies.