Constructions of large graphs on surfaces

DOI10.1007/S00373-013-1323-YMaRDI QIDQ742602zbMATH OpenOpenAlexFDO

Authors Guillermo Pineda-Villavicencio, Ramiro Feria-Purón

Publication date 19 September 2014

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.1648

zbMATH Keywords

graphs on surfacesmap colouring theorem

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35)

Abstract: We consider the degree/diameter problem for graphs embedded in a surface, namely, given a surface $Sigma$ and integers $Delta$ and $k$, determine the maximum order $N(Delta,k,Sigma)$ of a graph embeddable in $Sigma$ with maximum degree $Delta$ and diameter $k$. We introduce a number of constructions which produce many new largest known planar and toroidal graphs. We record all these graphs in the available tables of largest known graphs. Given a surface $Sigma$ of Euler genus $g$ and an odd diameter $k$, the current best asymptotic lower bound for $N(Delta,k,Sigma)$ is given by [sqrt{frac{3}{8}g}Delta^{lfloor k/2 floor}.] Our constructions produce new graphs of order [�egin{cases}6Delta^{lfloor k/2 floor}& ext{if $Sigma$ is the Klein bottle}\ (frac{7}{2}+sqrt{6g+frac{1}{4}})Delta^{lfloor k/2 floor}& ext{otherwise,}end{cases}] thus improving the former value by a factor of 4.

Recommendations

• On the maximum order of graphs embedded in surfaces
• Maximum size of a planar graph with given degree and even diameter
• Constructions of large planar networks with given degree and diameter
• New constructions of large scale planar networks with given diameter and maximum degree
• Large graphs with given degree and diameter. II

Cites work

• Constructions of large planar networks with given degree and diameter
• Extremal graphs of diameter two and given maximum degree, embeddable in a fixed surface
• Graphs on surfaces
• scientific article; zbMATH DE number 2172769 (Why is no real title available?)
• scientific article; zbMATH DE number 2187701 (Why is no real title available?)
• Largest 6-regular toroidal graphs for a given diameter
• Largest planar graphs and largest maximal planar graphs of diameter two
• Maximum size of a planar graph with given degree and even diameter
• Moore graphs and beyond: a survey of the degree/diameter problem
• The degree-diameter problem for sparse graph classes

Cited in

(5)

• Topological inductive constructions for tight surface graphs
• On the maximum order of graphs embedded in surfaces
• scientific article; zbMATH DE number 4145948 (Why is no real title available?)
• Largest 6-regular toroidal graphs for a given diameter
• The degree/diameter problem in maximal planar bipartite graphs

This page was built for publication: Constructions of large graphs on surfaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q742602)