Premium
Ranking measures for radially Moore graphs
Author(s) -
Capdevila Carles,
Conde Josep,
Exoo Geoffrey,
Gimbert Joan,
López Nacho
Publication year - 2010
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20377
Subject(s) - combinatorics , upper and lower bounds , mathematics , discrete mathematics , chordal graph , degree (music) , metric dimension , graph , 1 planar graph , physics , mathematical analysis , acoustics
For graphs with maximum degree d and diameter k , an upper bound on the number of vertices in the graphs is provided by the well‐known Moore bound (denoted by M d , k ). Graphs that achieve this bound (Moore graphs) are very rare, and determining how close one can come to the Moore bound has been a major topic in graph theory. Of particular note in this regard are the cage problem and the degree/diameter problem. In this article, we take a different approach and consider questions that arise when we fix the number of vertices in the graph at the Moore bound, but relax, by one, the diameter constraint on a subset of the vertices. In this context, regular graphs of degree d , radius k , diameter k + 1, and order equal to M d , k are called radially Moore graphs. We consider two specific questions. First, we consider the existence question (extending the work of Knor), and second, we consider some natural measures of how well a radially Moore graph approximates a Moore graph. © 2010 Wiley Periodicals, Inc. NETWORKS, 2010