2025/05/26 by Irena Penev, Penev, Irena, R. B. Sandeep +5 · 1 citation
#math.CO
paper · pdf · doi:10.48550/arxiv.2505.19913
An isometric path is a shortest path between two vertices. An isometric path partition (IPP) of a graph G is a set I of vertex-disjoint isometric paths in G that partition the vertices of G. The isometric path partition number of G, denoted by ipp(G), is the minimum cardinality of an IPP of~G. An induced path partition (IndPP) of a graph G is a set I of vertex-disjoint induced paths in~G that partition the vertices of G. The induced path partition number of G, denoted by 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 indpp(G) ≤ ipp(G) ≤ |V(G)| - ν(G), where ν(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 ipp(G) = |V(G)| - ν(G), (resp. indpp(G) = |V(G)| - ν(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 ipp(B) = |V(B)| - ν(B) (resp. indpp(B) = |V(B)| - ν(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.