DocServer

Graphs with a Given Degree Sequence

MacDougall, James A. and Eggleton, Roger B. and Adams, P. D. (2006) Graphs with a Given Degree Sequence. Congressus Numerantium, 179 . pp. 15-31.

[img]
Preview
PDF - Accepted Version
Download (207Kb) | Preview

    Abstract

    The level set $G(n,m)$ comprises all unlabelled simple graphs of order $n$ and size $m$, and is partitioned into similarity classes, comprising all graphs with the same degree sequence. When graphs are ordered lexicographically by their signature, a unique numerical list of structural descriptors, the similarity classes of $G(n,m)$ occur in contiguous blocks; the ¯rst graph in each similarity class is its sentinel. The sentinel of the ¯rst similarity class in each $G(n,m)$ is determined, and shown to be the unique realization of its degree sequence. The degree sequence of the last similarity class in each $G(n,m)$ is also determined, as are the exact size range for which it has more than one realization, and the exact size range for which its sentinel has more than one component.

    Item Type: Article
    Subjects: 00-xx General
    Faculty: UNSPECIFIED
    Depositing User: Stephanie
    Date Deposited: 18 Nov 2010 12:07
    Last Modified: 15 Apr 2014 08:46
    URI: https://docserver.carma.newcastle.edu.au/id/eprint/798

    Actions (login required)

    View Item