Scattering number and modular decomposition Original Research Article

The scattering number of a graph G equals max {c(G⧹S) − |S|S is a cutset of G} where c(G⧹S) denotes the number of connected components in G⧹S. Jung (1978) has given for any graph having no induced path on four vertices (P4-free graph) a correspondence between the value of its scattering number and the existence of Hamiltonian paths or Hamiltonian cycles. Hochstättler and Tinhofer (to appear) studied the Hamiltonicity of P4-sparse graphs introduced by Hoàng (1985). In this paper, using modular decomposition, we show that the results of Jung and Hochsta̋ttler and Tinhofer can be generalized to a subclass of the family of semi-P4-sparse graphs introduced in Fouquet and Giakoumakis (to appear).