$L(n)$ graphs are vertex-pancyclic and Hamilton-connected

Abstract

A graph $G$ of order $n>2$ is pancyclic if $G$ contains a cycle of length $l$ for each integer $l$ with $3\le l\le n$ and it is called vertex-pancyclic if every vertex is contained in a cycle of length $l$ for every $3\le l\le n$. A graph $G$ of order $n>2$ is Hamilton-connected if for any pair of distinct vertices $u$ and $v$, there is a Hamilton $u$-$v$ path, namely, there is a $u$-$v$ path of length $n-1$. The graph $B(n)$ is a graph with the vertex set $V=\{v|v\subset [n],|v|\in \{1,2\}\}$ and the edge set $E=\{\{v,w\}|v,w\in V,v\subset w$ or $w\subset v\}$, where $[n]=\{1,2,...,n\}$. We denote by $L(n)$ the line graph of $B(n)$, that is, $L(n)=L(B(n))$. In this paper, we show that the graph $L(n)$ is vertex-pancyclic and Hamilton-connected whenever $n\ge 6$.

7 pages. 1 figure

References in corpus (1)

• Johnson graphs are panconnected