Constructions of Large Graphs on Surfaces

We consider the degree/diameter problem for graphs embedded in a surface, namely, given a surface Σ and integers Δ and k , determine the maximum order N (Δ, k ,Σ) of a graph embeddable in Σ with maximum degree Δ and diameter k . We introduce a number of constructions which produce many new largest k...

Full description

Saved in:
Bibliographic Details
Published in:Graphs and combinatorics 2014-07, Vol.30 (4), p.895-908
Main Authors: Feria-Puron, Ramiro, Pineda-Villavicencio, Guillermo
Format: Article
Language:English
Subjects:
Combinatorial analysis
Combinatorics
Construction
Engineering Design
Graphs
Integers
Lower bounds
Mathematics
Mathematics and Statistics
Original Paper
Tables
Texts
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the degree/diameter problem for graphs embedded in a surface, namely, given a surface Σ and integers Δ and k , determine the maximum order N (Δ, k ,Σ) of a graph embeddable in Σ with maximum degree Δ 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 Σ of Euler genus g and an odd diameter k , the current best asymptotic lower bound for N (Δ, k ,Σ) is given by Our constructions produce new graphs of order thus improving the former value.
ISSN:0911-0119
1435-5914
DOI:10.1007/s00373-013-1323-y