A note on similar edges and edge-unique line graphs (Q1062999)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on similar edges and edge-unique line graphs |
scientific article |
Statements
A note on similar edges and edge-unique line graphs (English)
0 references
1985
0 references
A graph G is said to be vertex-unique if \(G\)-v\({}_ 1\) is not isomorphic to \(G\)-v\({}_ 2\) for any two distinct vertices of G. The notion of edge- uniqueness is defined in the obvious analogous manner. Let G be a finite connected graph (no loops or multiple edges) and L(G) its line graph. \textit{D. Merriell} proved that such a graph is edge-unique if and only if its line graph is vertex-unique [A note on uniquely reducible graphs, J. Comb. Theory, Ser. B 21, 282-284 (1976; Zbl 0305.05118)]. There are examples which demonstrate that both implications of the statement ''a graph is vertex-unique if and only if its line graph is edge-unique'' are false. The authors prove two results about connected graphs having no vertices of degree 2. The first is that L(G) is edge-unique whenever G is vertex-unique. The second is that if e and f are edges of L(G) such that L(G)-e is isomorphic to L(G)-f, then there is an automorphism of L(G) mapping the edge e onto the edge f. The proofs depend on the Krausz decomposition of L(G).
0 references
vertex-uniqueness
0 references
edge-uniqueness
0 references
line graph
0 references
Krausz decomposition
0 references