- Title
- On diregularity of digraphs of defect at most two
- Creator
- Dafik; Miller, Mirka; Iliopoulos, Costas; Ryjacek, Zdenek
- Relation
- Journal of Combinatorial Mathematics and Combinatorial Computing Vol. 71, p. 21-37
- Relation
- http://www.charlesbabbage.org
- Publisher
- Charles Babbage Research Centre
- Resource Type
- journal article
- Date
- 2009
- Description
- Since Moore digraphs do not exist for k ≠ 1 and d ≠ 1, the problem of finding digraphs of out-degree d ≥ 2, diameter k ≥ 2 and order close to the Moore bound, becomes an interesting problem. To prove the non-existence of such digraphs or to assist in their construction (if they exist), we first may wish to establish some properties that such digraphs must possess. In this paper we consider the diregularity of such digraphs. It is easy to show that any digraph with out-degree at most d ≥ 2, diameter k ≥ 2 and order one or two less than Moore bound must have all vertices of out-degree d. However, establishing the regularity or otherwise of the in-degree of such a digraph is not easy. In this paper we prove that all digraphs of defect two are either diregular or almost diregular. Additionally, in the case of defect one we present a new, simpler and shorter, proof that a digraph of defect one must be diregular, and in the case of defect two and for d = 2 and k ≥ 3, we present an alternative proof that a digraph of defect two must be diregular.
- Subject
- digraphs; diregularity; regularity; defect
- Identifier
- http://hdl.handle.net/1959.13/916945
- Identifier
- uon:8153
- Identifier
- ISSN:0835-3026
- Language
- eng
- Reviewed
- Hits: 4724
- Visitors: 4676
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|