Isometric and induced path partitions: a new upper bound and a characterization of some extremal graphs

Abstract

An \textit{isometric path} is a shortest path between two vertices. An \textit{isometric path partition} (IPP) of a graph $G$ is a set $\mathcal{I}$ of vertex-disjoint isometric paths in $G$ that partition the vertices of $G$. The \textit{isometric path partition number} of $G$, denoted by $\text{ipp}(G)$, is the minimum cardinality of an IPP of~$G$. An \textit{induced path partition} (IndPP) of a graph $G$ is a set $\mathcal{I}$ of vertex-disjoint induced paths in~$G$ that partition the vertices of $G$. The \textit{induced path partition number} of $G$, denoted by $\text{indpp}(G)$, is the minimum cardinality of an IndPP of $G$. In this article, we study both these parameters and observe that every graph $G$ satisfies $\text{indpp}(G)\le \text{ipp}(G)\le |V(G)|-\hat{I}½(G)$, where $\hat{I}½(G)$ is the matching number of $G$. We further prove that a connected graph $G$ is extremal with respect to this upper bound, i.e.\ satisfies $\text{ipp}(G)=|V(G)|-\hat{I}½(G)$, (resp.\ $\text{indpp}(G)=|V(G)|-\hat{I}½(G)$), if and only if either (i) all blocks of $G$ are odd complete graphs, or (ii) all blocks of $G$ except one are odd complete graphs, and the unique block $B$ of $G$ that is not an odd complete graph is even and satisfies $\text{ipp}(B)=|V(B)|-\hat{I}½(B)$ (resp.\ $\text{indpp}(B)=|V(B)|-\hat{I}½(B)$). As corollaries of these results, we obtain a full structural characterization of all connected odd graphs that are extremal with respect to our upper bound, as well as of all extremal block graphs.

This is a slightly improved version of the following paper: Irena Penev, R.B.~Sandeep, D.K.~Supraja, S~Taruni, "Isometric and induced path partitions: a new upper bound and a characterization of some extremal graphs''. Discrete Applied Mathematics}, 392 (2026), 260--273