Nonexistence of Triples of Nonisomorphic Connected Graphs with Isomorphic Connected $P_3$-graphs

Abstract

In the paper "Broersma and Hoede, Path graphs, J. Graph Theory 13 (1989) 427-444", the authors asked a problem whether there is a triple of mutually nonisomorphic connected graphs which have an isomorphic connected $P_3$-graph. In this paper, we show that there is no such triple, and thus completely solve this problem.