Specific Class of Graphs

In this section we survey the results known about the compactness of graphs, that is the smallest integer k that provides a shortest path k-IRS. We start with some general results. Recall that the compactness of G is denoted by $\mbox{\rm IRS}(G)$, $\mbox{\rm LIRS}(G)$ ( $\mbox{\rm SIRS}(G)$ and $\mbox{\rm SLIRS}(G)$) denotes the linear compactness ( strict and strict-linear compactness). See Paragraph 2.5.

For convenience, for every class of graphs $\cG$, we denote by $\mbox{\rm IRS}(\cG)$ the value defined by:

$$\mbox{\rm IRS}(\cG) ~=~ \max_{G\in \cG}{\mbox{\rm IRS}(G)}$$

that is a worst-case complexity of the compactness. A summary of the compactness of several classes of graphs is presented in Paragraph 3.9. In the following n always denotes the number of nodes.