A simple criterion on degree sequences of graphs |
| |
Authors: | Amitabha Tripathi |
| |
Affiliation: | a Department of Mathematics, Indian Institute of Technology, Hauz Khas, New Delhi-110016, India b Department of Electrical Engineering, Indian Institute of Technology, Hauz Khas, New Delhi-110016, India |
| |
Abstract: | A finite sequence of nonnegative integers is called graphic if the terms in the sequence can be realized as the degrees of vertices of a finite simple graph. We present two new characterizations of graphic sequences. The first of these is similar to a result of Havel-Hakimi, and the second equivalent to a result of Erd?s & Gallai, thus providing a short proof of the latter result. We also show how some known results concerning degree sets and degree sequences follow from our results. |
| |
Keywords: | Degree sequence Graphic sequence Graphically equivalent sequence Perfect degree sequence Quasi-perfect degree sequence |
本文献已被 ScienceDirect 等数据库收录! |
|