Domination in Graphs of Minimum Degree at least Two and large Girth

We prove that for graphs of order $n$, minimum degree $\delta\geq 2$ and girth $g\geq 5$ the domination number $\gamma$ satisfies $\gamma\leq\left(\frac{1}{3}+\frac{2}{3g}\right)n$. As a corollary this implies that for cubic graphs of order $n$ and girth $g\geq 5$ the domination number $\gamma$ satisfies $\gamma \leq \left(\frac{44}{135}+\frac{82}{135g}\right)n$ which improves recent results due to Kostochka and Stodolsky (An upper bound on the domination number of $n$-vertex connected cubic graphs, {\it manuscript} (2005)) and Kawarabayashi, Plummer and Saito (Domination in a graph with a 2-factor, {\it J. Graph Theory} {\bf 52} (2006), 1-6) for large enough girth.

Join work with Christian Loewenstein and Jochen Harant.

Some Optimization Results for Boolean Functions

We present recent results related to the optimization of Boolean functions with applications in VLSI design. In a first part we outline an algorithm for the redesign of so-called critical paths. The corresponding task consists in finding logically equivalent alternative circuit representations of Boolean functions with improved delay properties. In the second part we discuss generalizations of read-once functions that were recently studied by Golumbic et al. also in the context of VLSI design. We present simpler proofs of some of their results and discuss an interesting conjecture relating this concept to graph-theoretical covering problems.

Joint work with Christian Szegedy and Juergen Werber.