## Abstract

We present formulas to count the set D_{0}(n) of degree sequences of simple graphs of order n, the set D(n) of degree sequences of those graphs with no isolated vertices, and the set D_{k_con}(n) of degree sequences of those graphs that are k-connected for fixed k. The formulas all use a function of Barnes and Savage and the associated dynamic programming algorithms all run in time polynomial in n and are asymptotically faster than previous known algorithms for these problems. We also show that |D(n)| and |D_{1_con}(n)| are asymptotically equivalent but |D(n)| and |D_{0}(n)| as well as |D(n)| and |D_{k_con}(n)| with fixed k≥2 are asymptotically inequivalent. Finally, we explain why we are unable to obtain the absolute asymptotic orders of these functions from their formulas.

Original language | English |
---|---|

Pages (from-to) | 888-897 |

Number of pages | 10 |

Journal | Discrete Mathematics |

Volume | 342 |

Issue number | 3 |

DOIs | |

State | Published - Mar 2019 |

## Keywords

- Degree sequence
- Enumeration
- Graphical partition
- k-connected