Lightweight paths in graphs

• Autorzy: Harant Jochen , Jendrol Stanislav

Identyfikatory

DOI

10.7494/OpMath.2019.39.6.829

• Języki publikacji: EN

Abstrakty

EN

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 ∈ V(G) a real weight w(y). Upper bounds on the weight [formula] of P are presented, where P is chosen among all paths of G on k vertices with smallest weight.

Słowa kluczowe

EN

weighted graph; lightweight path

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2019
• Tom: Vol. 39, no. 6
• Strony: 829--837
• Opis fizyczny: Bibliogr. 10 poz.

Twórcy

autor

Harant Jochen

• University of Technology Department of Mathematics Ilmenau, Germany

autor

Jendrol Stanislav

• Pavol Józef Śafarik University Institute of Mathematics Kosice, Slovakia

Bibliografia

• [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 Universitat 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 //.-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.