Lower and upper orientable strong diameters of graphs satisfying the Ore condition

摘要

Let D be a strong digraph. The strong distance between two vertices u and v in D, denoted by sd(D)(u, v), is the minimum size (the number of arcs) of a strong sub-digraph of D containing u and v. For a vertex v of D, the strong eccentricity se(v) is the strong distance between v and a vertex farthest from v. The minimum strong eccentricity among all vertices of D is the strong radius, denoted by srad(D), and the maximum strong eccentricity is the strong diameter, denoted by sdiam(D). The lower (resp. upper) orientable strong radius srad(G) (resp. SRAD(G)) of a graph G is the minimum (resp. maximum) strong radius over all strong orientations of G. The lower (resp. upper) orientable strong diameter sdiam(G) (resp. SDIAM(G)) of a graph G is the minimum (resp. maximum) strong diameter over all strong orientations of G. In this work, we determine a bound of the lower orientable strong diameters and the bounds of the upper orientable strong diameters for graphs G = (V, E) satisfying the Ore condition (that is, sigma(2)(G) = min{d(x) + d(y)| for all xy is not an element of E(G)} >= n), in terms of girth g and order n of G.