History


Please fill in your query. A complete syntax description you will find on the General Help page.
Entropy bounds for perfect matchings and Hamiltonian cycles. (English)
Combinatorica 29, No. 3, 327-335 (2009).
For a graph $G = (V,E)$ and $ \boldsymbol{x}: E \to {\Bbb R}^+$ satisfying $\sum_{e\ni v}x_e = 1$ for each $v\in V,$ set $h(x)= \sum_e x_e \log(1/x_e)$ (with $\log = \log_2$). We show that, for any $n$-vertex $G$, a random (not necessarily uniform) perfect matching $\boldsymbol{f}$ satisfying a mild technical condition, and $x_e =Pr(e\in\boldsymbol{f}),$ $$H(\boldsymbol{f}) Reviewer: Nikolai L. Manev (Sofia)
WorldCat.org
Valid XHTML 1.0 Transitional Valid CSS!