# Largest cliques in connected supermagic graphs

Abstract : A graph $G=(V,E)$ is said to be $\textit{magic}$ if there exists an integer labeling $f: V \cup E \to [1, |V \cup E|]$ such that $f(x)+f(y)+f(xy)$ is constant for all edges $xy \in E$. Enomoto, Masuda and Nakamigawa proved that there are magic graphs of order at most $3n^2+o(n^2)$ which contain a complete graph of order $n$. Bounds on Sidon sets show that the order of such a graph is at least $n^2+o(n^2)$. We close the gap between those two bounds by showing that, for any given graph $H$ of order $n$, there are connected magic graphs of order $n^2+o(n^2)$ containing $H$ as an induced subgraph. Moreover it can be required that the graph admits a supermagic labelling $f$, which satisfies the additional condition $f(V)=[1,|V|]$.
Keywords :
Type de document :
Communication dans un congrès
Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.219-222, 2005, DMTCS Proceedings
Domaine :

Littérature citée [11 références]

https://hal.inria.fr/hal-01184371
Contributeur : Coordination Episciences Iam <>
Soumis le : vendredi 14 août 2015 - 11:38:01
Dernière modification le : jeudi 11 mai 2017 - 01:02:53
Document(s) archivé(s) le : dimanche 15 novembre 2015 - 11:02:44

### Fichier

dmAE0143.pdf
Fichiers éditeurs autorisés sur une archive ouverte

### Identifiants

• HAL Id : hal-01184371, version 1

### Citation

Anna Lladó. Largest cliques in connected supermagic graphs. Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.219-222, 2005, DMTCS Proceedings. 〈hal-01184371〉

### Métriques

Consultations de la notice

## 259

Téléchargements de fichiers