For full functionality of this site it is necessary to enable JavaScript. Here are the
instructions how to enable JavaScript in your web browser
.

Dissertation

2011-04-19

Das erste Fachkapitel ist der Berechnung von Kreispackungszahlen, d.h. der maximalen Größe kanten- bzw. eckendisjunkter Kreispackungen, gewidmet. Da diese Probleme bekanntermaßen sogar für subkubische Graphen schwer sind, behandelt der erste Abschnitt die Komplexität des Packens von Kreisen einer festen...

Article / Chapter

All rights reserved

2009-11-13

We prove several best-possible lower bounds in terms of the order and the average degree for the independence number of graphs which are connected and/or satisfy some odd girth condition. Our main result is the extension of a lower bound for the independence number of triangle-free graphs of maximum...

Article / Chapter

All rights reserved

2009-08-12

For $d,k\in \mathbb{N}$ with $k\leq 2d$, let $g(d,k)$ denote the infimum density of binary sequences $(x_i)_{i\in \mathbb{Z}}\in \{0,1\}^{\mathbb{Z}}$ which satisfy the minimum degree condition $\sum\limits_{j=1}^d(x_{i+j}+x_{i-j})\geq k$ for all $i\in\mathbb{Z}$ with $x_i=1$. We reduce the problem to...

Article / Chapter

All rights reserved

2009-04-29

We study the problems to nd a maximum packing of shortest edge-disjoint cycles in a graph of given girth g (g-ESCP) and its vertex-disjoint analogue g-VSCP. In the case g = 3, Caprara and Rizzi (2001) have shown that g-ESCP can be solved in polynomial time for graphs with maximum degree 4, but is APX-hard...

Article / Chapter

All rights reserved

2009-04-29

We study graphs G in which the maximum number of vertex-disjoint cycles \nu(G) is close to the cyclomatic number \mu(G) which is a natural upper bound for \nu(G). Our main result is the existence of a finite set P(k) of graphs for all k \in \mathbb{N}_0 such that every 2-connected graph G with \mu(G)...

Article / Chapter

All rights reserved

2008-12-03

For a graph G let \mu (G) denote the cyclomatic number and let \nu (G) denote the maximum number of edge-disjoint cycles of G. We prove that for every k \geq 0 there is a nite set P(k) such that every 2-connected graph G for which \mu (G) - \nu (G) = k arises by applying a simple extension rule to a...

Article / Chapter

All rights reserved

2008-06-20

We prove that every connected graph G of order n has a spanning tree T such that for every edge e of T the edge-cut defined in G by the vertex sets of the two components of T - e contains at most n^{\frac{3}{2}} many edges which solves a problem posed by Ostrovskii (Minimal congestion trees, Discrete...

Article / Chapter

All rights reserved

2008-06-20

For a graph G = (V,E) we consider vertex-k-labellings f : V \rightarrow {1,2,...,k} for which the induced edge weighting w : E \rightarrow {2,3,..., 2k} with w(uv) = f(u) + f(v) is injective or surjective or both. We study the relation between these labellings and the number theoretic notions of an additive...

Article / Chapter

All rights reserved

2008-01-30

We propose and study game-theoretic versions of independence in graphs. The games are played by two players - the aggressor and the defender - taking alternate moves on a graph G with tokens located on vertices from an independent set of G. A move of the aggressor is to select a vertex v of G. A move...