Anna Lladó - Largest cliques in connected supermagic graphs

dmtcs:3414 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) - https://doi.org/10.46298/dmtcs.3414
Largest cliques in connected supermagic graphs

Authors: Anna Lladó 1

  • 1 Universitat Politècnica de Catalunya [Barcelona]

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|]$.


Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: Labelings of graphs,magic graphs,Sidon sets,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo DOI 10.1016/s0012-365x(99)00110-7
  • 10.1016/s0012-365x(99)00110-7
On a question by Erdos about edge-magic graphs

Consultation statistics

This page has been seen 139 times.
This article's PDF has been downloaded 179 times.