Formulas in connection with parameters related to convexity of paths on three vertices: caterpillars and unit interval graphs

Resumen

We present formulas to compute the $P_3$-interval number, the $P_3$-hull number and the percolation time for a caterpillar, in terms of certain sequences associated with it. In addition, we find a connection between the percolation time of a unit interval graph and a parameter involving the diameter of a unit interval graph related to it. Finally, we present a hereditary graph class, defined by forbidden induced subgraphs, such that its percolation time is equal to one.

Publicación
Australasian Journal of Combinatorics 79(3) (2021), 401–423