Diameter of orientations of graphs with given minimum degree期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

Diameter of orientations of graphs with given minimum degree

Institution:	1. School of Mathematics, Statistics and Computer Science, University of KwaZulu-Natal, Pietermaritzburg, South Africa;2. Department of Pure and Applied Mathematics, University of Johannesburg, Johannesburg, South Africa

Abstract:	We show that every bridgeless graph of order $n$ and minimum degree $δ$ has a strongly connected orientation of diameter at most $\frac{11}{δ + 1} n + 9$ , and such an orientation can be found in polynomial time.

Keywords:
本文献已被 ScienceDirect 等数据库收录！