Article

Access to the text (HTML) Access to the text (HTML)
PDF Access to the PDF text
Advertising


Access to the full text of this article requires a subscription.
  • If you are a subscriber, please sign in 'My Account' at the top right of the screen.

  • If you want to subscribe to this journal, see our rates

  • You can purchase this item in Pay Per ViewPay per View - FAQ : 30,00 € Taxes included to order
    Pages Iconography Videos Other
    4 0 0 0


Comptes Rendus Mathématique
Volume 341, n° 1
pages 1-4 (juillet 2005)
Doi : 10.1016/j.crma.2005.05.021
Received : 27 April 2005 ;  accepted : 4 May 2005
Functional graphs
Graphes fonctionnels
 

Amine El Sahili
Lebanese university I, El hadas, Beyrout, Lebanon 

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

The full text of this article is available in PDF format.
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).

The full text of this article is available in PDF format.


© 2005  Académie des sciences@@#104156@@
EM-CONSULTE.COM is registrered at the CNIL, déclaration n° 1286925.
As per the Law relating to information storage and personal integrity, you have the right to oppose (art 26 of that law), access (art 34 of that law) and rectify (art 36 of that law) your personal data. You may thus request that your data, should it be inaccurate, incomplete, unclear, outdated, not be used or stored, be corrected, clarified, updated or deleted.
Personal information regarding our website's visitors, including their identity, is confidential.
The owners of this website hereby guarantee to respect the legal confidentiality conditions, applicable in France, and not to disclose this data to third parties.
Close
Article Outline
You can move this window by clicking on the headline
@@#110903@@