DIRECTED PATHOS MIDDLE DIGRAPH OF AN ARBORESCENCE

DIRECTED PATHOS MIDDLE DIGRAPH OF AN ARBORESCENCE

H. M. Nagesh

[PDF]

Abstract

A directed pathos middle digraph of an arborescence Ar, written Q = DPM(Ar), is the digraph whose vertex set V (Q) = V (Ar) [ A(Ar) [ P(Ar), where V (Ar) is the vertex set, A(Ar) is the arc set, and P(Ar) is a directed pathos set of Ar. The arc set A(Q) consists of the following arcs: ab such that a; b 2 A(Ar) and the head of a coincides with the tail of b; for every v 2 V (Ar), all arcs a1v; va2; for which v is a head of the arc a1 and tail of the arc a2 in Ar; Pa such that a 2 A(Ar) and P 2 P(Ar) and the arc a lies on the directed path P; PiPj such that Pi; Pj 2 P(Ar) and it is possible to reach the head of Pj from the tail of Pi through a common vertex, but it is possible to reach the head of Pi from the tail of Pj . The problem of reconstructing an arborescence from its directed pathos middle digraph is presented. The characterization of digraphs whose DPM(Ar) are planar; outerplanar; maximal outerplanar; and minimally non-outerplanar is studied.

Keywords

Line digraph, directed path number, crossing number, inner vertex number.