Narrow Results

In spectral graph theory, the Laplacian energy of undirected graphs has been studied extensively. However, there has been little work yet for digraphs. Recently, Perera and Mizoguchi (2010) introduced the directed Laplacian matrix$L=D-A$ and directed Laplacian energy$LE\left(G\right)=\sum _{i=1}^n{\lambda }_i^2$ using the second spectral moment of $L$ for a digraph $G$ with $n$ vertices, where $D$ is the diagonal out-degree matrix, and $A=\left(a_{ij}\right)$ with $a_{ij}=1$ whenever there is an arc $(i,j)$ from the vertex $i$ to the vertex $j$ and 0 otherwise. They studied the directed Laplacian energies of two special families of digraphs (simple digraphs and symmetric digraphs). In this paper, we extend the study of Laplacian energy for digraphs which allow both simple and symmetric arcs. We present lower and upper bounds for the Laplacian energy for such digraphs and also characterize the extremal graphs that attain the lower and upper bounds. We also present a polynomial algorithm to find an optimal orientation of a simple undirected graph such that the resulting oriented graph has the minimum Laplacian energy among all orientations. This solves an open problem proposed by Perera and Mizoguchi at 2010.

The reconfigurable architecture is a parallel computation model that consists of many processor elements (PEs) and a reconfigurable bus system. There are many variant proposed reconfigurable architectures, for example, reconfigurable mesh (R-Mesh), directional reconfigurable mesh (DR-Mesh), processor arrays with reconfigurable bus systems (PARBS), complete directional processor arrays with reconfigurable bus systems (CD-PARBS), reconfigurable multiple bus machine (RMBM), directional reconfigurable multiple bus machine (directional RMBM), and etc. In this paper, a transitive closure (TC) algorithm of digraph is proposed on the models without the directional capability (non-directional). Some related digraph problems, such as strongly connected digraph, strongly connected component (SCC), cyclic checking, and tree construction, can also be resolved by modifying our transitive closure algorithm. All the proposed algorithms are designed on a three-dimensional (3-D) n×n×n non-directional reconfigurable mesh, n is the number of vertices in a digraph D, and can resolve the respective problems in O(log d(D)) time, d(D) is the diameter of the digraph D. The cyclic checking problem can be further reduced to O(log c(D)) time, c(D) is the minimum distance of cycles in the digraph D. There exist two different approaches: the matrix multiplication approach on the non-directional models for algebraic path problems (APP) and s-t connectivity approach on the directional models. In this paper, we will use the tree construction algorithm to prove those two approaches are insufficient to resolve all digraph problems and demonstrate why our approach is so important and innovative for digraph problems on the reconfigurable models.

This paper corrects some mistakes about three theorems, two figures and some expressions on “finite field” in a literature, and then it analyzes the digraphs and period properties of the logistic map on residue class rings $Z(3^n)$ and $Z(p^n)$. Some theorems and conjectures are proved or given. To validate these properties, we make some numeral experiments and draw the relative figures and tables. So the theoretical analysis and numeral experiments show that there exists periods in the logistic map on $Z(3^n)$ and on $Z(p^n)$ and it can be applied in the pseudo-random generators, cryptography, spread spectrum communications and so on.

The recent discovery of a physical device behaving as a memristor has driven a lot of attention to memristive systems, which are likely to play a relevant role in electronics in the near future, especially at the nanometer scale. The derivation of explicit ODE models for these systems is important because it opens a way for the study of the dynamics of general memristive circuits, including e.g. stability aspects, oscillations, bifurcations or chaotic phenomena. We tackle this problem as a reduction of implicit ODE (differential-algebraic) models, and show how tree-based approaches can be adapted in order to accommodate memristors. Specifically, we prove that the derivation of a tree-based explicit ODE model is feasible for strictly passive memristive systems under broad coupling effects and without a priori current/voltage control assumptions on tree/cotree elements. Our framework applies in particular to topologically degenerate circuits and accommodates a wide class of controlled sources. We also discuss a quasilinear reduction of nonpassive problems, which do not admit an explicit ODE description in the presence of singularities; some related bifurcations are addressed in this context.

An iterative compatible cell mapping (CCM) method with the digraph theory is presented in this paper to compute the global invariant manifolds of dynamical systems with high precision and high efficiency. The accurate attractors and saddles can be simultaneously obtained. The simple cell mapping (SCM) method is first used to obtain the periodic solutions. The results obtained by the generalized cell mapping (GCM) method are treated as a database. The SCM and GCM are compatible in the sense that the SCM is a subset of the GCM. The depth-first search algorithm is utilized to find the coarse coverings of global stable and unstable manifolds based on this database. The digraph GCM method is used if the saddle-like periodic solutions cannot be obtained with the SCM method. By taking this coarse covering as a new cell state space, an efficient iterative procedure of the CCM method is proposed by combining sort, search and digraph algorithms. To demonstrate the effectiveness of the proposed method, the classical Hénon map with periodic or chaotic saddles is studied in far more depth than reported in the literature. Not only the global invariant manifolds, but also the attractors and saddles are computed. The computational efficiency can be improved by up to 200 times compared to the traditional GCM method.

