Nonexistence of triples of nonisomorphic connected graphs with isomorphic connected $P_{3}$-graphs

Summary

Summary: 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 P3-graph. In this paper, we show that there is no such triple, and thus completely solve this problem.

05C60, 05C75

Keywords/Phrases

path graph, connected, isomorphism