Bi-traceable graphs, the intersection of three longest paths and Hippchens conjecture


Abstract in English

Let $P,Q$ be longest paths in a simple graph. We analyze the possible connections between the components of $Pcup Qsetminus (V(P)cap V(Q))$ and introduce the notion of a bi-traceable graph. We use the results for all the possible configurations of the intersection points when $#V(P)cap V(Q)le 5$ in order to prove that if the intersection of three longest paths $P,Q,R$ is empty, then $#(V(P)cap V(Q))ge 6$. We also prove Hippchens conjecture for $kle 6$: If a graph $G$ is $k$-connected for $kle 6$, and $P$ and $Q$ are longest paths in $G$, then $#(V(P)cap V(Q))ge 6$.

Download