Premium
On the existence of N‐connected graphs with prescribed degrees (n ≧ 2)
Author(s) -
Wang D. L.,
Kleitman D. J.
Publication year - 1973
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230030303
Subject(s) - combinatorics , mathematics , vertex (graph theory) , degree (music) , graph , neighbourhood (mathematics) , discrete mathematics , mathematical analysis , physics , acoustics
In this paper we provide a simple algorithm for constructing an n‐ (vertex) connected graph with no multiple edges or loops having degree sequence satisfying the conditions indicated below. We prove these to be necessary and sufficient for the existence of such a graph. Our algorithm consists of constructing the graph in stages. An explicit construction is given if all degrees are n or n+1. Otherwise we choose a vertex with either the largest or smallest degree and connect it with a set of the remaining vertices having largest degrees, leaving a residual degree sequence for the rest of the graph which later can then be constructed by iteration. We connect the vertex of smallest degree above if the residual degrees after its connection are all at least n. Otherwise we connect the vertex of largest degree. The conditions on the degree sequence are that it must be realizable by a graph, all degrees must be at least n, and the number of edges which can avoid touching the n‐1 largest degree vertices are sufficient to form a tree among the other vertices.