The degree-diameter problem for sparse graph classes

被引：0
|
作者：
Pineda-Villavicencio, Guillermo [1 ]
Wood, David R. [2 ]
机构：
[1] Federat Univ Australia, Ctr Informat & Appl Optimisat, Ballarat, Vic, Australia
[2] Monash Univ, Sch Math Sci, Melbourne, Vic 3004, Australia
来源：
ELECTRONIC JOURNAL OF COMBINATORICS | 2015年 / 22卷 / 02期
基金：
澳大利亚研究理事会;
关键词：
degree-diameter problem; treewidth; arboricity; sparse graph; surface graph; apex-minor-free graph; EXTREMAL FUNCTION; PLANAR GRAPHS;
D O I：
暂无
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
The degree-diameter problem asks for the maximum number of vertices in a graph with maximum degree Delta and diameter k. For fixed k, the answer is Theta(Delta(k)). We consider the degree-diameter problem for particular classes of sparse graphs, and establish the following results. For graphs of bounded average degree the answer is Theta(Delta(k-1)), and for graphs of bounded arboricity the answer is Theta(Delta([k/2])) in both cases for fixed k. For graphs of given treewidth, we determine the the maximum number of vertices up to a constant factor. Other precise bounds are given for graphs embeddable on a given surface and apex-minor-free graphs.
引用
收藏
页数：20
相关论文
共 50 条
  • [1] THE DEGREE-DIAMETER PROBLEM FOR OUTERPLANAR GRAPHS
    Dankelmann, Peter
    Jonck, Elizabeth
    Vetrik, Tomas
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2017, 37 (03) : 823 - 834
  • [2] Improved lower bounds on the degree-diameter problem
    Zhang, Tao
    Ge, Gennian
    JOURNAL OF ALGEBRAIC COMBINATORICS, 2019, 49 (02) : 135 - 146
  • [3] t-STRONG CLIQUES AND THE DEGREE-DIAMETER PROBLEM
    Debski, Michal
    Sleszynska-Nowak, Malgorzata
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2021, 35 (04) : 3017 - 3029
  • [4] Tree densities in sparse graph classes
    Huynh, Tony
    Wood, David R.
    CANADIAN JOURNAL OF MATHEMATICS-JOURNAL CANADIEN DE MATHEMATIQUES, 2022, 74 (05): : 1385 - 1404
  • [5] The Firefighter problem on graph classes
    Fomin, Fedor V.
    Heggernes, Pinar
    van Leeuwen, Erik Jan
    THEORETICAL COMPUTER SCIENCE, 2016, 613 : 38 - 50
  • [6] DEGREE/DIAMETER PROBLEM FOR TREES AND PSEUDOTREES
    Christou, Michalis
    Iliopoulos, Costas S.
    Miller, Mirka
    AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2013, 10 (04) : 377 - 389
  • [7] Degree diameter problem on honeycomb networks
    Holub, Premysl
    Miller, Mirka
    Perez-Roses, Hebert
    Ryan, Joe
    DISCRETE APPLIED MATHEMATICS, 2014, 179 : 139 - 151
  • [8] Degree/diameter problem for mixed graphs
    Lopez, Nacho
    Perez-Roses, Hebert
    2ND INTERNATIONAL CONFERENCE OF GRAPH THEORY AND INFORMATION SECURITY, 2015, 74 : 2 - 9
  • [9] Kernelization using structural parameters on sparse graph classes
    Gajarsky, Jakub
    Hlineny, Petr
    Obdrzalek, Jan
    Ordyniak, Sebastian
    Reidl, Felix
    Rossmanith, Peter
    Villaamil, Fernando Sanchez
    Sikdar, Somnath
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2017, 84 : 219 - 242
  • [10] On the Complexity of List H-Packing for Sparse Graph Classes
    Gima, Tatsuya
    Hanaka, Tesshu
    Kobayashi, Yasuaki
    Otachi, Yota
    Shirai, Tomohito
    Suzuki, Akira
    Tamura, Yuma
    Zhou, Xiao
    WALCOM: ALGORITHMS AND COMPUTATION, WALCOM 2024, 2024, 14549 : 421 - 435
12345