Li, Xueliang; Liu, Yan

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

Electron. J. Comb. 15(1), Research Paper R31, 8 p. (2008)


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.

Mathematics Subject Classification

05C60, 05C75


path graph, connected, isomorphism