Exact enumeration of graphs and bipartite graphs with degree constraints

EUROCOMB’23

Abstract
We provide a new explicit formula enumerating graphs with constraints on their degrees, such as regular graphs, and extend it to bipartite graphs. It relies on generating function manipulations and Hadamard products. Keywords: regular graphs, exact enumeration, D-finite, differentiably finite

Pages:
254–262
References

E. A. Bender and E. R. Canfield. The asymptotic number of labeled graphs with given degree sequences. Journal of Combinatorial Theory, Series A, 24(3):296-307, 1978.
https://doi.org/10.1016/0097-3165(78)90059-6

F. Bergeron, G. Labelle, and P. Leroux. Combinatorial Species and Tree-like Structures. Cambridge University Press, 1997.
https://doi.org/10.1017/CBO9781107325913

B. Bollobás and O. Riordan. An old approach to the giant component problem. Journal of Combinatorial Theory, Series B, 113:236-260, 2015.
https://doi.org/10.1016/j.jctb.2015.03.002

M. Borinsky. Graphs in perturbation theory: Algebraic structure and asymptotics. Springer, 2018.
https://doi.org/10.1007/978-3-030-03541-9

F. Chyzak, M. Mishna, and B. Salvy. Effective scalar products of d-finite symmetric series. Journal of Combinatorial Theory, Series A, 112:1-43, 2005.
https://doi.org/10.1016/j.jcta.2005.01.001

E. de Panafieu. Analytic combinatorics of connected graphs. Random Structures & Algorithms, 2018.
https://doi.org/10.1002/rsa.20836

E. de Panafieu and L. Ramos. Graphs with degree constraints. Proceedings of the Meeting on Analytic Algorithmics and Combinatorics (Analco16), 2016.

S. Dovgal and V. Ravelomanana. Shifting the phase transition threshold for random graphs using degree set constraints. Proceedings of the American Theoretical Informatics Symposium (LATIN18), pages 399-412, 2018.
https://doi.org/10.1007/978-3-319-77404-6_29

M. M. Elin. Multidimensional Hadamard composition. Sibirskii Matematicheskii

Zhurnal, 35(5):1052-1057, 1994.

P. L. Erdős, I. Miklós, and L. Soukup. Towards random uniform sampling of bipartite graphs with given degree sequence. arXiv preprint arXiv:1004.2612, 2010.

P. Flajolet and R. Sedgewick. Analytic Combinatorics. Cambridge University Press, 2009.
https://doi.org/10.1017/CBO9780511801655

I. M. Gessel. Symmetric functions and p-recursiveness. Journal of Combinatorial Theory, Series A, 53:257-285, 1990.
https://doi.org/10.1016/0097-3165(90)90060-A

I. P. Goulden, D. M. Jackson, and J. W. Reilly. The Hammond series of a symmetric function and its application to P-recursiveness. SIAM Journal on Algebraic Discrete Methods, 4(2):179-193, 1983.
https://doi.org/10.1137/0604019

H. Hatami and M. Molloy. The scaling window for a random graph with a given degree sequence. Random Structures & Algorithms, 41(1):99-123, 2012.
https://doi.org/10.1002/rsa.20394

S. Janson and M. J. Luczak. A new approach to the giant component problem. Random Structures & Algorithms, 34(2):197-216, 2009.
https://doi.org/10.1002/rsa.20231

F. Joos, G. Perarnau, D. Rautenbach, and B. Reed. How to determine if a random graph with a fixed degree sequence has a giant component. Probability Theory and Related Fields, 170(1-2):263-310, 2018.
https://doi.org/10.1007/s00440-017-0757-1

A. Joyal. Une théorie combinatoire des séries formelles. Advances in mathematics, 42(1):1-82, 1981.
https://doi.org/10.1016/0001-8708(81)90052-9

M. Kang and T. G. Seierstad. The critical phase for random graphs with a given degree sequence. Combinatorics, Probability and Computing, 17(1):67-86, 2008.
https://doi.org/10.1017/S096354830700867X

A. Kaygun. Enumerating labeled graphs that realize a fixed degree sequence. arXiv preprint arXiv:2101.02299, 2021.

E. Leinartas. Multidimensional Hadamard composition and sums with linear constraints on the summation indices. Siberian Mathematical Journal, 30(2):250-255, 1989.
https://doi.org/10.1007/BF00971380

L. Lipshitz. The diagonal of a d-finite power series is d-finite. Journal of algebra, 113(2):373-378, 1988.
https://doi.org/10.1016/0021-8693(88)90166-4

B. D. McKay and N. C. Wormald. Asymptotic enumeration by degree sequence of graphs of high degree. European Journal of Combinatorics, 11(6):565-580, 1990.
https://doi.org/10.1016/S0195-6698(13)80042-X

M. Mishna. Automatic enumeration of regular objects. arXiv preprint math/0507249, 2005.

M. Mishna. Regularity in weighted graphs: a symmetric function approach. arXiv preprint arXiv:1507.05121, 2015.

M. Molloy and B. Reed. A critical point for random graphs with a given degree sequence. Random Structures & Algorithms, 6(2-3):161-180, 1995.
https://doi.org/10.1002/rsa.3240060204

T. Sadykov. The Hadamard product of hypergeometric series. Bulletin des Sciences Mathématiques, 126(1):31-43, 2002.
https://doi.org/10.1016/S0007-4497(01)01104-6

R. P. Stanley. Differentiably finite power series. European journal of combinatorics, 1(2):175-188, 1980.
https://doi.org/10.1016/S0195-6698(80)80051-5

D. Zeilberger. Sister Celine's technique and its generalizations. Journal of Mathematical Analysis and Applications, 85(1):114-145, 1982.
https://doi.org/10.1016/0022-247X(82)90029-4

Metrics

0

Views

0

PDF views