zbMATH — the first resource for mathematics

New bounds on the number of edges in a \(k\)-map graph. (English) Zbl 1091.05022
Chwa, Kyung-Yong (ed.) et al., Computing and combinatorics. 10th annual international conference, COCOON 2004, Jeju Island, Korea, August 17–20, 2004. Proceedings. Berlin: Springer (ISBN 3-540-22856-X/pbk). Lecture Notes in Computer Science 3106, 319-328 (2004).
Summary: It is known that for every integer \(k \geq 4\), each \(k\)-map graph with \(n\) vertices has at most \(kn-2 k\) edges. Previously, it was open whether this bound is tight or not. We show that this bound is tight for \(k =4\). We also show that this bound is not tight for large enough \(k\); more precisely, we show that for every \(0 < \varepsilon < \frac{3}{328}\) and for every integer \(k \geq \frac{140}{41\varepsilon}\), each \(k\)-map graph with \(n\) vertices has at most \((\frac{325}{328}+\varepsilon)kn - 2k\) edges. We further show that for every positive multiple \(k\) of 6, there are infinitely many integers \(n\) such that some \(k\)-map graph with \(n\) vertices has at least \((\frac{11}{12}k+\frac{1}{3})n\) edges.
For the entire collection see [Zbl 1053.68004].

05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: DOI