Comptes Rendus
no. 1
Logic/Combinatorics
Functional graphs
[Graphes fonctionnels]

Présenté par : Jean-Yves Girard

Amine El Sahili1
1 Lebanese university I, El hadas, Beyrout, Lebanon
Comptes Rendus. Mathématique, Volume 341 (2005) no. 1, pp. 1-4.

Un graphe G est dit graphe fonctionnel s'il existe deux applications f et g de V(G) dans un ensemble F telles que xy est une arête de G si et seulement si f(x)=g(y) ou g(x)=f(y). 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 3n−7 sommets est un graphe fonctionnel. Il sera montré à l'aide d'un exemple que 3n−7 est la meilleure borne possible.

A graph G is said to be a functional graph if there exist two mappings f and g from V(G) into a set F such that xy is an edge in G whenever f(x)=g(y) or g(x)=f(y). 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 3n−7 vertices is a functional graph. It will be shown by an example that this bound is the best possible.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2005.05.021
Amine El Sahili 1

1 Lebanese university I, El hadas, Beyrout, Lebanon 
@article{CRMATH_2005__341_1_1_0,
     author = {Amine El Sahili},
     title = {Functional graphs},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {1--4},
     publisher = {Elsevier},
     volume = {341},
     number = {1},
     year = {2005},
     doi = {10.1016/j.crma.2005.05.021},
     language = {en},
}
TY  - JOUR
AU  - Amine El Sahili
TI  - Functional graphs
JO  - Comptes Rendus. Mathématique
PY  - 2005
SP  - 1
EP  - 4
VL  - 341
IS  - 1
PB  - Elsevier
DO  - 10.1016/j.crma.2005.05.021
LA  - en
ID  - CRMATH_2005__341_1_1_0
ER  - 
%0 Journal Article
%A Amine El Sahili
%T Functional graphs
%J Comptes Rendus. Mathématique
%D 2005
%P 1-4
%V 341
%N 1
%I Elsevier
%R 10.1016/j.crma.2005.05.021
%G en
%F CRMATH_2005__341_1_1_0
Amine El Sahili. Functional graphs. Comptes Rendus. Mathématique, Volume 341 (2005) no. 1, pp. 1-4. doi : 10.1016/j.crma.2005.05.021. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2005.05.021/

[1] L.W. Beineke On derived graphs and digraphs (H. Sachs; H.J. Voss; H. Walter, eds.), Beitrage zur Graphentheorie, Teubner, Leipzig, 1968, pp. 17-23

[2] V. Chvátal; C. Ebenegger A note on line digraphs and the directed max-cut problem, Discrete Appl. Math., Volume 29 (1990), pp. 165-170

[3] A. El Sahili Functions and line digraphs, J. Graph Theory, Volume 4 (2003), pp. 296-303

[4] A. El Sahili A characterization problem on underlying graphs of line digraphs, J. Discrete Appl. Math., Volume 146 (2005), pp. 99-101

[5] M. Manzano Model Theory, Clarendon Press, Oxford, 1999

[6] B. Poizat A Course in Model Theory, Springer-Verlag, New York, 2000

Cité par Sources :

Commentaires - Politique

Ces articles pourraient vous intéresser

Graph-theoretical methods in general function theory

Amine El Sahili

C. R. Math (2002)

Antidirected paths in 5-chromatic digraphs

Amine El Sahili

C. R. Math (2004)

Claws in digraphs

Amine El Sahili; Mekkia Kouider

C. R. Math (2008)