Algebraický pohled na strukturu tokově spojitých zobrazení

Hušek, Radek

We explore the structure of the cycle space of the graphs - most notably questions about nowhere-zero flows and cycle double covers. We touch several facets of this field. First we show that there are edge 2-connected graphs which distinguish Z2 2- and Z4- connectivity (group connectivity which is a strengthening of nowhere-zero flows). Then we examine a conjecture of Matt DeVos which asserts existence of group flows given existence of a graph homomorphism between suitable Cayley graphs. We introduce a strengthening of this conjecture called strong homomorphism property (SHP for short) which allows splitting vertices (and hence a reduction to cubic graphs). We conjecture that SHP holds for every graph and the smallest group in which the graph has a nowhere- zero flow and we prove that both SHP and the original conjecture imply existence of cycle double covers with few cycles. The question we discuss the most is counting objects on graphs - especially counting circuit double covers. We shows an almost exponential lower bound for graphs on surfaces with nice embeddings and we also show that this bound does not apply to Flower snarks. Then we shows quite precise bound for flower snarks and we also improve the lower bound for planar graphs to an exponential one. Along the way we build a framework for counting...

host :: přihlásit Digitální repozitář
		Hledej		Nový záznam		Nápověda		O repozitáři