Publikacije Elektrotehnickog fakulteta - serija: matematika 2003 Issue 14, Pages: 1-3
Full text ( 90 KB)
Cited by

Antiregular graphs are universal for trees

Merris Russell

A graph on n vertices is antiregular if its vertex degrees take on n − 1 different values. For every n ≥ 2 there is a unique connected antiregular graph on n vertices. Call it An. (The unique disconnected antiregular graph on n vertices is Acn.) The main result of this note is that every tree on n vertices is isomorphic to a subgraph of An.

Keywords: Adjacency matrix, chordal graph, chromatic number, Laplacian matrix, matching number, perfect graph, threshold graph