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
All rights reserved
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
All rights reserved
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
All rights reserved
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
All rights reserved
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
All rights reserved
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
All rights reserved
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
All rights reserved
2008-06-20

Edge-injective and edge-surjective vertex labellings

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

Chiraptophobic cockroaches evading a torch light

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...