We present emergent dynamics of continuous and discrete thermomechanical Cucker–Smale (TCS) models equipped with temperature as an extra observable on general digraph. In previous literature, the emergent behaviors of the TCS models were mainly studied on a complete graph, or symmetric connected graphs. Under this symmetric setting, the total momentum is a conserved quantity. This determines the asymptotic velocity and temperature a priori using the initial data only. Moreover, this conservation law plays a crucial role in the flocking analysis based on the elementary ${\ell }_2$ energy estimates. In this paper, we consider a more general connection topology which is registered by a general digraph, and the weights between particles are given to be inversely proportional to the metric distance between them. Due to this possible symmetry breaking in communication, the total momentum is not a conserved quantity, and this lack of conservation law makes the asymptotic velocity and temperature depend on the whole history of solutions. To circumvent this lack of conservation laws, we instead employ some tools from matrix theory on the scrambling matrices and some detailed analysis on the state-transition matrices. We present two sufficient frameworks for the emergence of mono-cluster flockings on a digraph for the continuous and discrete models. Our sufficient frameworks are given in terms of system parameters and initial data.

Given a finite-dimensional Leibniz algebra with certain basis, we show how to associate such algebra with a combinatorial structure of dimension 2. In some particular cases, this structure can be reduced to a digraph or a pseudodigraph. In this paper, we study some theoretical properties about this association and we determine the type of Leibniz algebra associated to each of them.

The Kautz digraphs K(d, ℓ) are a well-known family of dense digraphs, widely studied as a good model for interconnection networks. Closely related to these, the cyclic Kautz digraphs CK(d, ℓ) were recently introduced by Böhmová, Huemer and the author, and some of its distance-related parameters were fixed. In this paper we propose a new approach to the cyclic Kautz digraphs by introducing the family of the subKautz digraphs sK(d, ℓ), from where the cyclic Kautz digraphs can be obtained as line digraphs. This allows us to give exact formulas for the distance between any two vertices of both sK(d, ℓ) and CK(d, ℓ). Moreover, we compute the diameter and the semigirth of both families, also providing efficient routing algorithms to find the shortest path between any pair of vertices. Using these parameters, we also prove that sK(d, ℓ) and CK(d, ℓ) are maximally vertex-connected and super-edge-connected. Whereas K(d, ℓ) are optimal with respect to the diameter, we show that sK(d, ℓ) and CK(d, ℓ) are optimal with respect to the mean distance, whose exact values are given for both families when ℓ = 3. Finally, we provide a lower bound on the girth of CK(d, ℓ) and sK(d, ℓ).

Restricted arc-connectivity is a more refined network reliability index than arc-connectivity. An arc subset $S$ of a strong digraph $D$ is a restricted arc-cut of $D$ if $D-S$ has a non-trivial strong component $D_1$ such that $D-V(D_1)$ contains an arc. The restricted arc-connectivity is the minimum cardinality over all restricted arc-cuts of $D$. A strong digraph is super-${\lambda }^{\prime }$ if its restricted arc-connectivity is maximal and the number of its minimum restricted arc-cuts is minimal. In this paper, we present some neighborhood conditions for a digraph to be super-${\lambda }^{\prime }$.

A ring R is said to be right serial, if it is a direct sum of right ideals which are uniserial. A ring that is right serial need not be left serial. Right artinian, right serial ring naturally arise in the study of artinian rings satisfying certain conditions. For example, if an artinian ring R is such that all finitely generated indecomposable right R-modules are uniform or all finitely generated indecomposable left R-modules are local, then R is right serial. Such rings have been studied by many authors including Ivanov, Singh and Bleehed, and Tachikawa. In this paper, a universal construction of a class of indecomposable, non-local, basic, right artinian, right serial rings is given. The construction depends on a right artinian, right serial ring generating system X, which gives rise to a tensor ring T(L). It is proved that any basic right artinian, right serial ring is a homomorphic image of one such T(L).

This paper shows that, for any positive integer $s$, there exist $s$-arc-transitive digraphs which have non-isomorphic in-local action and out-local action.

The aim of this paper is to use the graphical properties of a group mapping to study the algebraic properties of its centralizers. Equivalent conditions for the simplicity of the centralizer nearring of a given group mapping are given. Examples are provided to demonstrate and delimit our results.

Let H be an abelian group written additively and k be a positive integer. Let G(H, k) denote the digraph whose set of vertices is just H, and there exists a directed edge from a vertex a to a vertex b if b = ka. In this paper we give a necessary and sufficient condition for G(H, k₁) ≃ G(H, k₂). We also discuss the problem when G(H₁, k) is isomorphic to G(H₂, k) for a given k. Moreover, we give an explicit formula of G(H, k) when H is a p-group and gcd(p, k)=1.

We first study the spectrum of Hermitian adjacency matrix (H-spectrum) of Cayley digraphs X(D_2n, S) on dihedral group D_2n with |S| = 3. Then we show that all Cayley digraphs X(D_2p, S) with |S| = 3 and p odd prime are Cay-DS, namely, for any Cayley digraph X(D_2p, T), X(D_2p, T) and X(D_2p, S) having the same H-spectrum implies that they are isomorphic.

