EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-ND 4.0

Asymptotic enumeration of constrained bipartite, directed and oriented graphs by degree sequence

Catherine Greenhill, Mahdieh Hasheminezhad, Isaiah Iliffe, Brendan D. McKay

Discrete Applied Mathematics · 2027-01 · 396 · 328-341

DOI: 10.1016/j.dam.2026.10.003 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Discrete Applied Mathematics, 2027-01. Verfasst von Catherine Greenhill und 3 weiteren Autor:innen. Die Arbeit nennt 15 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0). Gefördert von: Australian Research Council.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In the sufficiently sparse case, we find the probability that a uniformly random bipartite graph with given degree sequence contains no edge from a specified set of edges. This enables us to enumerate loop-free digraphs and oriented graphs with given in-degree and out-degree sequences, and obtain subgraph probabilities. Our theorems are not restricted to the near-regular case. As an application, we determine the expected permanent of sparse or very dense random matrices with given row and column sums; in the regular case, our formula holds over all densities. We also draw conclusions about the degrees of a random orientation of a random undirected graph with given degrees, including its number of Eulerian orientations.

Förderung

  • Australian Research Council

Zitieren

APA

Greenhill, C., Hasheminezhad, M., Iliffe, I., & McKay, B. D. (2027). Asymptotic enumeration of constrained bipartite, directed and oriented graphs by degree sequence. Discrete Applied Mathematics, 396, 328-341. https://doi.org/10.1016/j.dam.2026.10.003

Vancouver

Greenhill C, Hasheminezhad M, Iliffe I, McKay BD. Asymptotic enumeration of constrained bipartite, directed and oriented graphs by degree sequence. Discrete Applied Mathematics. 2027;396:328-341. doi:10.1016/j.dam.2026.10.003

BibTeX
@article{Greenhill2027,
  author = {Greenhill, Catherine and Hasheminezhad, Mahdieh and Iliffe, Isaiah and McKay, Brendan D.},
  title = {Asymptotic enumeration of constrained bipartite, directed and oriented graphs by degree sequence},
  journal = {Discrete Applied Mathematics},
  year = {2027},
  volume = {396},
  pages = {328--341},
  doi = {10.1016/j.dam.2026.10.003}
}
Kostenlos starten →