THE (∆ , D)-PROBLEM IN PLANAR BIPARTITE MIXED GRAPHS

Abstract

The objective of this research is to find and to study the largest graphs with given       maximum degree ∆ and diameter D.  In this paper we study the planar bipartite mixed graphs  (partially directed graphs that have both arcs and edges ) ,  we prove that the maximum number of      vertices is n = 2D for ∆ = 3, then we show that in the maximal planar bipartite mixed graphs  (graphs where every face is a rectangle) for D = 3, ∆ = 3 (respectively D =4, ∆=3) exist and      the number of vertices is n =6 (respectively n =8)     Finally, we construct a family of maximal planar bipartite mixed graphs G_i of order     ,     maximum degree ∆_i =2ⁱ⁺¹+1 , for all natural numbers i and diameter D (calculated using the Breadth-First-Search (BFS) method ).