Extremal Spanning Trees of Random Marked Graphs with Independent Edge Weights
In this paper, we consider a Bernoulli random graph~\(G\) on~\(n\) vertices with non-uniform edge probabilities, where each vertex has an independent mark and each edge is equipped with an independent positive weight. The cost of an edge depends on the weight as well the marks of the endvertices and we estimate the growth of the maximum and minimum cost of a spanning tree containing all the vertices. For edge weights with heavy tails and vertex marks distributed uniformly in the unit square, we obtain a phase transition in terms of the tail decay exponent~\(s:\) If~\(s\) is large, then the…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.26162
curl -X POST /api/v1/records/arxiv/2609.26162/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.26162/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'