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 条
  • [41] The minimum degree Group Steiner problem
    Kortsarz, Guy
    Nutov, Zeev
    DISCRETE APPLIED MATHEMATICS, 2022, 309 : 229 - 239
  • [42] MINOR-CLOSED GRAPH CLASSES WITH BOUNDED LAYERED PATHWIDTH
    Dujmovic, Vida
    Eppstein, David
    Joret, Gwenael
    Morin, Pat
    Wood, David R.
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2020, 34 (03) : 1693 - 1709
  • [43] Layered separators in minor-closed graph classes with applications
    Dujmovic, Vida
    Morin, Pat
    Wood, David R.
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2017, 127 : 111 - 147
  • [44] The complexity of finding uniform sparsest cuts in various graph classes
    Bonsma, Paul
    Broersma, Hajo
    Patel, Viresh
    Pyatkin, Artem
    JOURNAL OF DISCRETE ALGORITHMS, 2012, 14 : 136 - 149
  • [45] Complexity of rainbow vertex connectivity problems for restricted graph classes
    Lauri, Juho
    DISCRETE APPLIED MATHEMATICS, 2017, 219 : 132 - 146
  • [46] Graph classes with and without powers of bounded clique-width
    Bonomo, Flavia
    Grippo, Luciano N.
    Milanic, Martin
    Safe, Martin D.
    DISCRETE APPLIED MATHEMATICS, 2016, 199 : 3 - 15
  • [47] Thin graph classes and polynomial-time approximation schemes
    Dvorak, Zdenek
    SODA'18: PROCEEDINGS OF THE TWENTY-NINTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2018, : 1685 - 1701
  • [48] Overview of Sparse Graph for Multiple Access in Future Mobile Networks
    Lei, Jing
    Li, Baoguo
    Li, Erbao
    Gong, Zhenghui
    FREQUENZ, 2017, 71 (11-12) : 601 - 610
  • [49] GENERIC SPARSE GRAPH BASED CONVOLUTIONAL NETWORKS FOR FACE RECOGNITION
    Wu, Renjie
    Kamata, Sei-ichiro
    2021 IEEE INTERNATIONAL CONFERENCE ON IMAGE PROCESSING (ICIP), 2021, : 1589 - 1593
  • [50] Neighbor sum distinguishing total coloring of a kind of sparse graph
    Gong, Xiangnan
    Xu, Changqing
    Song, Hongjie
    Pan, Wenhua
    ARS COMBINATORIA, 2016, 127 : 133 - 141
12345