On commutativity of two unary digraph operations: Subdividing and line-digraphing

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.     

The k-point Exponent Set of Primitive Digraphs with Girth 2

Let D =(V,E)be a primitive digraph.The vertex exponent of D at a vertex v∈V,denoted by exPD(V),is the least integer p such that there is a v→u walk of length p for each u∈V.Following Brualdi and Liu,we order the vertices of D so that exPD(v_1)≤exPD(v_2)≤…≤exPD(v_n).Then exPD(v_k)is called the k- point exponent of D and is denoted by exP_D(k),1≤k≤n.In this paper we define e(n,k):=max{exp_D(k)|D∈PD(n,2)} and E(n,k):= {expD(k)|D∈PD(n,2)},where PD(n,2)is the set of all primitive digraphs of order n with girth 2.We completely determine e(n,k)and E(n,k)for all n,k with n≥3 and 1≤k≤n.     

Chain Dominated Orders

We study finite partial orders which have a chain such that every element of the order either belongs to this chain or has all its covers in this chain. We show that such orders are exactly the orders being both interval orders and truncated lattices. We prove that their jump number is polynomially tractable and that their dimension is unbounded. We also show that every order admits a visibility model having such an order as host.     

On the structure of the adjacency matrix of the line digraph of a regular digraph

We show that the adjacency matrix M of the line digraph of a d-regular digraph D on n vertices can be written as M=AB, where the matrix A is the Kronecker product of the all-ones matrix of dimension d with the identity matrix of dimension n and the matrix B is the direct sum of the adjacency matrices of the factors in a dicycle factorization of D.     

有向循环图的直径与覆盖指数

本文给出了有向循环图的直径的一个关系式,并讨论了直径与覆盖指数之间的关系。     

A reflexive digraph that is retraction trivial but not endomorphism trivial

In this note we give an example of a reflexive digraph that has no non-trivial retractions, but does have non-trivial endomorphisms.     

An information‐combining model for expectation states theory: Derivation and tests

Our status‐related behavior toward others is a function of the characteristics we perceive them to possess. Expectation states theory specifies the nature of the relationship between social characteristics and behavior, but until recently was limited to situations in which only one characteristic is perceived. This paper adds to the theory additional general assumptions from which an information‐combining model is derived. This model specifies status‐related behavior in multiple characteristic situations and other circumstances beyond the original scope of the theory. Comparisons of the model with other formulations provide excellent support.     

k‐Kings in k‐Quasitransitive Digraphs

Let D be a digraph with vertex set and arc set . A vertex x is a k‐king of D, if for every , there is an ‐path of length at most k. A subset N of is k‐independent if for every pair of vertices , we have and ; it is l‐absorbent if for every there exists such that . A ‐kernel of D is a k‐independent and l‐absorbent subset of . A k‐kernel is a ‐kernel. A digraph D is k‐quasitransitive, if for any path of length k, x₀ and are adjacent. In this article, we will prove that a k‐quasitransitive digraph with has a k‐king if and only if it has a unique initial strong component and the unique initial strong component is not isomorphic to an extended ‐cycle where each has at least two vertices. Using this fact, we show that every strong k‐quasitransitive digraph has a ‐kernel.     

Constructing continuum many countable, primitive, unbalanced digraphs

We construct continuum many non-isomorphic countable digraphs which are highly arc transitive, have finite out-valency and infinite in-valency, and whose automorphism groups are primitive.