Minimal vertex covers of random trees

Details Minimal vertex covers of random trees Minimal vertex covers of random trees

2004-11-15

arxiv.org/abs/cond-mat/0411382v1

Physics

Condensed Matter

Statistical Mechanics

Scientific paper

10.1088/1742-5468/2005/06/P06007

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$, $\lim_{n\to +\infty} <\log N_{vc}(A)>_n/n= 0.1033252\pm 10^{-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.

Affiliated with

Also associated with

No associations

Rating

Minimal vertex covers of random trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Minimal vertex covers of random trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimal vertex covers of random trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-39391