Scattering number and modular decomposition (Q1356754)

The authors present a method for studying Hamiltonicity of (undirected, simple, finite) graphs, by connecting the so-called modular decomposition tree of a graph \(G\) with its scattering number \(s(G):=\max\{s\mid\text{there is } S\subseteq V(G)\) such that \(c(G- S)\neq 1\) and \(c(G- S)-|S|=s\}\), where \(V(G)\) denotes the vertex set of \(G\) and \(c(H)\) the number of (connected) components of a graph \(H\). This method is applied to the class of Jung semi-\(P_4\)-sparse graphs. A graph \(G\) is said to be \(P_4\)-free if it does not contain any \(P_4\) as an induced subgraph, and \(G\) is a \(P_4\)-sparse graph if any set of five vertices induces at most one \(P_4\) in \(G\), where \(P_k\) denotes a chordless path on \(k\) vertices in \(G\). If, more generally, \(G\) does not contain any \(P_5\), any \(\widetilde P_5\), any kite, and any 3-sun as an induced subgraph then \(G\) is called a Jung semi-\(P_4\)-sparse graph. Here, \(\widetilde H\) denotes the complement of \(H\) in the complete graph on the vertex set \(V(H)\), a kite is a graph isomorphic to \((\{x_1,\dots,x_5\},\{x_1x_3, x_1x_4, x_ix_{i+1}\mid i=1,\dots,4\})\), and a \(k\)-sun is a graph obtained from a chordless cycle \((x_1,\dots, x_k,x_1)\) by adding \(k\) new vertices \(y_1,\dots,y_k\) and the edges \(x_1y_1,\dots, x_ky_k\). Let \(\varrho(G)\) denote the minimum number of (elementary) disjoint paths which cover \(V(G)\) (minimum path partition number of \(G\)). A Jung graph is a graph \(G\) satisfying (1) \(\varrho(G)=\max\{1,s(G)\}\), (2) if \(s(G)= 0\) then \(G\) is Hamiltonian, (3) if \(s(G)<0\) then \(G\) is Hamiltonian-connected. The main result of the paper is the theorem that every Jung semi-\(P_4\)-sparse graph is a Jung graph.