Geodesic
On the number of perfect matchings and Hamilton cycles in \(\varepsilon\)-regular non-bipartite graphs
The electronic journal of combinatorics, Tome 7 (2000)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A graph $G=(V,E)$ on $n$ vertices is super $\epsilon$-regular if (i) all vertices have degree in the range $[(d-\epsilon)n,(d+\epsilon)n]$, $dn$ being the average degree, and (ii) for every pair of disjoint sets $S,T\subseteq V,\,|S|,|T|\geq \epsilon n$, $e(S,T)$ is in the range $[(d-\epsilon)|S||T|,(d+\epsilon)|S||T|]$. We show that the number of perfect matchings lies in the range $$[((d-2\epsilon)^\nu {{n!}\over {\nu !2^\nu}},(d+2\epsilon)^\nu {{n!}\over {\nu !2^\nu}}],$$ where $\nu ={{n}\over {2}}$, and the number of Hamilton cycles lies in the range $[(d-2\epsilon)^nn!,(d+2\epsilon)^nn!]$.
DOI : 10.37236/1535
Classification : 05C70, 05C45, 05C50, 05C80
Mots-clés : perfect matchings, Hamilton cycles 
@article{10_37236_1535,
     author = {Alan Frieze},
     title = {On the number of perfect matchings and {Hamilton} cycles in \(\varepsilon\)-regular non-bipartite graphs},
     journal = {The electronic journal of combinatorics},
     year = {2000},
     volume = {7},
     doi = {10.37236/1535},
     zbl = {0964.05053},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1535/}
}
TY  - JOUR
AU  - Alan Frieze
TI  - On the number of perfect matchings and Hamilton cycles in \(\varepsilon\)-regular non-bipartite graphs
JO  - The electronic journal of combinatorics
PY  - 2000
VL  - 7
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1535/
DO  - 10.37236/1535
ID  - 10_37236_1535
ER  - 
%0 Journal Article
%A Alan Frieze
%T On the number of perfect matchings and Hamilton cycles in \(\varepsilon\)-regular non-bipartite graphs
%J The electronic journal of combinatorics
%D 2000
%V 7
%U http://geodesic.mathdoc.fr/articles/10.37236/1535/
%R 10.37236/1535
%F 10_37236_1535
Alan Frieze. On the number of perfect matchings and Hamilton cycles in \(\varepsilon\)-regular non-bipartite graphs. The electronic journal of combinatorics, Tome 7 (2000). doi: 10.37236/1535

Cité par Sources :