Forbidden induced subgraphs in iterative higher order line graphs
<|reference_start|>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 \neq \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 \geq 2$. In [Derived graphs and digraphs, Beitrage zur Graphentheorie (Teubner, Leipzig 1968), 17--33 (1968)], 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 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$.<|reference_end|>
@article{sanghi2024forbidden,
    title={Forbidden induced subgraphs in iterative higher order line graphs},
    author={Aryan Sanghi, Devsi Bantva and Sudebkumar Prasant Pal},
    journal={arXiv preprint arXiv:2410.04607},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.04607},
    primaryClass={math.CO cs.DM}
}