Non-isomorphic smallest maximally non-Hamiltonian graphs
type: Item
instance of: scholarly article
zbMATH Open document ID: 0962.05034
author: Ladislav Stacho
publication date: 2001-05-30T00:00:00Z
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 1600936
zbMATH Keywords: maximally non-Hamiltonian graph
zbMATH Keywords: Isaacs' snark
MaRDI profile type: Publication
title: Non-isomorphic smallest maximally non-Hamiltonian graphs
published in: Ars Combinatoria
review text: A graph \(G\) is maximally non-Hamiltonian (MNH) if \(G\) is not Hamiltonian but adding to \(G\) any edge results in a Hamiltonian graph. The main result presents a construction based on a modification of Isaacs' snarks, showing that, for any \(n\geq 88\), there are at least \(\tau (n)\) smallest (i.e. with minimum number of edges) MNH graphs of order \(n\), where \(\tau (n)\geq 3\) and \(\lim _{n\to \infty} \tau (n)=\infty \). Thus, only a finite number of orders \(n\) remain for which only a unique smallest MNH graph is known.
reviewed by: Zdeněk Ryjáček
description: scientific article; zbMATH DE number 1600936