A Note on Induced Path Decomposition of Graphs
| Autor: | Akbari, S., Maimani, H. R., Seify, A. |
|---|---|
| Rok vydání: | 2019 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | Let $G$ be a graph of order $n$. The path decomposition of $G$ is a set of disjoint paths, say $\mathcal{P}$, which cover all vertices of $G$. If all paths are induced paths in $G$, then we say $\mathcal{P}$ is an induced path decomposition of $G$. Moreover, if every path is of order at least 2, then we say $G$ has an IPD. In this paper, we prove that every connected $r$-regular graph which is not complete graph of odd order admits an IPD. Also we show that every connected bipartite cubic graph of order $n$ admits an IPD of size at most $\frac{n}{3}$. We classify all connected claw-free graphs which admit an IPD. Comment: 5 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|