Path graphs

H.J. Broersma, C. Hoede

Research output: Contribution to journalArticleAcademic

48 Citations (Scopus)
4345 Downloads (Pure)


The concept of a line graph is generalized to that of a path graph. The path graph Pk(G) of a graph G is obtained by representing the paths Pk in G by vertices and joining two vertices whenever the corresponding paths Pk in G form a path Pk+1 or a cycle Ck. P3-graphs are characterized and investigated on isomorphism and traversability. Trees and unicyclic graphs with hamiltonian P3-graphs are characterized.
Original languageEnglish
Pages (from-to)427-444
Number of pages18
JournalJournal of graph theory
Issue number4
Publication statusPublished - Sep 1989


  • IR-70879


Dive into the research topics of 'Path graphs'. Together they form a unique fingerprint.

Cite this