Minimal vertex covers of random trees

DOI10.1088/1742-5468/2005/06/P06007zbMATH Open1456.82434arXivcond-mat/0411382MaRDI QIDQ4968859FDOQ4968859

Authors: Stéphane Coulomb 

Publication date: 9 July 2019

Published in: Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Abstract: We study minimal vertex covers of trees. Contrarily to the number $N_{vc}(A)$ of minimal vertex covers of the tree $A$, $log{N}_{vc}(A)$ is a self-averaging quantity. We show that, for large sizes $n$, $li{m}_{no+infty}<log{N}_{vc}(A){>}_n/n=0.1033252pm10^{-7}$. The basic idea is, given a tree, to concentrate on its degenerate vertices, that is those vertices which belong to some minimal vertex cover but not to all of them. Deletion of the other vertices induces a forest of totally degenerate trees. We show that the problem reduces to the computation of the size distribution of this forest, which we perform analytically, and of the average $<log{N}_{vc}>$ over totally degenerate trees of given size, which we perform numerically.

Full work available at URL: https://arxiv.org/abs/cond-mat/0411382

Recommendations

• Covering minimum spanning trees of random subgraphs
• Covering minimum spanning trees of random subgraphs
• On the minimum vertex \(k\)-path cover of trees
• Minimum vertex covers and the spectrum of the normalized Laplacian on trees
• On random minimum length spanning trees
• scientific article; zbMATH DE number 1984546
• The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph
• Min-max tree covers of graphs.
• Minimum vertex cover in generalized random graphs with power law degree distribution

zbMATH Keywords

networksrandom graphsspin glasses (theory)

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30)

Cites Work

• Title not available (Why is that?)
• Statistical mechanics of the vertex-cover problem

Cited In (2)

• Min-max tree covers of graphs.
• Minimum vertex cover in generalized random graphs with power law degree distribution

This page was built for publication: Minimal vertex covers of random trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4968859)