Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2410.04607 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929530000637952 |
|---|---|
| author | Sanghi, Aryan Bantva, Devsi Pal, Sudebkumar Prasant |
| author_facet | Sanghi, Aryan Bantva, Devsi Pal, Sudebkumar Prasant |
| contents | 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 $Δ(G) = 3$ and $4$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_04607 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Forbidden induced subgraphs in iterative higher order line graphs Sanghi, Aryan Bantva, Devsi Pal, Sudebkumar Prasant Combinatorics Discrete Mathematics 05C76, 05C75 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 $Δ(G) = 3$ and $4$. |
| title | Forbidden induced subgraphs in iterative higher order line graphs |
| topic | Combinatorics Discrete Mathematics 05C76, 05C75 |
| url | https://arxiv.org/abs/2410.04607 |