Counting loopy graphs with given degrees

DOI10.1016/J.LAA.2011.03.052MaRDI QIDQ763074zbMATHOpenAlexFDO

Authors Catherine Greenhill, Brendan D. McKay

Publication date 8 March 2012

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1103.0080

zbMATH Keywords

graphrandom matrixrandom graphPoisson binomial distributionasymptotic enumerationloop1 matrixsymmetric 0

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Vertex degrees (05C07) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Enumeration in graph theory (05C30)

Abstract: Let d=(d_1,d_2,..., d_n) be a vector of non-negative integers. We study the number of symmetric 0-1 matrices whose row sum vector equals d. While previous work has focussed on the case of zero diagonal, we allow diagonal entries to equal 1. When forming the row sum, each diagonal entry is multiplied by a factor of D, where D is 1 or 2. The case D=1 corresponds to enumeration by the usual row sum of matrices. The case D=2 corresponds to enumeration by degree sequence of undirected graphs with loops but no repeated edges, due to the convention that a loop contributes 2 to the degree of its incident vertex. We obtain asymptotically precise formulae for the number of matrices in the sparse range (where, roughly, the maximum row sum is o(n^{1/2})), and in the dense range (where, roughly, the average row sum is proportional to n and the row sums do not vary greatly).

Recommendations

• scientific article; zbMATH DE number 2053249
• scientific article; zbMATH DE number 1507223
• scientific article; zbMATH DE number 4148119
• scientific article; zbMATH DE number 1744105
• scientific article; zbMATH DE number 6700490
• Degree sums for edges and cycle lengths in graphs
• Counting links in complete graphs
• scientific article; zbMATH DE number 3933107
• On the locatic number of graphs
• Degree sums and proper connection number of graphs

Cites work

• scientific article; zbMATH DE number 3877221 (Why is no real title available?)
• scientific article; zbMATH DE number 3906527 (Why is no real title available?)
• scientific article; zbMATH DE number 47948 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• A dichotomy for minimum cost graph homomorphisms
• An approximation theorem for the Poisson binomial distribution
• Asymptotic enumeration by degree sequence of graphs of high degree
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• Asymptotic enumeration of dense 0-1 matrices with equal row sums and equal column sums
• Asymptotic expansions for sums of nonidentically distributed Bernoulli random variables
• Concentration Inequalities and Martingale Inequalities: A Survey
• On Recursions Connected With Symmetric Groups I
• On Solutions of x^d = 1 In Symmetric Groups
• On the rate of Poisson convergence
• Rational realization of maximum eigenvalue multiplicity of symmetric tree sign patterns
• Subgraphs of dense random graphs with specified degrees
• The On-Line Encyclopedia of Integer Sequences
• The asymptotic number of labeled graphs with given degree sequences
• The degree sequence of a random graph. I. The models
• The number of graphs and a random graph with a given degree sequence

Cited in

(2)

• Asymptotic enumeration of sparse multigraphs with given degrees
• scientific article; zbMATH DE number 5239164 (Why is no real title available?)

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Counting loopy graphs with given degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q763074)