×

Highly irregular graphs. (English) Zbl 0665.05043

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\neq w\) implies that \(\deg_Hu\neq \deg_Hw\) 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 \log_23+o(1)\) and conjectured that \(Hl(n)\sim cn^2\) 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 \(\{H_m\}\) 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 \(2^d\). 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

MSC:

05C75 Structural characterization of families of graphs
05C30 Enumeration in graph theory
05C05 Trees
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Behzad, Amer. Math. Monthly 74 pp 962– (1967)
[2] Erdös, Amer. Math. Monthly 70 pp 1074– (1963)
[3] Theorie der endlichen und unendlichen Graphen. Leipzig (1936). Reprinted Chelsea, New York (1950).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.