The maximum girth and minimum circumference of graphs with prescribed radius and diameter

被引：1

作者：

Qiao, Pu ^{[1
]}

Zhan, Xingzhi ^{[1
]}

机构：

[1] East China Normal Univ, Dept Math, Shanghai 200241, Peoples R China

来源：

DISCRETE MATHEMATICS | 2018年 / 341卷 / 10期

关键词：

Girth; Circumference; Block; Radius; Diameter;

D O I：

10.1016/j.disc.2018.06.038

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Ostrand posed the following two questions in 1973. (1) What is the maximum girth of a graph with radius r and diameter d? (2) What is the minimum circumference of a graph with radius r and diameter d? Question 2 has been answered by Hrnciar who proves that if d <= 2r - 2 the minimum circumference is 4r - 2d. In this note we first answer Question 1 by proving that the maximum girth is 2r + 1. This improves on the obvious upper bound 2d + 1 and implies that every Moore graph is self-centered. We then prove a property of the blocks of a graph which implies Hrnciar's result. (C) 2018 Elsevier B.V. All rights reserved.

引用

页码：2827 / 2830

页数：4