Scattering number and extremal non-Hamiltonian graphs (Q1109047): Difference between revisions

The scattering number, s(G), of a graph G is defined by \(s(G)=\max \{k(G- X)-| X|;\quad X\subseteq V(G),\quad k(G-X)\neq 1\},\) where k(H) denotes the number of components of the graph H. Let \(Q_ 0\), \(Q_ 1\) and \(Q_ 2\) stand for the words traceable, Hamiltonian and Hamiltonian- connected (every pair of vertices is connected by a Hamiltonian path), respectively. In the paper the following conjecture is stated: Let h and i be integers with \(h\geq 0\) and \(0\leq i\leq 2\). There exists an integer N(h,i) such that if G is a graph with order \(n\geq N(h,i)\), size \(q\geq \left( \begin{matrix} n-2h- 3\\ 2\end{matrix} \right)+(2h+3)(h+i+1)\) and scattering number s(G)\(\leq 1- h-i\) then either G is in \(Q_ i\) or \(G\simeq K_{h+i}+A_{n-3h-i- 3,2h+3}\) where, for \(p\geq r\), \(A_{p,r}\) denotes the graph of order \(p+r\) obtained by identifying an end vertex of each edge of \(rK_ 2\) with a distinct vertex of \(K_ p.\) The author proves the conjecture for \(h=0\) and \(i=0,1,2\) \((N(0,i)=19+i)\) and \(h=1\) and \(i=0\) \((N(1,0)=31)\).