Forbidden Induced Subgraphs in Iterative Higher Order Line Graphs
摘要
Let G be a simple finite connected graph. The line graph L(G) of graph G is the graph whose vertices are the edges of G, where \(ef \in E(L(G))\) when \(e \cap f \ne \emptyset \) . Iteratively, the higher order line graphs are defined inductively as \(L^1(G) = L(G)\) and \(L^n(G) = L(L^{n-1}(G))\) for \(n \ge 2\) . In [1, 2], Beineke characterize line graphs in terms of nine forbidden subgraphs. Inspired by this result, in this paper, we characterize second order line graphs in terms of pure forbidden induced line subgraphs. We also give a sufficient list of forbidden subgraphs for a graph G such that G is a higher order line graph. We characterize all order line graphs of graph G with \(\Delta (G) = 3\) and 4.