Scattering number and extremal non-Hamiltonian graphs
type: Item
instance of: scholarly article
title: Scattering number and extremal non-Hamiltonian graphs
zbMATH Open document ID: 0655.05044
DOI: 10.1016/0012-365X(88)90069-6
author: George R. T. Hendry
published in: Discrete Mathematics
publication date: 1988-01-01T00:00:00Z
review text: 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)\).
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 4068917
zbMATH Keywords: scattering number
zbMATH Keywords: traceable
zbMATH Keywords: Hamiltonian
zbMATH Keywords: Hamiltonian-connected
reviewed by: Peter Horák
MaRDI profile type: Publication
cites work: Q4187840
cites work: Variations on the Hamiltonian Theme
cites work: A method in graph theory
cites work: On Hamilton's ideals
cites work: Tough graphs and Hamiltonian circuits.
cites work: A catalogue of small maximal nonhamiltonian graphs
cites work: On a class of posets and the corresponding comparability graphs
cites work: Q5578810
cites work: Nonhamiltonian connected graphs
cites work: Arc coverings of graphs
cites work: Hamilton connected graphs
cites work: Q5722819
Wikidata QID: Q126819334
full work available at URL: 0012-365x(88)90069-6
OpenAlex ID: W2038465558
description: scientific article; zbMATH DE number 4068917