Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 665.05043
Autor: Alavi, Yousef; Chartrand, Gary; Chung, F.R.K.; Erdös, Paul; Graham, Ronald L.; Oellermann, Ortrud R.
Title: Highly irregular graphs. (In English)
Source: J. Graph Theory 11, No.2, 235-249 (1987).
Review: Highly irregular graphs are defined as connected graphs H where every vertex v is adjacent only to vertices with distinct degree, or more formally: u,w in N(v), u\ne w implies that \degHu\ne \degHw with N(v) being the set of vertices adjacent to v. First the authors state some easy observations. For example a highly irregular graph H with maximum degree d has at least 2d vertices. Or for every positive integer d there exists a highly irregular graph H with maximum degree d (which may always be taken to be a tree). It is further shown that there are no highly irregular graphs of order n = 3, 5 or 7 while for all other positive integers n highly irregular graphs of order n exist.
Next an analogue to König's theorem about regular graphs is proved for irregular ones. It says that every graph of order n \geq 2 is an induced subgraph of a highly irregular graph of order 4n-4. A corollary shows that this bound cannot be improved in general. However, there also exists a class of graphs where the bound is not sharp. According to the authors it appears to be very difficult to determine the minimum order of a highly irregular graph containing G as an induced subgraph - even if G is regular.
The next question addressed is, how many highly irregular graphs exist. Let Hl(n) be the number of (nonisomorphic) highly irregular graphs and G(n) the total number of graphs with n vertices. It is shown that 1/16+o(1) < log Hl(n)/ log G(n) < 2-3/4 log23+o(1) and conjectured that Hl(n) ~ cn2 for some constant c.
From the definition of highly irregular graphs it can be supposed that they contain large independent sets of vertices. The authors show the existence of a family {Hm} of highly irregular graphs where almost all vertices are independent. Further it is derived that every highly irregular graph must have a moderately large independence number. Finally highly irregular trees are studied. The order of these trees with maximum degree d is proved to be at least 2d. In contrast to highly irregular graphs in general there exist no highly irregular trees where almost all vertices are independent. This result is provided by giving upper bounds for their independence numbers.
Reviewer: E.Maehle
Classif.: * 05C75 Structural characterization of types of graphs
05C30 Enumeration of graphs and maps
05C05 Trees
Keywords: independence number; enumeration of graphs; Highly irregular graphs; highly irregular trees
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag