Let G be a multigraph. A transition in G is a pair of adjacent edges. For each vertex x of G , a set T ( x ) of allowed transition with respect to x is a set of unordered pairs of edges incident to x . A transition system T is a set { T ( x ): x ∈ V ( G )}, where T ( x ) is a fixed set of allowed transition with respect to x . Given a multigraph G and a transition system T , for each x ∈ V ( G ), the transition graph of x , denoted by G x , is a graph such that its vertex set is the set of edges incident to x ; and two vertices e and g of G x are adjacent whenever eg ∈ T ( x ). A trail in G is T -compatible if for every , . In this paper we deal with the problem of finding T -compatible trails between s and t two given vertices in a multigraph with transition system T . First, we prove that finding a T -compatible trail between two given edges can be done in polynomial time. Consequently, find a T -compatible trail can be done in polynomial time. Moreover, it can be found a shortest T -compatible trail and a closed T -compatible trail containing a given vertex in polynomial time. Finally, we study multigraphs with transition systems such that their transition graph is connected or complete multipartite graph. The properly colored setting is a particular case of transition systems where all its transition graphs are complete multipartite graphs.

A kernel in a digraph is an independent and absorbent subset of its vertex set. A digraph is critical kernel imperfect if it does not have a kernel, but every proper induced subdigraph does. In this article, we characterize asymmetrical 4-quasi-transitive and 4-transitive digraphs, as well as 2-anti-transitive, and asymmetrical 4-anti-transitive digraphs with bounded diameter, which are critical kernel imperfect.

Let D be a digraph with minimum indegree at least one. The following results are proved: a digraph D has a semikernel if and only if its line digraph $L(D)$ does; the number of (k,1)-kernels in L(D) is less than or equal to that in D; if the number of (k,l)-kernels in D is less than or equal to the number of (2,l)-kernels in L(D), and if L(D) has a (k,l)-kernel, then D has a (k',l')-kernel for $k'+l\leq k$, $l\leq l'$. As a consequence, it obtains previous results about kernels and quasikernels in the line digraph. It is also proved that any digraph has a (k,l)-kernel with $l\geq 2k-2$, $k\geq 1$, generalizing a previous result on the existence of quasikernels in digraphs.

It is proved that the number of semikernels (quasi kernels) of a digraph D is less than or equal to the number of semikernels (quasi kernels) of its line digraph $L( D )$. It is also proved that the number of Grundy functions of D is equal to the number of Grundy functions of its line digraph $L( D )$ (in the case where every vertex of D has indegree at least one).