×

zbMATH — the first resource for mathematics

Antiregular graphs are universal for trees. (English) Zbl 1088.05505
A graph on \(n\) vertices is antiregular if its vertex degrees take on \(n-1\) different values. For every \(n\geq2\) there is an unique connected antiregular graph on \(n\) vertices denoted by \(A_n\). It is proved that every tree is isomorphic to a subgraph of \(A_n\).

MSC:
05C90 Applications of graph theory
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C17 Perfect graphs
05C05 Trees
PDF BibTeX XML Cite
Full Text: DOI