Médecine

Paramédical

Autres domaines


S'abonner

Functional graphs - 01/01/05

Doi : 10.1016/j.crma.2005.05.021 
Amine El Sahili
Lebanese university I, El hadas, Beyrout, Lebanon 

Bienvenue 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.

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

Plan indisponible

© 2005  Académie des sciences. Publié par Elsevier Masson SAS. Tous droits réservés.
Ajouter à ma bibliothèque Retirer de ma bibliothèque Imprimer
Export

    Export citations

  • Fichier

  • Contenu

Vol 341 - N° 1

P. 1-4 - juillet 2005 Retour au numéro
Article précédent Article précédent
  • Editorial Board
| Article suivant Article suivant
  • Convergence to the equilibrium for the Pauli equation without detailed balance condition
  • Naoufel Ben Abdallah, Miguel Escobedo, Stéphane Mischler

Bienvenue 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 ?

;

Mon compte


Plateformes Elsevier Masson

Déclaration CNIL

EM-CONSULTE.COM est déclaré à la CNIL, déclaration n° 1286925.

En application de la loi nº78-17 du 6 janvier 1978 relative à l'informatique, aux fichiers et aux libertés, vous disposez des droits d'opposition (art.26 de la loi), d'accès (art.34 à 38 de la loi), et de rectification (art.36 de la loi) des données vous concernant. Ainsi, vous pouvez exiger que soient rectifiées, complétées, clarifiées, mises à jour ou effacées les informations vous concernant qui sont inexactes, incomplètes, équivoques, périmées ou dont la collecte ou l'utilisation ou la conservation est interdite.
Les informations personnelles concernant les visiteurs de notre site, y compris leur identité, sont confidentielles.
Le responsable du site s'engage sur l'honneur à respecter les conditions légales de confidentialité applicables en France et à ne pas divulguer ces informations à des tiers.