Functional graphs - 01/01/05
pages | 4 |
Iconographies | 0 |
Vidéos | 0 |
Autres | 0 |
Abstract |
A graph G is said to be a functional graph if there exist two mappings f and g from into a set F such that xy is an edge in G whenever or . Chvátal and Ebenegger proved that recognizing functional graphs is an NP-complete problem. Using the compactness theorem, we prove that if G is an infinite graph such that any finite subgraph of G is a functional graph, then G is a functional graph. We give an elementary proof of this fact in the infinite countable case. In the finite case, we prove that for n large enough, any graph of girth n containing at most vertices is a functional graph. It will be shown by an example that this bound is the best possible. To cite this article: A. El Sahili, C. R. Acad. Sci. Paris, Ser. I 341 (2005).
Le texte complet de cet article est disponible en PDF.Résumé |
Un graphe G est dit graphe fonctionnel sʼil existe deux applications f et g de dans un ensemble F telles que xy est une arête de G si et seulement si ou . Chvátal et Ebenegger ont prouvé que le problème de reconnaissance des graphes fonctionnels est NP-complet. En utilisant le théorème de compacité, nous prouvons que si G est un graphe infini tel que tout sous-graphe fini de G est fonctionnel, alors G est fonctionnel. Nous donnons une preuve élémentaire de ce fait dans le cas dénombrable. Dans le cas fini, nous prouvons que pour n suffisamment grand, tout graphe sans cycle dʼordre plus petit que n et contenant au plus sommets est un graphe fonctionnel. Il sera montré à lʼaide dʼun exemple que est la meilleure borne possible. Pour citer cet article : A. El Sahili, C. R. Acad. Sci. Paris, Ser. I 341 (2005).
Le texte complet de cet article est disponible en PDF.Plan
Vol 341 - N° 1
P. 1-4 - juillet 2005 Retour au numéroBienvenue sur EM-consulte, la référence des professionnels de santé.
L’accès au texte intégral de cet article nécessite un abonnement.
Bienvenue sur EM-consulte, la référence des professionnels de santé.
L’achat d’article à l’unité est indisponible à l’heure actuelle.
Déjà abonné à cette revue ?