Loops of any size and Hamilton cycles in random scale-free networks

Details Loops of any size and Hamilton cycles in random scale-free networks Loops of any size and Hamilton cycles in random scale-free networks

2005-02-23

arxiv.org/abs/cond-mat/0502552v2

Physics

Condensed Matter

Disordered Systems and Neural Networks

14 pages, 4 figures, minor changes

Scientific paper

10.1088/1742-5468/2005/06/P06005

Loops are subgraphs responsible for the multiplicity of paths going from one to another generic node in a given network. In this paper we present an analytic approach for the evaluation of the average number of loops in random scale-free networks valid at fixed number of nodes N and for any length L of the loops. We bring evidence that the most frequent loop size in a scale-free network of N nodes is of the order of N like in random regular graphs while small loops are more frequent when the second moment of the degree distribution diverges. In particular, we find that finite loops of sizes larger than a critical one almost surely pass from any node, thus casting some doubts on the validity of the random tree approximation for the solution of lattice models on these graphs. Moreover we show that Hamiltonian cycles are rare in random scale-free networks and may fail to appear if the power-law exponent of the degree distribution is close to 2 even for minimal connectivity grater than 3.

Affiliated with

Also associated with

No associations

Rating

Loops of any size and Hamilton cycles in random scale-free networks 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 Loops of any size and Hamilton cycles in random scale-free networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Loops of any size and Hamilton cycles in random scale-free networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-398820