Open AccessAntiregular graphs are universal for trees
Author(s) -
Russell Merris
Publication year - 2003
Publication title -
publikacija elektrotehnickog fakulteta - serija matematika
Language(s) - English
Resource type - Journals
eISSN - 2406-0852
pISSN - 0353-8893
DOI - 10.2298/petf0314001m
Subject(s) - combinatorics , wheel graph , path graph , mathematics , vertex (graph theory) , neighbourhood (mathematics) , graph factorization , graph , graph power , graph homomorphism , discrete mathematics , line graph , mathematical analysis
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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom