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 \(XL_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 \geq 5\). We also investigate cycles in 3-xline graphs and characterize those graphs \(G\) where \(XL_3(G)\) is Eulerian.