Faculty of Mathematics, Physics
and Informatics
Comenius University Bratislava

# Seminar of Graph Theory - Robert Lukoťka (15.12.2016)

## Thursday 15.12.2016 at 9:50, Lecture room M/213

13. 12. 2016 09.57 hod.

Robert Lukoťka:
Perfect matchings in highly cyclically connected regular graphs

Abstrakt:
Let \$G\$ be a \$d\$-regular cyclically \$(d-1+2k)\$-edge-connected graph (with \$k\geq 0\$) of even order. A leaf matching operation (LMO) on \$G\$ consists of removing a vertex of degree \$1\$ together with its neighbour from \$G\$. We show that for any given set \$X\$ of \$d-1+k\$ edges, there is no \$1\$-factor of \$G\$ avoiding \$X\$ if and only if either an isolated vertex can be obtained by a series of LMO operations in \$G-X\$ or \$G-X\$ has an independent set that contains more than half of the vertices of \$G\$. We show how signed graphs are useful to verify the two conditions of the statement by proving several statements on cubic graphs. We prove that for every integer \$k\$, if \$G\$ is sufficiently cyclically edge-connected, then for any three distant paths, there exists a \$2\$-factor of \$G\$ that contains one of these paths. For paths of length \$3\$ and \$4\$ we analyse the cases when only one or two (possibly intersecting) paths are given. As a consequence, we obtain that for cyclically 7-edge-connected cubic graph \$G\$ and a vertex \$v\$ of \$G\$ there exists a \$2\$-factor such that \$v\$ is in cycle of length greater than \$7\$.

This is joint work with Edita Rollová (University of West Bohemia, Pilsen, Czech Republic).