Search

For an arborescence \(A_r\), a directed pathos total digraph \(Q=DPT(A_r)\) has vertex set \(V(Q)=V(A_r)∪A(A_r)∪P(A_r)\), where \(V(A_r)\) is the vertex set, \(A(A_r)\) is the arc set, and \(P(A_r)\) is a directed pathos set of \(A_r\). The arc set \(A(Q)\ consists of the following arcs: \(ab\) such that \(a,b∈A(A_r)\) and the head of \(a\) coincides with the tail of \(b; uv\) such that \(u,v∈V(A_r)\) and \(u\) is adjacent to \(v; au(ua)\) such that \(a∈A(A_r)\) and \(u∈V(A_r)\) and the head (tail) of \(a\) is \(u; Pa\) such that \(a∈A(A_r)\) and \(P∈P(A_r)\) and the arc \(a\) lies on the directed path \(P; P_i, P_j\ such that \(P_i,P_j∈P(A_r)\) and it is possible to reach the head of \(P_j\) from the tail of \(P_i\) through a common vertex, but it is possible to reach the head of \(P_i\) from the tail of \(P_j\). For this class of digraphs we discuss the planarity; outerplanarity; maximal outerplanarity; minimally nonouterplanarity; and crossing number one properties of these digraphs. The problem of reconstructing an arborescence from its directed pathos total digraph is also presented.

Let \(D\) be a connected digraph of order \(n\); \((n \geq 3)\) and let \(B(D)=\{B_1,B_2,\ldots,B_N\}\) be a set of blocks of \(D\). The block digraph \(Q=\mathbb{B}(D)\) has vertex set \(V(Q)=B(D)\) and arc set \(A(Q)=B_iB_j\) and \(B_i,B_j \in V(Q),\) \(B_i,B_j\) have a cut-vertex of \(D\) in common and every vertex of \(B_j\) is reachable from every other vertex of \(B_i\) We study the properties of \(\mathbb{B}(D)\) and present the characterization of digraphs whose \(\mathbb{B}(D)\) are planar; outerplanar; maximal outerplanar; minimally nonouterplanar; Eulerian; and Hamiltonian.

The path number of a graph G is the number of paths in any pathos. The path number of a tree T equals k, where 2k is the number of odd degree vertices of T Harary and Stanton calculated the path number of certain classes of graphs like trees and complete graphs.