Please use this identifier to cite or link to this item:
http://hdl.handle.net/10773/13474
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 |
URI: | http://hdl.handle.net/10773/13474 |
ISSN: | 0835-3026 |
Publisher Version: | http://www.combinatorialmath.ca/jcmcc/ |
Appears in Collections: | CIDMA - Artigos |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
mainZham9.pdf | Research article | 397.91 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.