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

Présenté par : Jean-Yves Girard

El Sahili, Amine1
1 Lebanese university I, El hadas, Beyrout, Lebanon
Comptes Rendus. Mathématique, Tome 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
El Sahili, Amine 1

1 Lebanese university I, El hadas, Beyrout, Lebanon 
@article{CRMATH_2005__341_1_1_0,
     author = {El Sahili, Amine},
     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},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2005.05.021/}
}
TY  - JOUR
AU  - El Sahili, Amine
TI  - Functional graphs
JO  - Comptes Rendus. Mathématique
PY  - 2005
SP  - 1
EP  - 4
VL  - 341
IS  - 1
PB  - Elsevier
UR  - http://www.numdam.org/articles/10.1016/j.crma.2005.05.021/
DO  - 10.1016/j.crma.2005.05.021
LA  - en
ID  - CRMATH_2005__341_1_1_0
ER  - 
%0 Journal Article
%A El Sahili, Amine
%T Functional graphs
%J Comptes Rendus. Mathématique
%D 2005
%P 1-4
%V 341
%N 1
%I Elsevier
%U http://www.numdam.org/articles/10.1016/j.crma.2005.05.021/
%R 10.1016/j.crma.2005.05.021
%G en
%F CRMATH_2005__341_1_1_0
El Sahili, Amine. Functional graphs. Comptes Rendus. Mathématique, Tome 341 (2005) no. 1, pp. 1-4. doi : 10.1016/j.crma.2005.05.021. http://www.numdam.org/articles/10.1016/j.crma.2005.05.021/

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

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

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

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

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

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

Cité par Sources :