テクノロジーと最適化のグローバル ジャーナル

Vertex Exponents of Two-Colored Primitive Extremal Ministrong Digraphs

Abstract

Saib Suwilo

A two-colored digraph D(2) is a digraph D whose each of its arcs is colored by either red or blue. A two-colored digraph D(2) is primitive provided that there is a positive integer h+k such that any pair of vertices in D(2) can be connected by a walk of length h+k consisting of h red arcs and k blue arcs. The smallest of such positive integer h+k is the exponent of D(2) and is denoted by exp(D(2)). The exponent of a vertex v in a two-colored digraph D(2) is the smallest positive integer s+t such that for each vertex x in D(2) there is a walk of length s+t consisting of s red arcs and t blue arcs. In this paper we discuss the vertex exponents of a primitive twocolored extremal ministrong digraph D(2) on n vertices. If D(2) has one blue arc, we show that the exponents of vertices of D(2) lie on [n2 – 5n + 8, n2 – 3n + 1]. If D(2) has two blue arcs, we show that the exponents of vertices in D(2) lie on [n2 – 4n + 4, n2 – n].