Názov:Real flows in graphs
Vedúci:doc. RNDr. Martin ©koviera, PhD.
Kµúčové slová:Real flows, real flow number, flow number, snark, Isaacs snarks
Abstrakt:A real flow on a graph is a flow with values in $\mathbb{R}$. A real nowhere-zero $r$-flow is a real flow~$\varphi$ with each edge satisfying the condition $1\leq|\varphi (e)|\leq r-1$. The real flow number $\Phi_\mathbb{R}(G)$ of a graph $G$ is the infimum of all reals $r$ such that $G$ has a real nowhere-zero $r$-flow. The purpose of this thesis is threefold. First, we summarize and systematize the fundamental results of real flow theory. We give new proofs of several known results, in particular we present a new direct combinatorial proof of the existence of the minimal real nowhere-zero $r$-flow. Second, we continue in the work of Z. Pan and X. Zhu who showed that for each rational number $r$ between $2$ and $5$ there exist a graph with real flow number $r$ [J. Graph Theory {\bf 49} (2003), 304-318]. We answer their question whether for each rational number $4<r\leq 5$ exists a snark with real flow number $r$ by constructing an infinite family of snarks for each such $r$. Finally, we obtain a lower bound on the real flow number of a snark of a given order and show that the Isaacs flower snarks attain this bound. As a consequence we show that the real flow number of the Isaacs snark $I_{2k+1}$ is $\Phi_\mathbb{R}(I_{2k+1})=4+1/k$, completing the upper bound of E. Steffen [J. Graph Theory {\bf 36} (2001), 24--34].

Súbory diplomovej práce: