Paper Info
Title
Degree switching and partitioning for enumerating graphs to arbitrary orders of accuracy
Abstract
We provide a novel method for constructing asymptotics (to arbitrary accuracy) for the number of directed graphs that realize a fixed bidegree sequence $d = a \times b$ with maximum degree $d_{max}=O(S^{\frac{1}{2}-\tau})$ for an arbitrarily small positive number $\tau$, where $S$ is the number edges specified by $d$. Our approach is based on two key steps, graph partitioning and degree preserving switches. The former idea allows us to relate enumeration results for given sequences to those for sequences that are especially easy to handle, while the latter facilitates expansions based on numbers of shared neighbors of pairs of nodes. While we focus primarily on directed graphs allowing loops, our results can be extended to other cases, including bipartite graphs, as well as directed and undirected graphs without loops. In addition, we can relax the constraint that $d_{max} = O(S^{\frac{1}{2}-\tau})$ and replace it with $a_{max} b_{max} = O(S^{1-\tau})$. where $a_{max}$ and $b_{max}$ are the maximum values for $a$ and $b$ respectively. The previous best results, from Greenhill et al., only allow for $d_{max} = o(S^{\frac{1}{3}})$ or alternatively $a_{max} b_{max} = o(S^{\frac{2}{3}})$. Since in many real world networks, $d_{max}$ scales larger than $o(S^{\frac{1}{3}})$, we expect that this work will be helpful for various applications.
Year
Venue
Field
2015
CoRR
Discrete mathematics,Graph,Combinatorics,Enumeration,Bipartite graph,Directed graph,Degree (graph theory),Graph partition,Asymptotic analysis,Mathematics
DocType
Volume
Citations 
Journal
abs/1511.03738
0
PageRank 
References 
Authors
0.34
9
2
Name
Order
Citations
PageRank
david burstein100.68
Jonathan E. Rubin223531.34