Currently displaying 1 – 15 of 15

Showing per page

Order by Relevance | Title | Year of publication

A Note on Barnette’s Conjecture

Jochen Harant — 2013

Discussiones Mathematicae Graph Theory

Barnette conjectured that each planar, bipartite, cubic, and 3-connected graph is hamiltonian. We prove that this conjecture is equivalent to the statement that there is a constant c > 0 such that each graph G of this class contains a path on at least c|V (G)| vertices.

Some news about the independence number of a graph

Jochen Harant — 2000

Discussiones Mathematicae Graph Theory

For a finite undirected graph G on n vertices some continuous optimization problems taken over the n-dimensional cube are presented and it is proved that their optimum values equal the independence number of G.

On domination in graphs

Frank GöringJochen Harant — 2005

Discussiones Mathematicae Graph Theory

For a finite undirected graph G on n vertices two continuous optimization problems taken over the n-dimensional cube are presented and it is proved that their optimum values equal the domination number γ of G. An efficient approximation method is developed and known upper bounds on γ are slightly improved.

A note on domination in bipartite graphs

Tobias GerlachJochen Harant — 2002

Discussiones Mathematicae Graph Theory

DOMINATING SET remains NP-complete even when instances are restricted to bipartite graphs, however, in this case VERTEX COVER is solvable in polynomial time. Consequences to VECTOR DOMINATING SET as a generalization of both are discussed.

On double domination in graphs

Jochen HarantMichael A. Henning — 2005

Discussiones Mathematicae Graph Theory

In a graph G, a vertex dominates itself and its neighbors. A subset S ⊆ V(G) is a double dominating set of G if S dominates every vertex of G at least twice. The minimum cardinality of a double dominating set of G is the double domination number γ × 2 ( G ) . A function f(p) is defined, and it is shown that γ × 2 ( G ) = m i n f ( p ) , where the minimum is taken over the n-dimensional cube C = p = ( p , . . . , p ) | p i I R , 0 p i 1 , i = 1 , . . . , n . Using this result, it is then shown that if G has order n with minimum degree δ and average degree d, then γ × 2 ( G ) ( ( l n ( 1 + d ) + l n δ + 1 ) / δ ) n .

Paths of low weight in planar graphs

Igor FabriciJochen HarantStanislav Jendrol' — 2008

Discussiones Mathematicae Graph Theory

The existence of paths of low degree sum of their vertices in planar graphs is investigated. The main results of the paper are: 1. Every 3-connected simple planar graph G that contains a k-path, a path on k vertices, also contains a k-path P such that for its weight (the sum of degrees of its vertices) in G it holds w G ( P ) : = u V ( P ) d e g G ( u ) ( 3 / 2 ) k ² + ( k ) 2. Every plane triangulation T that contains a k-path also contains a k-path P such that for its weight in T it holds w T ( P ) : = u V ( P ) d e g T ( u ) k ² + 13 k 3. Let G be a 3-connected simple planar graph of circumference...

On Longest Cycles in Essentially 4-Connected Planar Graphs

Igor FabriciJochen HarantStanislav Jendroľ — 2016

Discussiones Mathematicae Graph Theory

A planar 3-connected graph G is essentially 4-connected if, for any 3-separator S of G, one component of the graph obtained from G by removing S is a single vertex. Jackson and Wormald proved that an essentially 4-connected planar graph on n vertices contains a cycle C such that [...] . For a cubic essentially 4-connected planar graph G, Grünbaum with Malkevitch, and Zhang showed that G has a cycle on at least ¾ n vertices. In the present paper the result of Jackson and Wormald is improved. Moreover,...

Page 1

Download Results (CSV)