有向P_2-路图的结构性质(英文)  

Structural Properties of Directed P_2-Path Graphs

作　　者：庄蔚[1] 杨卫华[1] 

机构地区：[1]厦门大学数学科学学院,福建厦门361005

出　　处：《数学研究》2011年第1期16-21,共6页Journal of Mathematical Study

基　　金：supported by NSFC(10831001).

摘　　要：一个有向图D的有向P_k-路图P_k(D)是通过把D中的所有有向k长路作为点集;两点u=x_1x_2…x_(k+1),v=y_1y_2…y_(k+1)之间有弧uv当x_i=y_(i-1),i=2,3,…,k+1.明显地,当k=1时P_k(D)就是通常的有向线图L(D).在[1,2]中,P_2-路图得到完整刻画。在[3]中,Broersma等人研究了有向P_2-路图的一些性质,特别是在相似性和传递性方面。在他们的文章中,描述了所有与自身的有向P_2-路图同构的有向图D,证明了对于任意的有向图D_1和D_2,若P_2(D_1)(?)P_2(D_2),"几乎总是"暗示D_1(?)D_2,并描述了所有这样的有向图:其有向P_2-路图是欧拉图或哈密顿图。另外,对于任意一个不包含有向2长圈且至少包含一个有向2长路的有向图D,有P_2(D)(?)L^2(D).在这篇文章中我们刻画了有向P_2-路图。同时,我们考虑了有向P_2-路图的直径问题,并对于正则有向图,给出了其有向P_2-路图的独立数的一个上界。The directed P_k-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…x（k＋1）,v=y1y2…y（k＋1） are joined by arc uv if xi=y（i-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^2（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 directed P2-path graph of a regular digraph.

关 键 词：有向路图 直径 有向线图 

分 类 号：O157.5[理学—数学]