Alrik Sandberg: P_3-Hull Numbers and Infection Times of Unit Interval Graphs

Abstract.

It is well known that the \(P_3\)-hull number and the infection time are difficult to calculate for large graphs. We find that it is possible to calculate the \(P_3\)-hull number, and find at least one contagious set for certain, specific, types of unit interval graphs. Furthermore we show that the number of unit interval graphs with a possible maximal infection time of \(n-2\) is constant for \(n \ge 4\) vertices. These graphs with a maximal possible infection time also share a specific structure. This means that it is possible to easily find all unit interval graphs of this type for a given number of vertices. We also show that the number of unit interval graphs of size \(n\) with a \(P_3\)-hull number of \(n\) is given by the \((n+1)\)th Fibonacci number. Lastly, we show how the number of unit interval graphs consisting of n vertices that has \(P_3\)-hull number equal to \(2\) is equal to \(2\) times the \((n-2)\)th Catalan number.