In this paper, new forms of nano topological spaces through a neighborhood system of vertices for a digraph will be presented and studied. We apply the connection between digraph theory and nano topological spaces in the human heart as an example in real life. We have a blood flow system in the human heart with respect to oxygenated and deoxygenated blood circulation. Our study will be definitely helpful to develop a tool in solving the blood flow system in the human heart. Finally, we have succeeded in improving Proposition 1.6 in [7] and Proposition 4.4.1 in [11].

Let $D=(V,A)$ be a finite and simple digraph. A $k$-rainbow dominating function ($k$RDF) of a digraph $D$ is a function $f$ from the vertex set $V$ to the set of all subsets of the set $\{1,2,\dots ,k\}$ such that for any vertex $v\in V$ with $f(v)=\varnothing$ the condition ${\bigcup }_{u\in N^{-}(v)}f(u)=\{1,2,\dots ,k\}$ is fulfilled, where $N^{-}(v)$ is the set of in-neighbors of $v$. The weight of a $k$RDF $f$ is the value $\omega (f)={\sum }_{v\in V}|f(v)|$. The $k$-rainbow domination number of a digraph $D$, denoted by ${\gamma }_{rk}(D)$, is the minimum weight of a $k$RDF of $D$. The $k$-rainbow reinforcement number$r_{rk}(D)$ of a digraph $D$ is the minimum number of arcs that must be added to $D$ in order to decrease the $k$-rainbow domination number. In this paper, we initiate the study of $k$-rainbow reinforcement number in digraphs and we present some sharp bounds for $r_{rk}(D)$. In particular, we determine the $2$-rainbow reinforcement number of some classes of digraphs.

We consider the skew Laplacian matrix of a digraph $\overrightarrow{G^{}}$ obtained by giving an arbitrary direction to the edges of a graph $G$ having $n$ vertices and $m$ edges. With ${\nu }_1,{\nu }_2,\dots ,{\nu }_n$ to be the skew Laplacian eigenvalues of $\overrightarrow{G^{}}$, the skew Laplacian energy $\mathrm{\text{SLE}}(\overrightarrow{G^{}})$ of $\overrightarrow{G^{}}$ is defined as $\mathrm{\text{SLE}}(\overrightarrow{G^{}})={\sum }_{i=1}^n\left|{\nu }_i\right|$. In this paper, we analyze the effect of changing the orientation of an induced subdigraph on the skew Laplacian spectrum. We obtain bounds for the skew Laplacian energy $\mathrm{\text{SLE}}(\overrightarrow{G^{}})$ in terms of various parameters associated with the digraph $\overrightarrow{G^{}}$ and the underlying graph $G$ and we characterize the extremal digraphs attaining these bounds. We also show these bounds improve some known bounds for some families of digraphs. Further, we show the existence of some families of skew Laplacian equienergetic digraphs.

Let D be a simple digraph with arc set A(D), and let j and k be two positive integers. A function f : A(D) → {-1, 1} is said to be a signed star j-dominating function (SSjDF) on D if ∑_{a ∈ A(v)} f(a) ≥ j for every vertex v of D, where A(v) is the set of arcs with head v. A set {f₁, f₂, …, f_d} of distinct SSjDFs on D with the property that for each a ∈ A(D), is called a signed star (j, k)-dominating (SS(j, k)D) family (of functions) on D. The maximum number of functions in a SS(j, k)D family on D is the signed star (j, k)-domatic number of D, denoted by . In this paper, we study properties of the signed star (j, k)-domatic number of a digraph D. In particular, we determine bounds on . Some of our results extend these ones given by Sheikholeslami and Volkmann [Signed star k-domination and k-domatic number of digraphs, submitted] for the signed (j, 1)-domatic number.

A real $n\times n$ matrix is a $Q$-matrix if for $k=1,\dots ,n$ the sum of all $k\times k$ principal minors is positive. A digraph $D$ is said to have positive $Q$-completion if every partial positive $Q$-matrix specifying $D$ can be completed to a positive $Q$-matrix. In this paper, necessary conditions for a digraph to have positive $Q$-completion are obtained and sufficient conditions for a digraph to have positive $Q$-completion are provided. The digraphs of order at most 4 that include all loops and have positive $Q$-completion are characterized. Tournaments whose complements have positive $Q$-completion are singled out. Further, some comparisons between the $Q$-matrix and positive $Q$-matrix completion problems have been made.

A subset $U\subset V(D)$ is acyclic if it induces an acyclic subdigraph of a digraph $D$ and the dichromatic number ${\chi }_d(D)$ of $D$ is defined to be the minimum integer $n$ such that $V(D)$ can be partitioned into $n$ acyclic subsets. In this paper, we obtain lower and upper bounds for the dichromatic number of a generalized lexicographic product and the dichromatic number of a generalized corona of digraphs in terms of dichromatic numbers of those digraphs.