Narrow Results

We introduce L-drawings, a novel paradigm for representing directed graphs aiming at combining the readability features of orthogonal drawings with the expressive power of adjacency matrix representations. In an L-drawing, vertices have exclusive $x$- and $y$-coordinates and edges consist of two segments, one exiting the source vertically and one entering the destination horizontally.

We study the problem of computing L-drawings using minimum ink. We prove its NP-hardness and provide a heuristic based on a polynomial-time algorithm that adds a vertex to a drawing using the minimum additional ink. We performed an experimental analysis of the heuristic which confirms its effectiveness.

For a directed graph G, we generalize the Catalan numbers by using the canonical generating partial isometries of the Cuntz–Krieger algebra for the transition matrix A^G of the directed edges of G. The generalized Catalan numbers enumerate the number of Dyck paths for the graph G. Its generating functions will be studied.

The standardization of the Semantic Web has reached as far as ontologies and ontology languages. However, in order for the full potential of the Semantic Web to be achieved, the ability of reasoning over the available information is also essential. Rules can assist in this affair and various logics have been proposed for the Semantic Web domain. One of them is defeasible reasoning that deals with incomplete and conflicting information. However, despite its solid mathematical notation, it may be confusing to end users. To confront this downside, we proposed a representation schema for defeasible logic rule bases, which is based on directed graphs that feature distinct node and connection types. This paper presents DR-VisMo, a defeasible logic rule base editor and visualization system that implements this representation approach. The system also features a stratification algorithm for visualizing rule bases that deals with decisions, regarding the arrangement of the various elements in the graph. DR-VisMo is implemented as part of VDR-DEVICE, an environment for modeling and deploying defeasible logic rule bases on top of RDF ontologies.

Call two pairs (M,N) and (M′,N′) of m × n matrices over a field K, simultaneously K-equivalent if there exist square invertible matrices S,T over K, with M′ = SMT and N′ = SNT. Kronecker [2] has given a complete set of invariants for simultaneous equivalence of pairs of matrices.

Associate in the natural way to a finite directed graph Γ, with v vertices and e edges, an ordered pair (M,N) of e × v matrices of zeros and ones. It is natural to try to compute the Kronecker invariants of such a pair (M,N), particularly since they clearly furnish isomorphism-invariants of Γ. Let us call two graphs "linearly equivalent" when their two corresponding pairs are simultaneously equivalent.

There have existed, since 1890, highly effective algorithms for computing the Kronecker invariants of pairs of matrices of the same size over a given field [1,2,5,6] and in particular for those arising in the manner just described from finite directed graphs.

The purpose of the present paper, is to compute directly these Kronecker invariants of finite directed graphs, from elementary combinatorial properties of the graphs. A pleasant surprise is that these new invariants are purely rational — indeed, integral, in the sense that the computation needed to decide if two directed graphs are linearly equivalent only involves counting vertices in various finite graphs constructed from each of the given graphs — and does not involve finding the irreducible factorization of a polynomial over K (in apparent contrast both to the familiar invariant-computations of graphs furnished by the eigenvalues of the connection matrix, and to the isomorphism problem for general pairs of matrices).

Here I show that digraphs (directed graphs) are inherent both in the relationships between elements of biological systems and in transitions between different system states. Properties of digraphs therefore underlie many biological phenomena, especially criticality and phase changes. Examples include epidemics, development, vegetation change and evolution. An important source of variety in biological systems is the extreme variability in digraph patterns that occurs when levels of connectivity are critical. Many biological processes, including evolution, appear to exploit this variety via a mechanism in which the connectivity of a system flips back and forth across the critical level.

This paper presents some results concerning the qualitative behaviour of possibilistic networks. The behaviour of singly connected networks is analysed, providing the foundations for qualitative reasoning about changes in possibility values in both predictive and evidential directions. The problems inherent in handling multiply connected networks are also discussed, and a possible solution is proposed. The behaviour of qualitative possibilistic networks is compared to qualitative probabilistic networks, and an example of the kind of reasoning that is permitted by the use of these networks is provided.

Let $F_q$ be a finite field with $q$ elements, $n\ge 2$ a positive integer, $T(n,q)$ the semigroup of all $n\times n$ upper triangular matrices over $F_q$ under matrix multiplication, $T^{\ast }(n,q)$ the group of all invertible matrices in $T(n,q)$, $P{T}^{\ast }(n,q)$ the quotient group of $T^{\ast }(n,q)$ by its center.

The one-divisor graph of $T(n,q)$, written as ${𝕋}_n(q)$, is defined to be a directed graph with $T(n,q)$ as vertex set, and there is a directed edge from $A\in T(n,q)$ to $B\in T(n,q)$ if and only if $r(AB)=1$, i.e. $A$ and $B$ are, respectively, a left divisor and a right divisor of a rank one matrix in $T(n,q)$. The definition of ${𝕋}_n(q)$ is motivated by the definition of zero-divisor graph ${𝒯}$ of $T(n,q)$, which has vertex set of all nonzero zero-divisors in $T(n,q)$ and there is a directed edge from a vertex $A$ to a vertex $B$ if and only if $AB=0$, i.e. $r(AB)=0$.

The automorphism group of zero-divisor graph ${𝒯}$ of $T(n,q)$ was recently determined by Wang [A note on automorphisms of the zero-divisor graph of upper triangular matrices, Lin. Alg. Appl.465 (2015) 214–220.]. In this paper, we characterize the automorphism group of one-divisor graph ${𝕋}_n(q)$ of $T(n,q)$, proving that $\mathrm{\text{Aut}}({𝕋}_n(q))\simeq P{T}^{\ast }(n,q)\times \mathrm{\text{Aut}}(F_q)\times H$, where $\mathrm{\text{Aut}}(F_q)$ is the automorphism group of field $F_q$, $H$ is a direct product of some symmetric groups. Besides, an application of automorphisms of ${𝕋}_n(q)$ is given in this paper.

Via a detailed case study of mesial temporal lobe epilepsy, we show that a method of determining the direction of information flow among signals is able to provide focal localization via the simultaneous analysis of multiple EEG channels. This determination is accomplished by representing information flow direction via directed graphs, where focal electrodes are associated with high observed rates of pertinence to strongly connected subgraphs. Further clinical support to this finding is provided by results for an additional 9 cases of focal epilepsy cases. The graph theoretical approach is a tool for describing and analyzing the effective connectivity dynamics behind epileptic seizures and may provide a common language for studying other complex dynamic relationships between neural structures.

Thanks to the tremendous progress in data, computing power and algorithms, AI-based material mining and design have gained much attention. However, building high-performance AI models requires efficient material structure representation. In this work, we propose a structural characterization method based on the neighborhood path complex for the first time. Specifically, we use persistent neighborhood path homology to obtain the structural features by introducing a filtration. This approach preserves more elemental information, as well as the corresponding physicochemical information, through the directed edges of the neighborhood digraph. To validate our model, we perform cross-validation with the carborane structures. The Pearson coefficient for stability prediction is as high as 0.903, which is a 15.5% improvement compared to the traditional persistent homology method. In addition, we constructed a prediction model based on the neighborhood path complex, and the Pearson coefficients for the prediction of carboranes’ HOMO, LUMO, and HOMO–LUMO gaps were 0.915, 0.946, and 0.941, respectively. The results show that our proposed method can effectively extract structural information and achieve accurate material property prediction.

In the following paper, we present a collection of known and new formulations for the Steiner problem in undirected and directed graphs.