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.
References
[1]
Ore, O. Theory of Graphs; American Mathematical Society: Providence, RI, USA, 1962.
[2]
Lovásv, L. Vertex Packing Algorithms. In Automata, Languages, and Programming, 12th Colloquium Nafplion, Greece, 15–19 July, 1985; Brauer, W., Ed.; Springer-Verlag: Berlin, Germany, 1985; pp. 1–14.
[3]
Brigham, R.; Dutton, R. A compilation of relations between graph invariants. Networks 1985, 15, 73–107, doi:10.1002/net.3230150108.
[4]
Hemminger, R.; Beineke, L. Line Graphs and Line Digraphs. In Selected Topics in Graph Theory; Beineke, L., Wilson, R., Eds.; Academic Press: London, UK, 1978; pp. 271–305.
[5]
Hocking, J.; Young, G. Topology; Addison-Wesley: Reading, MA, USA, 1961; p. 242.
[6]
Hu, S. Homology Theory:A First Course in Algebraic Topology; Holden-Day: San Francisco, CA, USA, 1966; p. 119.
[7]
Behzad, M.; Chartrand, G.; Lesniak-Foster, L. Graphs and Digraphs; Wadsworth International Group: Belmont, CA, USA, 1979; p. 190.
[8]
Rotman, J. An Introduction to Algebraic Topology; Springer-Verlag: New York, NY, USA, 1988; p. 154.
[9]
Berge, C. Graphs and Hypergraphs; North-Holland: London, UK, 1973; p. 413.
