Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/24602
- Title
- Maximum order of planar digraphs
- Author/Creator
-
Simanjuntak, R.;
Miller, Mirka
- 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.
- 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)
- Date
- 2005
- Publisher
- Springer Verlag
- Keyword(s)
-
moore graphs;
diameter 2
- Resource Type
- conference paper
- Identifier
- http://hdl.handle.net/1959.13/24602
- Identifier
- ISBN:3-540-24401-8
- Language
- eng
5 Visitors
7 Hits
0 Downloads
