15 problems

Let $G$ be a $k$-connected graph. A longest path is a path of maximum length in $G$. Hippchen's conjecture. Every pair of longest paths in $G$ intersect in at least $k$ vertices. T…

Let a longest path of a connected graph be a path of maximum length. Zamfirescu's conjecture. For every connected graph, any $3$ of its longest paths have a common vertex. This is…

Let $n$ and $k$ be positive integers, and let $\Pi(n;k)$ be the class of graphs of order $n$ whose longest path has order $n-k$ and such that deleting any set of $k$ vertices leave…

Let $G$ be a $k$-connected graph with $k e 1$ and let $x,y$ be two distinct vertices of $G$. An $(x,y)$-path is a path whose endpoints are $x$ and $y$; a path is longest if it…

Let $k\geq 1$ and $r\leq k$. A graph is $k$-connected if, for any two distinct vertices, it has $k$ internally disjoint paths between them. A longest path is a path of maximum leng…

Let $G$ be a connected graph, and let $\alpha(G)$ denote its independence number. A vertex of $G$ is a Gallai vertex if it belongs to every longest path in $G$. Gallai vertex conje…

Let $G$ be a connected graph, and let $P$, $Q$, and $R$ be any three longest paths in $G$. Common-vertex conjecture. The paths $P$, $Q$, and $R$ have a common vertex. This is known…

Let $G$ be a 5-connected graph. 5-connected Hippchen conjecture. Every pair of longest paths intersect each other in at least five vertices. The paper proves the analogous statemen…

Let $G$ be a $k$-connected graph on $n$ vertices. Weak Hippchen conjecture. If $k \geq n/4$, then every pair of longest paths intersect in at least $k$ vertices. This weakens Hippc…

Independence-five Gallai vertex conjecture. If

Independence-five Gallai vertex conjecture. If

Let $G$ be a connected graph of order $n$, let $\mathcal{L}(G)$ denote the set of longest paths of $G$, and let $f(G,\mathcal{P})$ denote the distance parameter for a subset…

Let a longest path of a connected graph be a path of maximum length. Common-vertex conjecture. For every connected graph, any $k$ of its longest paths have a common vertex for…

Sublinear bound conjecture. There exists a sublinear non-decreasing function $g$ such that, for every connected graph $G$ of order $n$ and every subset…

Let $G$ be a connected graph, let $\mathcal{L}(G)$ be the set of longest paths of $G$, and let $f(G,\mathcal{P})$ be the minimum, over vertices $v\in V(G)$, of…