Longest Path Starting at a Vertex

Abstract

Let $G$ be a connected graph of order $n$. Denote $p_u(G)$ the order of a longest path starting at vertex $u$ in $G$. In this paper, we prove that if $G$ has more than $t(\genfrac{}{}{0ex}{}{k}{2})+(\genfrac{}{}{0ex}{}{p+1}{2})+(n-k-1)$ edges, where $k\ge 2$, $n=t(k-1)+p+1$, $t\ge 0$ and $0\le p\le k-1$, then $p_u(G)>k$ for each vertex $u$ in $G$. By this result, we give an alternative proof of a result obtained by P. Wang et al. that if $G$ is a 2-connected graph on $n$ vertices and with more than $t(\genfrac{}{}{0ex}{}{k-2}{2})+(\genfrac{}{}{0ex}{}{p}{2})+(2n–3)$ edges, where $k\ge 3$, $n-2=t(k-2)+p$, $t\ge 0$ and $0\le p\le k-2$, then each edge of $G$ lies on a cycle of order more than $k$.