Premium
P 3 ‐isomorphisms for graphs
Author(s) -
Aldred R. E. L.,
Ellingham M. N.,
Hemminger R. L.,
Jipsen P.
Publication year - 1997
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199709)26:1<35::aid-jgt5>3.0.co;2-i
Subject(s) - combinatorics , mathematics , chordal graph , cograph , discrete mathematics , indifference graph , pathwidth , vertex (graph theory) , symmetric graph , adjacency list , 1 planar graph , line graph , graph , voltage graph
The P 3 ‐ graph of a finite simple graph G is the graph whose vertices are the 3‐vertex paths of G , with adjacency between two such paths whenever their union is a 4‐vertex path or a 3‐cycle. In this paper we show that connected fnite simple graphs G and H with isomorphic P 3 ‐graphs are either isomorphic or part of three exceptional families. We also characterize all isomorphisms between P 3 ‐graphs in terms of the original graphs. © 1997 John Wiley & Sons, Inc. J Graph Theory 26:35–51, 1997