Geodesic
The characterization of hereditary unigraphs on the canonical decomposition theory base
Trudy Instituta matematiki, Tome 20 (2012) no. 2, pp. 93-102 
R. A. Petrovich. The characterization of hereditary unigraphs on the canonical decomposition theory base. Trudy Instituta matematiki, Tome 20 (2012) no. 2, pp. 93-102. http://geodesic.mathdoc.fr/item/TIMB_2012_20_2_a9/
@article{TIMB_2012_20_2_a9,
     author = {R. A. Petrovich},
     title = {The characterization of hereditary unigraphs on the canonical decomposition theory base},
     journal = {Trudy Instituta matematiki},
     pages = {93--102},
     year = {2012},
     volume = {20},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMB_2012_20_2_a9/}
}
TY  - JOUR
AU  - R. A. Petrovich
TI  - The characterization of hereditary unigraphs on the canonical decomposition theory base
JO  - Trudy Instituta matematiki
PY  - 2012
SP  - 93
EP  - 102
VL  - 20
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/TIMB_2012_20_2_a9/
LA  - ru
ID  - TIMB_2012_20_2_a9
ER  - 
%0 Journal Article
%A R. A. Petrovich
%T The characterization of hereditary unigraphs on the canonical decomposition theory base
%J Trudy Instituta matematiki
%D 2012
%P 93-102
%V 20
%N 2
%U http://geodesic.mathdoc.fr/item/TIMB_2012_20_2_a9/
%G ru
%F TIMB_2012_20_2_a9

Voir la notice de l'article provenant de la source Math-Net.Ru

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.

[1] Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I., Lektsii po teorii grafov, M., 1990 | MR

[2] Tyshkevich R., “Decomposition of graphical sequences and unigraphs”, Discrete Math., 220 (2000), 201–238 | DOI | MR | Zbl

[3] Barrus M. D., On 2-switches and isomorphism classes, Elsevier, 2012 | MR

[4] Tyshkevich R. I., “Kanonicheskoe razlozhenie grafa”, Dokl. AN BSSR, 24:8 (1980), 677–679 | MR | Zbl

[5] Maksimovich O. V., Tyshkevich R. I., “Normalnaya forma dominantno-porogovogo grafa”, Dokl. NAN Belarusi, 53:2 (2009), 16–18 | MR

[6] Barrus M. D., Hartke S. G., Kumbat M., “Graph classes characterized both by forbidden subgraphs and degree sequences”, Graph Theory, 2008, no. 2, 131–148 | DOI | MR | Zbl

[7] Tyshkevich R. I., Suzdal S. V., Maksimovich O. V., Petrovich R. A., “Algebraicheskaya teoriya dekompozitsii grafov: iz istorii, poslednie dostizheniya, perspektivy”, Vestnik BGU. Ser. 1, 2011, no. 3, 126–138 | MR | Zbl

[8] Tyshkevich R. I., Suzdal S. V., “Dekompozitsiya grafov”, Izbr. tr. BGU, 6 (2001), 482–500