- Title
- 4-Free Strong Digraphs with the Maximum Size
- Creator
- Zhang, Qifan; Xu, Liqiong; Lin, Yuqing
- Relation
- Parallel Processing Letters Vol. 33, Issue 1-2, no. 2350004
- Publisher Link
- http://dx.doi.org/10.1142/S0129626423500044
- Publisher
- World Scientific Publishing
- Resource Type
- journal article
- Date
- 2023
- Description
- Directed cycles in digraphs are useful in embedding linear arrays and rings, and are suitable for designing simple algorithm with low communication costs in parallel computer systems, thus the existence of directed cycles on digraphs has been largely investigated. Let n, k ≥ 2 be integers. Bermond et al. [Journal of Graph Theory 4(3) (1980) 337-341] proved that if the size of a strong digraph D with order n is at least (n-k+2/2) + k - 1, then the girth of D is no more than k. Consequently, when D is a 4-free strong digraph with order n, which means that every directed cycle in D has length at least 5, then the maximum size of D is (n-2 2) + 2. In this paper, we mainly give the structural characterizations for all 4-free strong digraphs of order n whose arc number exactly is (n-2 2) + 2.
- Subject
- interconnection networks; 4-free digraph; strong digraph; strong component
- Identifier
- http://hdl.handle.net/1959.13/1481292
- Identifier
- uon:50699
- Identifier
- ISSN:0129-6264
- Language
- eng
- Reviewed
- Hits: 2885
- Visitors: 2869
- Downloads: 0
Thumbnail | File | Description | Size | Format |
---|