Utilize este identificador para referenciar este registo:
http://hdl.handle.net/10773/13474
Título: | Necessary and sufficient conditions for a Hamiltonian graph |
Autor: | Sciriha, I Cardoso, Domingos M. |
Palavras-chave: | Hamiltonian graphs Singular graphs Graph eigenvalues |
Data: | Fev-2012 |
Editora: | Charles Babbage Research Centre |
Resumo: | 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 |
Versão do Editor: | http://www.combinatorialmath.ca/jcmcc/ |
Aparece nas coleções: | CIDMA - Artigos |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
mainZham9.pdf | Research article | 397.91 kB | Adobe PDF | Ver/Abrir |
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.