On the Determination Problem for \(P_3\) -Transformation of Graphs

Broersma and Hoede studied the \(P_3\)-transformation of graphs and claimed that it is an open problem to characterize all pairs of nonisomorphic connected graphs with isomorphic connected \(P_3\)-graphs. In this paper, we solve the problem to a great extent by proving that the \(P_3\)-transformation is one-to-one on all graphs with minimum degree greater than two. The only cases that remain open are cases where some degree is 1 or 2, and examples indicate that the problem seems to be difficult in these cases. This in some sense can be viewed as a counterpart with respect to \(P_3\)-graphs for Whitney’s result on line graphs.