Quadrilateral line graphs
Abstract
The quadrilateral line graph Q(G) of a graph G is that graph whose vertices are the edges of G and such that two vertices of Q(G) are adjacent if and only if the corresponding edges of G are adjacent and belong to a common 4-cycle. It is shown that if G is a graph every edge of which belongs to a 4-cycle and neither K2,3 nor K4 is a subgraph of G, then every component of Q(G) is eulerian. Also, if G is a connected graph of order at least 4, every two adjacent edges of which belong to a common 4-cycle, then Q(G) is hamiltonian. For n ≥ 2, the nth iterated quadrilateral line graph Qn (G) of a graph G is defined as Q(Qn-1(G)), where Q1(G) = Q(G) and Qn-1(G) is assumed to be nonempty. It is shown that if G is a graph containing 4-cycles that contains no subgraph isomorphic to K1 + P4, P3 × K2, K2,3, or K4, then the sequence {Qk(G)} converges to mC4 for some positive integer m.
