- Title
- Maximum order of planar digraphs
- Creator
- Simanjuntak, R.; Miller, Mirka
- Relation
- Combinatorial Geometry and Graph Theory: Indonesia-Japan Joint Conference, IJCCGGT 2003 Bandung, Indonesia, September 13-16, 2003. Revised Selected Papers. (Bandung, Indonesia September 13-16, 2003)
- Publisher
- Springer Verlag
- Resource Type
- conference paper
- Date
- 2005
- Description
- We consider the degree/diameter problem for directed planar graphs. We show that planar digraphs with diameter 2 and maximum out-degree and in-degree d, d >= 41, cannot have more than 2d vertices. We show that 2d is the best possible upper bound by constructing planar digraphs of diameter 2 having exactly 2d vertices. Furthermore, we give upper and lower bounds for the largest possible order of planar digraphs with diameter greater than 2.
- Subject
- moore graphs; diameter 2
- Identifier
- uon:512
- Identifier
- http://hdl.handle.net/1959.13/24602
- Identifier
- ISBN:3-540-24401-8
- Language
- eng
- Hits: 463
- Visitors: 387
- Downloads: 0