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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Forbidden Induced Subgraphs in Iterative Higher Order Line Graphs

  • Aryan Sanghi,
  • Devsi Bantva,
  • Sudebkumar Prasant Pal

摘要

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.