DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

Largest cliques in connected supermagic graphs

Anna Lladó


A graph G=(V,E) is said to be magic if there exists an integer labeling f: V∪E →[1, |V∪E|] such that f(x)+f(y)+f(xy) is constant for all edges xy∈E. Enomoto, Masuda and Nakamigawa proved that there are magic graphs of order at most 3n2+o(n2) which contain a complete graph of order n. Bounds on Sidon sets show that the order of such a graph is at least n2+o(n2). 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 n2+o(n2) 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|].

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional