𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Degree realization of undirected graphs in reduced form

✍ Scribed by J.N. Ayoub; I.T. Frisch

Publisher
Elsevier Science
Year
1970
Tongue
English
Weight
653 KB
Volume
289
Category
Article
ISSN
0016-0032

No coin nor oath required. For personal study only.

✦ Synopsis

AwwzucT : Necessary and su@cient conditions are given for a set of non-negative integers to be the degreea of vertices of an n-vertex undirected graph. The conditions and their proof are based on a novel decomposition procedure which gives some inkght in& the structure to he realized, and leads to a simple and e&Sent algorithm to construct the graph directly with a minimum number of parallel branches and a minimum number of self-loops. In the case in which the given set is not realizable, the algorithm, determines the least modi$cation necessary for the resulting set to be realizable.

I. Introduction

In this paper we are concerned with establishing necessary and sufficient conditions for a set of non-negative integers to be the degrees of vertices of an undirected n-vertex graph.

Hakimi (1, 2), has given necessary and sufficient conditions for the realizability of a set of non-negative integers as the degrees of a graph either with or without parallel branches. He has also given a realization algorithm in the case in which there are no parallel branches and no selfloops. Owens and Trent (3) studied the problem of evaluating the minimum number of singularities (self-loops and parallel branches) needed for a graph whose degrees are prescribed.

In this paper we give an alternative set of necessary and sufficient conditions for a set of non-negative integers to be realizable as the degrees of vertices of an undirected graph which enable us to present a realization algorithm for graphs with parallel branches and self-loops. Furthermore, the algorithm realizes such graphs directly in reduced form, i.e. with minimum numbers of self-loops and parallel branches.

II. Background

An undirected graph G = (V, r) consists of a set of elements called vertices and a set of unordered pairs of vertices called branches. The set of vertices is denoted by the symbol V and the set of branches by the symbol l?. Let

πŸ“œ SIMILAR VOLUMES

Realizability of p-point graphs with pre
Realizability of p-point graphs with prescribed minimum degree, maximum degree, and line connectivity
✍ F. T. Boesch; C. L. Suffel πŸ“‚ Article πŸ“… 1980 πŸ› John Wiley and Sons 🌐 English βš– 316 KB

## Abstract It is well known that certain graph‐theoretic extremal questions play a central role in the study of communication network vulnerability. Herein we consider a generalization of some of the classical results in this area. We define a (__p__, Ξ”, Ξ΄, Ξ») graph as a graph having __p__ points,

On the reduced signless Laplacian spectr
On the reduced signless Laplacian spectrum of a degree maximal graph
✍ Bit-Shun Tam; Shu-Hui Wu πŸ“‚ Article πŸ“… 2010 πŸ› Elsevier Science 🌐 English βš– 314 KB

For a (simple) graph G, the signless Laplacian of G is the matrix A(G) + D(G), where A(G) is the adjacency matrix and D(G) is the diagonal matrix of vertex degrees of G; the reduced signless Laplacian of G is the matrix (G) + B(G), where B(G) is the reduced adjacency matrix of G and (G) is the diago