scientific article; zbMATH DE number 19200
[For the entire collection see Zbl 0734.00014.] A graph is called highly irregular if the neighbours of each vertex have distinct degrees. In 1987, \textit{Y. Alavi}, \textit{G. Chartrand}, \textit{F. R. K. Chung}, \textit{P. Erdős}, \textit{R. L. Graham} and \textit{O. R. Oellermann} [J. Graph Theory 11, No. 2, 235-249 (1987; Zbl 0665.05043)] showed that the minimum order of a highly irregular tree with maximum degree \(d\) is \(2^ d\). In this paper the authors investigate highly irregular multigraphs with no cycles of length greater than 2, called multitrees. For every \(s\geq 2\), they construct a recursive family \(\{T(d,s)\}_{d\geq 2}\) of highly irregular multitrees with maximum degree \(d\) and maximum multiplicity \(s\), with the property that the order \(f(d,s)\) and the size \(g(d,s)\) are minimum among all highly irregular multitrees with the same parameters \(d\) and \(s\). Moreover, \(T(d,2)\) is the unique minimal highly irregular multitree with the maximum degree \(d\) and maximum multiplicity 2. They obtain also some partial results concerning the behaviour of the functions \(f(d,s)\) and \(g(d,s)\).
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3976630)
