Connected cubic graphs with the maximum number of perfect matchings
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2020
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909154427273216 |
|---|---|
| author | Horak, Peter Kim, Dongryul |
| author_facet | Horak, Peter Kim, Dongryul |
| contents | It is proved that for $n \geq 6$, the number of perfect matchings in a simple connected cubic graph on $2n$ vertices is at most $4 f_{n-1}$, with $f_n$ being the $n$-th Fibonacci number. The unique extremal graph is characterized as well. In addition, it is shown that the number of perfect matchings in any cubic graph $G$ equals the expected value of a random variable defined on all $2$-colorings of edges of $G$. Finally, an improved lower bound on the maximum number of cycles in a cubic graph is provided. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2006_13459 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Connected cubic graphs with the maximum number of perfect matchings Horak, Peter Kim, Dongryul Combinatorics 05C35 It is proved that for $n \geq 6$, the number of perfect matchings in a simple connected cubic graph on $2n$ vertices is at most $4 f_{n-1}$, with $f_n$ being the $n$-th Fibonacci number. The unique extremal graph is characterized as well. In addition, it is shown that the number of perfect matchings in any cubic graph $G$ equals the expected value of a random variable defined on all $2$-colorings of edges of $G$. Finally, an improved lower bound on the maximum number of cycles in a cubic graph is provided. |
| title | Connected cubic graphs with the maximum number of perfect matchings |
| topic | Combinatorics 05C35 |
| url | https://arxiv.org/abs/2006.13459 |