Skip to content
DraconiticResearch
Search Sources API
201,683 studies31 sourcesUpdated 38 min ago
PreprintCC BY 4.0arXiv

Extremal Spanning Trees of Random Marked Graphs with Independent Edge Weights

  • Ghurumuruhan Ganesan
Open at sourcePDFDOICite

Abstract

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 maximum cost is essentially determined by the vertex locations and if~s is small, then the edge weights crucially influence the maximum cost. We derive a similar result for minimum cost spanning trees and use martingale difference based methods to establish the~L2−convergence of the extremal cost, appropriately scaled and centred.

Related

  1. An extremal theorem for non-isomorphic spanning trees
    Zhifei Yan, Lu-Ming Zhang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. A Turán-type extremal problem for the number of spanning trees in C4-free graphs
    Shaohan Xu, Fengming Dong, Kexiang Xu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Rooted spanning forests in wheel graphs: Fibonacci-Lucas formulas and extremal root configurations
    Shunya Tamura, Yuuho Tanaka
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Extremal Spanning Trees in Product Grid Graphs
    Jiechen Zhang
    arXivPreprintCC BY 4.0Full textAnalysis & PDEsCombinatorics & discrete mathematicsarXiv
  5. On Hypergraph Colorings and Completely Independent Spanning Trees in Chordal Graphs
    Mohammed Lalou, Nader Mbarek, Abdallah Skender +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{ganesan2026extremal,
  title = {{Extremal Spanning Trees of Random Marked Graphs with Independent Edge Weights}},
  author = {Ghurumuruhan Ganesan},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.26162},
  eprint = {2609.26162},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.26162},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Extremal Spanning Trees of Random Marked Graphs with Independent Edge Weights
AU  - Ghurumuruhan Ganesan
PY  - 2026
DA  - 2026/09/01
PB  - arXiv
DO  - 10.48550/arxiv.2609.26162
UR  - https://arxiv.org/abs/2609.26162
AB  - 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 maximum cost is essentially determined by the vertex locations and if~s is small, then the edge weights crucially influence the maximum cost. We derive a similar result for minimum cost spanning trees and use martingale difference based methods to establish the~L^2−convergence of the extremal cost, appropriately scaled and centred.
ER  -