New necessary and sufficient condition and algorithm for directed hamiltonian graph based on boolean determinant theory
| Autor: | Mao-Ming Jin, Qinghua Zhang, Hong-Gang Li, Qing-Bi He, Huiming Duan |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
Algebra and Number Theory 010308 nuclear & particles physics Applied Mathematics Two-element Boolean algebra And-inverter graph 010102 general mathematics Implication graph Graph algebra Directed graph Complete Boolean algebra 01 natural sciences 0103 physical sciences 0101 mathematics Stone's representation theorem for Boolean algebras Null graph Algorithm Analysis MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Journal of Discrete Mathematical Sciences and Cryptography. 20:725-745 |
| ISSN: | 2169-0065 0972-0529 |
| DOI: | 10.1080/09720529.2016.1226618 |
| Popis: | In this paper, a Boolean determinant is introduced, and some properties of the determinants are discussed in Boolean algebra. Next, applying with the properties of characteristic determinant of directed graph, a new Hamiltonian-cycles decision theorem and a new necessary and sufficient conditions for a Hamiltonian directed graph are studied, and a new Hamiltonian-cycles decision algorithm is established. Finally, an example is provided. The obtained results seem to be general in nature. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|