首页 | 本学科首页   官方微博 | 高级检索  
     检索      


On commutativity of two unary digraph operations: Subdividing and line-digraphing
Authors:Fuji Zhang  Zhibo Chen
Institution:a Department of Mathematics, Xiamen University, Xiamen 361005, China
b Department of Mathematics, Penn State University, McKeesport Campus, McKeesport, PA 15132, USA
Abstract:For a digraph D, let L(D) and S(D) denote its line digraph and subdivision digraph, respectively. The motivation of this paper is to solve the digraph equation L(S(D))=S(L(D)). We show that L(S(D)) and S(L(D)) are cospectral if and only if D and L(D) have the same number of arcs. Further, we characterize the situation that L(S(D)) and S(L(D)) are isomorphic. Our approach introduces the new notion, the proper image D* of a digraph D, and a new type of connectedness for digraphs. The concept D* plays an important role in the main result of this paper. It is also useful in other aspects of the study of line digraphs. For example, L(D) is connected if and only if D* is connected; L(D) is functional (contrafunctional) if and only if D* is functional (contrafunctional). Some related results are also presented.
Keywords:Line digraph  Subdivision digraph  Proper image of a digraph  Properly connected digraph  Characteristic polynomial  Digraph equation
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号