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 Connect in order to contact the contributor
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

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, ⟨10.46298/dmtcs.3414⟩. ⟨hal-01184371⟩

Share

Metrics

Record views

43

Files downloads

406