Jochen Harant
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Jochen Harant has a total of 21 co-authors. Here are the top co-authors by number of shared publications:
- Stanislav Jendrol'
Institute of Mathematics, P. J. Šafárik University, Košice, Slovakia
5 shared publications - Igor Fabrici
Institute of Mathematics Pavol Jozef Šafárik University Košice Slovakia
2 shared publications - Peter Recht
Lehrstuhl für Operations Research und Wirtschaftsinformatik, Universität Dortmund, D-44227 Dortmund, Germany
2 shared publications - Samuel Mohr
Fakulta informatiky Masarykova univerzita Brno Brno Czech Republic
2 shared publications - Tomáš Madaras
Institute of Mathematics, Košice, Slovakia
2 shared publications - Carol T. Zamfirescu
Department of Mathematics Computer Science and Statistics Ghent University 9000 Ghent Belgium
1 shared publication
Latest Publications
- 1 January 2023
- Published by University of Zielona Góra, Poland in Discussiones Mathematicae Graph Theory
- Vol. 43 (3) , 809-824
New bounds on domination and independence in graphs
- 1 January 2023
- Published by University of Zielona Góra, Poland in Discussiones Mathematicae Graph Theory
- Vol. 43 (3) , 809-824
New bounds on domination and independence in graphs
- 10 February 2020
- Published by Wiley in Journal of Graph Theory
- Vol. 95 (1) , 125-137
Long cycles and spanning subgraphs of locally maximal 1‐planar graphs
A graph is 1‐planar if it has a drawing in the plane such that each edge is crossed at most once by another edge. Moreover, if this drawing has the additional property that for each crossing of two edges the end vertices of these edges induce a complete subgraph, then the graph is locally maximal 1‐planar. For a 3‐connected locally maximal 1‐planar graph G, we show the existence of a spanning 3‐connected planar subgraph and prove that G is Hamiltonian if G has at most three 3‐vertex‐cuts, and that G is traceable if G has at most four 3‐vertex‐cuts. Moreover, infinitely many nontraceable 5‐connected 1‐planar graphs are presented.
- 10 February 2020
- Published by Wiley in Journal of Graph Theory
- Vol. 95 (1) , 125-137
Long cycles and spanning subgraphs of locally maximal 1‐planar graphs
A graph is 1‐planar if it has a drawing in the plane such that each edge is crossed at most once by another edge. Moreover, if this drawing has the additional property that for each crossing of two edges the end vertices of these edges induce a complete subgraph, then the graph is locally maximal 1‐planar. For a 3‐connected locally maximal 1‐planar graph G, we show the existence of a spanning 3‐connected planar subgraph and prove that G is Hamiltonian if G has at most three 3‐vertex‐cuts, and that G is traceable if G has at most four 3‐vertex‐cuts. Moreover, infinitely many nontraceable 5‐connected 1‐planar graphs are presented.
- 1 January 2019
- Published by AGH University Press in Opuscula Mathematica
- Vol. 39 (6) , 829-837
Lightweight paths in graphs
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.- 1 January 2019
- Published by AGH University Press in Opuscula Mathematica
- Vol. 39 (6) , 829-837
Lightweight paths in graphs
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.- 1 November 2016
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 55, 143-146
On Longest Cycles in Essentially 4-connected Planar Graphs
- 1 November 2016
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 55, 143-146
On Longest Cycles in Essentially 4-connected Planar Graphs
- 11 March 2014
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 165, 146-151
An upper bound on the sum of powers of the degrees of simple 1-planar graphs
- 11 March 2014
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 165, 146-151
An upper bound on the sum of powers of the degrees of simple 1-planar graphs
- 1 December 2011
- Published by Wiley in Journal of Graph Theory
- Vol. 71 (3) , 245-259
The potential of greed for independence
The well‐known lower bound on the independence number of a graph due to Caro (Technical Report, Tel‐Aviv University, 1979) and Wei (Technical Memorandum, TM 81 ‐ 11217 ‐ 9, Bell Laboratories, 1981) can be established as a performance guarantee of two natural and simple greedy algorithms or of a simple randomized algorithm. We study possible generalizations and improvements of these approaches using vertex weights and discuss conditions on so‐called potential functions pG: V(G)→ℕ0 defined on the vertex set of a graph G for which suitably modified versions of the greedy algorithms applied to G yield independent sets I with . We provide examples of such potentials, which lead to bounds improving the bound due to Caro and Wei. Furthermore, suitably adapting the randomized algorithm we give a short proof of Thiele's lower bound on the independence number of a hypergraph (T. Thiele, J Graph Theory 30 (1999), 213–221).
- 1 December 2011
- Published by Wiley in Journal of Graph Theory
- Vol. 71 (3) , 245-259
The potential of greed for independence
The well‐known lower bound on the independence number of a graph due to Caro (Technical Report, Tel‐Aviv University, 1979) and Wei (Technical Memorandum, TM 81 ‐ 11217 ‐ 9, Bell Laboratories, 1981) can be established as a performance guarantee of two natural and simple greedy algorithms or of a simple randomized algorithm. We study possible generalizations and improvements of these approaches using vertex weights and discuss conditions on so‐called potential functions pG: V(G)→ℕ0 defined on the vertex set of a graph G for which suitably modified versions of the greedy algorithms applied to G yield independent sets I with . We provide examples of such potentials, which lead to bounds improving the bound due to Caro and Wei. Furthermore, suitably adapting the randomized algorithm we give a short proof of Thiele's lower bound on the independence number of a hypergraph (T. Thiele, J Graph Theory 30 (1999), 213–221).
- 16 December 2010
- Published by Wiley in Journal of Graph Theory
- Vol. 67 (2) , 112-123
Upper bounds on the sum of powers of the degrees of a simple planar graph
- 16 December 2010
- Published by Wiley in Journal of Graph Theory
- Vol. 67 (2) , 112-123
Upper bounds on the sum of powers of the degrees of a simple planar graph
- 28 July 2010
- Published by Elsevier in Discrete Mathematics
- Vol. 310 (13-14) , 1974-1978
Packing disjoint cycles over vertex cuts
- 28 July 2010
- Published by Elsevier in Discrete Mathematics
- Vol. 310 (13-14) , 1974-1978
Packing disjoint cycles over vertex cuts
- 6 May 2010
- Published by Elsevier in Discrete Mathematics
- Vol. 310 (9) , 1456-1462
Packing edge-disjoint cycles in graphs and the cyclomatic number
- 6 May 2010
- Published by Elsevier in Discrete Mathematics
- Vol. 310 (9) , 1456-1462
Packing edge-disjoint cycles in graphs and the cyclomatic number
- Open Access
- 1 January 2008
- Published by University of Zielona Góra, Poland in Discussiones Mathematicae Graph Theory
- Vol. 28 (1) , 121
Paths of low weight in planar graphs
Discussiones Mathematicae Graph Theory
- 1 January 2008
- Published by University of Zielona Góra, Poland in Discussiones Mathematicae Graph Theory
- Vol. 28 (1) , 121
Open AccessPaths of low weight in planar graphs
Discussiones Mathematicae Graph Theory