MATHEMATICA BOHEMICA, Vol. 123, No. 4, pp. 365-369 (1998)

Digraphs contractible onto ${}^*\!K_3$.

Stefan Janaqi, F. Lescure, M. Maamoun, H. Meyniel

Stefan Janaqi, Laboratoire Leibniz, IMAG, Grenoble, France; F. Lescure, M. Maamoun, H. Meyniel, Equipe Combinatorie, CNRS, Université Paris VI, Paris, France

Abstract: We show that any digraph on $n\ge3$ vertices and with not less than $3n-3$ arcs is contractible onto ${}^*\!K_3$

Keywords: digraph, minor, contraction

Classification (MSC2000): 05C20

Full text of the article:

[Previous Article] [Next Article] [Contents of this Number] [Journals Homepage]
© 2000 ELibM for the EMIS Electronic Edition