# 9 documents found

Dissertation
2011-04-19

### On cycles and independence in graphs

﻿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
2009-11-13

### Independence, odd girth, and average degree

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
2009-08-12

### Minimum degree and density of binary sequences

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
2009-04-29

### On packing shortest cycles in graphs

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
2009-04-29

### Graphs with many vertex-disjoint cycles

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
2008-12-03

### Packing edge-disjoint cycles in graphs and the cyclomatic number

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
2008-06-20

### On spanning tree congestion

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