Search Results

Now showing 1 - 2 of 2

Some of the metrics are blocked by your
consent settings
Bi-traceable graphs, the intersection of three longest paths and Hippchen's conjecture
(Cornell University, 2021-01-19)
Let $P,Q$ be longest paths in a simple graph. We analyze the possible connections between the components of $P\cup Q\setminus (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 Hippchen's conjecture for $k\le 6$: If a graph $G$ is $k$-connected for $k\le 6$, and $P$ and $Q$ are longest paths in $G$, then $\#(V(P)\cap V(Q))\ge 6$.
Some of the metrics are blocked by your
consent settings
On two conjectures about the intersection of longest paths and cycles
(Elsevier B.V., 2024-11-01)
A conjecture attributed to Smith states that every two longest cycles in a k-connected graph intersect in at least k vertices. In this paper, we show that every two longest cycles in a k-connected graph on n vertices intersect in at least min⁡{n,8k−n−16} vertices, which confirms Smith's conjecture when k≥(n+16)/7. An analog conjecture for paths instead of cycles was stated by Hippchen. By a simple reduction, we relate both conjectures, showing that Hippchen's conjecture is valid when either k≤7 or k≥(n+9)/7.

3. Producción