Functional graphs

Amine El Sahili

doi:10.1016/j.crma.2005.05.021

Logic/Combinatorics

Functional graphs

Presented by: Jean-Yves Girard

Amine El Sahili ¹

¹ Lebanese university I, El hadas, Beyrout, Lebanon

Comptes Rendus. Mathématique, Volume 341 (2005) no. 1, pp. 1-4

Abstract (Original language)
Résumé

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 $3 n - 7$ vertices is a functional graph. It will be shown by an example that this bound is the best possible.

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 $3 n - 7$ sommets est un graphe fonctionnel. Il sera montré à l'aide d'un exemple que $3 n - 7$ est la meilleure borne possible.

Received: 2005-04-27
Accepted: 2005-05-04
Published online: 2005-06-28

DOI: 10.1016/j.crma.2005.05.021

Author's affiliations:

Amine El Sahili ¹

¹ 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},
     year = {2005},
     publisher = {Elsevier},
     volume = {341},
     number = {1},
     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

References
Cited by

[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

Cited by Sources:

Comments - Policy