Please use this identifier to cite or link to this item:
Title: Necessary and sufficient conditions for a Hamiltonian graph
Author: Sciriha, I
Cardoso, Domingos M.
Keywords: Hamiltonian graphs
Singular graphs
Graph eigenvalues
Issue Date: Feb-2012
Publisher: Charles Babbage Research Centre
Abstract: A graph is singular if the zero eigenvalue is in the spectrum of its 0-1 adjacency matrix A. If an eigenvector belonging to the zero eigenspace of A has no zero entries, then the singular graph is said to be a core graph. A ( k,t)-regular set is a subset of the vertices inducing a k -regular subgraph such that every vertex not in the subset has t neighbours in it. We consider the case when k=t which relates to the eigenvalue zero under certain conditions. We show that if a regular graph has a ( k,k )-regular set, then it is a core graph. By considering the walk matrix we develop an algorithm to extract ( k,k )-regular sets and formulate a necessary and sufficient condition for a graph to be Hamiltonian.
Peer review: yes
ISSN: 0835-3026
Publisher Version:
Appears in Collections:CIDMA - Artigos

Files in This Item:
File Description SizeFormat 
mainZham9.pdfResearch article397.91 kBAdobe PDFView/Open

Formato BibTex MendeleyEndnote Degois 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.