Complete characterization of almost moore digraphs of degree three
- Authors: Baskoro, Edy , Miller, Mirka , Siran, Jozef , Sutton, Martin
- Date: 2005
- Type: Text , Journal article
- Relation: Journal of Graph Theory Vol. 48, no. 2 (2005), p. 112-126
- Full Text: false
- Reviewed:
- Description: It is well known that Moore digraphs do not exist except for trivial cases (degree 1 or diameter 1), but there are digraphs of diameter two and arbitrary degree which miss the Moore bound by one. No examples of such digraphs of diameter at least three are known, although several necessary conditions for their existence have been obtained. In this paper, we prove that digraphs of degree three and diameter k ≥ 3 which miss the Moore bound by one do not exist. © 2004 Wiley Periodicals, Inc.
- Description: C1
- Description: 2003000904
HSAGA and its application for the construction of near-Moore digraphs
- Authors: Tang, Jianmin , Miller, Mirka , Lin, Yuqing
- Date: 2008
- Type: Text , Journal article
- Relation: Journal of Discrete Algorithms Vol. 6, no. 1 (2008), p. 73-84
- Full Text: false
- Reviewed:
- Description: The degree/diameter problem is to determine the largest graphs or digraphs of given maximum degree and given diameter. This paper deals with directed graphs. General upper bounds, called Moore bounds, exist for the largest possible order of such digraphs of maximum degree d and given diameter k. It is known that simulated annealing and genetic algorithm are effective techniques to identify global optimal solutions. This paper describes our attempt to build a Hybrid Simulated Annealing and Genetic Algorithm (HSAGA) that can be used to construct large digraphs. We present our new results obtained by HSAGA, as well as several related open problems. © 2007 Elsevier B.V. All rights reserved.
- Description: C1