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

An $\mathit{\text{isometric}}\mathit{\text{path}}$ is a shortest path between two vertices. An $\mathit{\text{isometric}}\mathit{\text{path}}\mathit{\text{partition}}$ (IPP) of a graph $G$ is a set $I$ of vertex-disjoint isometric paths in $G$ that partition the vertices of $G$. The $\mathit{\text{isometric}}\mathit{\text{path}}\mathit{\text{partition}}\mathit{\text{number}}$ of $G$, denoted by $\text{ipp}(G)$, is the minimum cardinality of an IPP of $G$. In this article, we prove that every graph $G$ satisfies $\text{ipp}(G)\le \mathrm{\mid }V(G)\mathrm{\mid }-\nu (G)$, where $\nu (G)$ is 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)=\mathrm{\mid }V(G)\mathrm{\mid }-\nu (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 satisfy $\text{ipp}(B)=\mathrm{\mid }V(B)\mathrm{\mid }-\nu (B)$. As corollaries of this result, 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.