Jan Volec

Hello, welcome to my REU page. My name is Jan Volec and I am an undergraduate student of Computer Science at the Faculty of Maths and Physics of Charles University in Prague. My main scientific interests are combinatorics, graph theory and algorithms.

REU 2009

The other members of our research group are Ondra Bílka, Jozef Jirásek, Pavel Klavík, Pavel Paták, Zuzka Safernová and Martin Tancer.

Problems

We are working together on several problems, some of them are described on pages of my colleagues. Our advisor is Aaron Jaggard.

Vertex cover in cubic graphs with large girth

Definitions

Cubic graph denotes a graph with all vertices of degree exactly 3.

Girth of a graph is the length of the smallest cycle. By large we mean that the bound holds when the girth is large enough.

Vertex cover is a subset of vertices such that every edge has at least one endpoint inside this subset.

Problem

We are interested in finding bounds for the size of minimum vertex cover in cubic graphs with large girth. Lower bound is 1/2×n (using connection between matching and vertex cover), from easy probabilistic argument we can obtain 5/8×n. Our aim is to improve this upper bound using better argument.

You can also download my introductory presentation.

Results

Using similar argument which was used for bounding the domination number, we derived that size of minimum vertex cover in cubic graph with large girth is less than 0.5835×n.

Current state

We are going to study Ph.D. thesis of Carlos Hoppen and try to apply his ideas to the problem.

References

D. Kral, P. Skoda, J.Volec, Domination number of cubic graphs with large girth, to appear in Journal of Graph Theory
D. Rautenbach, B. Reed, Domination in cubic graphs of large girth, CGGT 2007, LNCS vol. 4535, 2008, 186-190
C. Lowenstein, D. Rautenbach, Domination in graphs with minimum degree at least two and large girth, Graphs Combin. 24, 2008, 37-46