Counting loopy graphs with given degrees

DOI10.1016/J.LAA.2011.03.052zbMATH Open1236.05108arXiv1103.0080OpenAlexW2962853152MaRDI QIDQ763074FDOQ763074

Authors: Catherine Greenhill, Brendan D. McKay 

Publication date: 8 March 2012

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

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).

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

Recommendations

• scientific article; zbMATH DE number 2053249
• scientific article; zbMATH DE number 1507223
• scientific article
• 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

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)

Cites Work

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

Cited In (1)

• Title not available (Why is that?)

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)