• DocumentCode
    1888809
  • Title

    A novel condition for Hamiltonicity; constructing Hamiltonian circuits

  • Author

    Onete, Maria Cristina C ; Onete, Cristian E.

  • Author_Institution
    CASED, Tech. Univ. Darmstadt, Darmstadt, Germany
  • fYear
    2011
  • fDate
    27-29 April 2011
  • Firstpage
    1
  • Lastpage
    4
  • Abstract
    In this paper, we derive a new necessary and sufficient condition for a simple, undirected graph to have a Hamiltonian circuit. Our novel approach uses a modified incidence matrix and constructs Hamiltonian circuits from the graph´s spanning trees. We furthermore optimise the underlying spanning-tree algorithm, and give an example of our results.
  • Keywords
    integrated circuit design; trees (mathematics); Hamiltonian circuit construction; Hamiltonicity; graph spanning trees; incidence matrix; undirected graph; Complexity theory; Equations; Genetics; Graph theory; Labeling; Strontium; Sufficient conditions; Hamiltonian circuit; Hamiltonicity; Wang Algebra;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    EUROCON - International Conference on Computer as a Tool (EUROCON), 2011 IEEE
  • Conference_Location
    Lisbon
  • Print_ISBN
    978-1-4244-7486-8
  • Type

    conf

  • DOI
    10.1109/EUROCON.2011.5929160
  • Filename
    5929160
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1888809