This work is licensed under the Creative Commons Attribution License. On P-transitive graphs and applications

We introduce a new class of graphs which we call P-transitive graphs, lying between transitive and 3-transitive graphs. First we show that the analogue of de Jongh-Sambin Theorem is false for well-founded P-transitive graphs; then we show that the µ-calculus fixpoint hierarchy is infinite for P-transitive graphs. Both results contrast with the case of transitive graphs. We give also an undecid-ability result for an enriched µ-calculus on P-transitive graphs. Finally, we consider a polynomial time reduction from the model checking problem on arbitrary graphs to the model checking problem on P-transitive graphs. All these results carry over to 3-transitive graphs.