Deakin University
Browse

File(s) under permanent embargo

Constructions of large graphs on surfaces

journal contribution
posted on 2014-07-01, 00:00 authored by R Feria-Puron, Guillermo Pineda VillavicencioGuillermo Pineda Villavicencio
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 (Formula presented). Our constructions produce new graphs of order (Formula presented) thus improving the former value. © 2013 Springer Japan.

History

Journal

Graphs and combinatorics

Volume

30

Pagination

895-908

Location

Tokyo, Japan

ISSN

0911-0119

Language

eng

Publication classification

C1.1 Refereed article in a scholarly journal

Copyright notice

2013, Springer Japan

Issue

4

Publisher

Springer

Usage metrics

    Research Publications

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC