×

Nonexistence of triples of nonisomorphic connected graphs with isomorphic connected \(P_{3}\)-graphs. (English) Zbl 1159.05040

Summary: In the paper “Path graphs”, H.J. Broersma and C. Hoede [J. Graph Theory 13, No.4, 427–444 (1989; Zbl 0677.05068)] posed the 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.

MSC:

05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C75 Structural characterization of families of graphs

Citations:

Zbl 0677.05068
PDFBibTeX XMLCite
Full Text: arXiv EuDML EMIS