Skip to Main content Skip to Navigation
Conference papers

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|]$.
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184371
Contributor : Coordination Episciences Iam <>
Submitted on : Friday, August 14, 2015 - 11:38:01 AM
Last modification on : Monday, November 16, 2020 - 3:56:03 PM
Long-term archiving on: : Sunday, November 15, 2015 - 11:02:44 AM

File

dmAE0143.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184371, version 1

Collections

Citation

Anna Lladó. Largest cliques in connected supermagic graphs. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.219-222. ⟨hal-01184371⟩

Share

Metrics

Record views

318

Files downloads

654