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
,
(
and
)
denotes the linear compactness (
strict and strict-linear compactness). See Paragraph 2.5.

For convenience, for every class of graphs ,
we denote by
the value defined by:

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

- Extremal Compactness
- Interconnection Networks
- Chordal Rings
- Planar Graphs
- Treewidth Bounded Graphs
- Random Graphs
- Other Classes of Graphs
- Graph Operators
- Summary