Highly irregular graphs with extreme numbers of edges

A simple connected graph is highly irregular if each of its vertices is adjacent only to vertices with distinct degrees. In this paper we find: (1) the greatest number of edges of a highly irregular graph with n vertices, where n is an odd integer (for n even this number is given in [1]), (2) the sm...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 1997-02, Vol.164 (1), p.237-242
Main Authors: Majcher, Zofia, Michael, Jerzy
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A simple connected graph is highly irregular if each of its vertices is adjacent only to vertices with distinct degrees. In this paper we find: (1) the greatest number of edges of a highly irregular graph with n vertices, where n is an odd integer (for n even this number is given in [1]), (2) the smallest number of edges of a highly irregular graph of given order.
ISSN:0012-365X
1872-681X
DOI:10.1016/S0012-365X(96)00056-8