SOME NEW PROPERTIES OF CERTAIN PATH GRAPHS

Abstract

Path graphs were proposed as a generalization of line graphs. The 2-path graphdenoted by P₂(G), of a graph G has vertex set the set of all paths of length two. Two suchvertices are adjacent in the new graph if their union is a path of length three or a cycle oflength three. In this paper we characterize when P₂(G) is a path, a cycle or a tree. If G isconnected, we investigate when P₂(G) is complete and we study the path graphs of Bipartitegraphs. Also we characterize whenP₂(G) is isomorphic to the complement of G.