有向P2-路图的结构性质

一个有向图D的有向Pk-路图Pk(D)是通过把D中的所有有向k长路作为点集;两点u= x1x2…xk+1,v=y1y2…yk+1之间有弧uv当xi=yi-1,i=2,3,…,k+1.明显地,当k=1时Pk(D)就是通常的有向线图L(D).在1,2]中,P2-路图得到完整刻画.在3]中,Broersma等人研究了有向...

Structural Properties of Directed P2-Path Graphs

The directed Pk-path graph Pk(D) of a digraph D is obtained by representing the directed paths of length k of D by vertices. Two vertices u = x1x2 … xk+1,v = y1y2 … yk+1 are joined by arc uv if xi = yi-1, i = 2, 3, …, k + 1. Clearly, the directed path graph Pk(D) is the line digraph L(D) when k = 1. In 1,2], the P2-path graph is characterized. In 3], several properties of P2(D) were studied, in particular with respect to isomorphism and traversability. Broersma et al. characterized all digraphs D with P2(D) ≌ D, show that P2(D1) ≌ P2(D2) "almost always" implies D1 ≌ D2- and characterized all digraphs D with P2(D) is Eulerian or Hamiltonian. Furthermore, for any digraph D with at least one directed path of length 2 and no directed cycle of length 2, P2(D) ≌ L (D). In this note, we obtain a characterization of P2(D), and give the upper bound and the lower bound of the diameter of the directed P2-path graph of a strongly connected digraph, and also a upper bound of the independence number of the directedP2-path graph of a regular digraph.