Topological Invariance under Line Graph Transformations

Symmetry

关键词: algebraic graph theory;    line graph;    Krausz decomposition;    homology;    graph invariant;    Euler characteristic;   

DOI  :  10.3390/sym4020329

来源: mdpi

【 摘 要 】

It is shown that the line graph transformation G ↦ L(G) of a graph G preserves an isomorphic copy of G as the nerve of a finite simplicial complex K which is naturally associated with the Krausz decomposition of L(G). As a consequence, the homology of K is isomorphic to that of G. This homology invariance algebraically confirms several well known graph theoretic properties of line graphs and formally establishes the Euler characteristic of G as a line graph transformation invariant.

【 授权许可】

CC BY   
© 2012 by the authors; licensee MDPI, Basel, Switzerland.