Back to Search
Start Over
Counting Hamiltonian cycles in the matroid basis graph
- Source :
- Repositório Institucional da USP (Biblioteca Digital da Produção Intelectual), Universidade de São Paulo (USP), instacron:USP, Graphs and Combinatorics, Graphs and Combinatorics, Springer Verlag, 2019, 35 (2), pp.539-550. ⟨10.1007/s00373-019-02011-8⟩
- Publication Year :
- 2019
-
Abstract
- International audience; We present superfactorial and exponential lower bounds on the number of Hamiltonian cycles passing through any edge of the basis graph of generalized Catalan, uniform, and graphic matroids. All lower bounds were obtained by a common general strategy based on counting appropriated cycles of length four in the corresponding matroid basis graph.
- Subjects :
- Mathematics::Combinatorics
Hamiltonian cycle
matroid basis graph
010102 general mathematics
TEORIA DOS GRAFOS
0102 computer and information sciences
01 natural sciences
Hamiltonian path
Matroid
Graph
Theoretical Computer Science
Exponential function
Combinatorics
symbols.namesake
010201 computation theory & mathematics
generalized Catalan matroid
[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
symbols
Discrete Mathematics and Combinatorics
[MATH]Mathematics [math]
0101 mathematics
Hamiltonian (quantum mechanics)
Mathematics
Subjects
Details
- ISSN :
- 09110119 and 14355914
- Database :
- OpenAIRE
- Journal :
- Repositório Institucional da USP (Biblioteca Digital da Produção Intelectual), Universidade de São Paulo (USP), instacron:USP, Graphs and Combinatorics, Graphs and Combinatorics, Springer Verlag, 2019, 35 (2), pp.539-550. ⟨10.1007/s00373-019-02011-8⟩
- Accession number :
- edsair.doi.dedup.....426872cadb88a3c888cba02a9efa435e