The 3-Xline graph of a given graph

Abstract

For a given graph $G$, a variation of its line graph is the 3-xline graph, where two 3-paths $P$ and $Q$ are adjacent in $G$ if $V(P)\cap V(Q)=\{v\}$ when $v$ is the interior vertex of both $P$ and $Q$. The vertices of the 3-xline graph $X{L}_3(G)$ correspond to the 3-paths in $G$, and two distinct vertices of the 3-xline graph are adjacent if and only if they are adjacent 3-paths in $G$. In this paper, we study 3-xline graphs for several classes of graphs, and show that for a connected graph $G$, the 3-xline graph is never isomorphic to $G$ and is connected only when $G$ is the star $K_{1,n}$ for $n=2$ or $n\ge 5$. We also investigate cycles in 3-xline graphs and characterize those graphs $G$ where $X{L}_3(G)$ is Eulerian.