|
|||||
|
|
Sur la contractibilité d'un graphe orienté en K4 |
|
| Authors: | Pierre Duchet and Viktor Kaneti |
| Affiliation: | CNRS (IMAG) Université Joseph Fourier, Grenoble Cedex, France |
| Abstract: | We prove that every directed graph with n vertices at least 5n–8 arcs admits the complete symmetric digraph of order 4 as a minor. The result is sharp. This answers a question raised by Meyniel (1983). We conclude with some open problems. |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ | |