A Note on Induced Path Decomposition of Graphs

MaRDI QIDQ6330182zbMATH OpenFDO

Authors S. Akbari, H. R. Maimani, Abbas Seify

Publication date 1 December 2019

Abstract: Let $G$ be a graph of order $n$. The path decomposition of $G$ is a set of disjoint paths, say $mathcalP$, which cover all vertices of $G$. If all paths are induced paths in $G$, then we say $mathcalP$ 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 $fracn3$. We classify all connected claw-free graphs which admit an IPD.

This page was built for publication: A Note on Induced Path Decomposition of Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6330182)