The characterization of hereditary unigraphs on the canonical decomposition theory base

R. A. Petrovich

Belarusian State University, Minsk

Abstract: Considered the class of hereditary unigraphs.
A graph determined up to isomorphism by its degree sequence is called a unigraph.
A graph is called a hereditary unigraph if all its vertex induced subgraphs is a unigraphs. It is known that not all unigraphs are hereditary.
It this paper the characterization of hereditary unigraphs on the canonical decomposition base is performed and a scheme of a linear algorithm that recognizes the property "to be a hereditary unigraph" is proposed.

UDC: 519.1

Received: 16.10.2012