We determine the forbidden induced subgraphs for the intersection of the classes of chordal bipartite graphs and line graphs of acyclic directed graphs. This is a first step towards finding the forbidden induced subgraphs for the class of line graphs of directed graphs.

The topological ordering algorithm sorts nodes of a directed graph such that the order of the tail of each arc is lower than the order of its head. In this paper, we introduce the notion of covering between nodes of a directed graph. Then, we apply the topological orderingalgorithm on graphs containing the covering nodes. We show that there exists a cut set withforward arcs in these graphs and the order of the covering nodes is successive.

Given a T0-quasi-metric space we associate a directed graph with it and study some properties of the related directed graph. The present work complements and refines earlier work in the field in which the symmetry graph of a T0-quasi-metric space was studied.

Let G G be a simple graph with an orientation σ σ ‎, ‎which ‎assigns to each edge a direction so that G σ Gσ becomes a‎ ‎directed graph‎. ‎G G is said to be the underlying graph of the‎ ‎directed graph G σ Gσ ‎. ‎In this paper‎, ‎we define a weighted skew‎ ‎adjacency matrix with Randc weight‎, ‎the skew Randic matrix ‎‎R S (G σ) ‎‎RS(Gσ) ‎, ‎of G σ Gσ as the real skew symmetric matrix‎ ‎[(r s) ij] [(rs)ij] where (r s) ij =(d i d j) −12 (rs)ij=(didj)−12 and‎ ‎(r s) ji =‎−‎(d i d j) −12 (rs)ji=‎−‎(didj)−12 if v i →v j vi→vj is‎ ‎an arc of G σ Gσ ‎, ‎otherwise (r s) ij =(r s) ji =0 (rs)ij=(rs)ji=0 ‎. ‎We‎ ‎derive some properties of the skew Randic energy of an oriented‎ ‎graph‎. ‎Most properties are similar to those for the skew energy of‎ ‎oriented graphs‎. ‎But‎, ‎surprisingly‎, ‎the extremal oriented graphs‎ ‎with maximum or minimum skew Randic energy are completely‎ ‎different‎, ‎no longer being some kinds of oriented regular graphs‎.

Deza digraphs were introduced in 2003 by Zhang and Wang as directed graph version of Deza graphs, that also generalize the notion of directed strongly regular graphs. In this paper, we give several new constructions of Deza digraphs. Further, we introduce twin and Siamese twin (directed) Deza graphs and construct several examples. Finally, we study a variation of directed Deza graphs and provide a construction from finite fields.

Prediction of the future behavior of the stock market has always attracted researchers' attention as an important challenge in the field of machine learning. In recent years deep learning methods have been successfully applied in this domain to improve prediction performance. Previous studies have demonstrated that aggregating information from related stocks can improve the performance of prediction. However, the capacity of modeling the stocks relations as directed graphs and the power of sophisticated graph embedding techniques such as Graph Attention Networks have not been exploited so far for prediction in this domain. In this work, we introduce a framework called DeepNet that creates a directed graph representing how useful the data from each stock can be for improving the prediction accuracy of any other stocks. DeepNet then applies Graph Attention Network to extract a useful representation for each node by aggregating information from its neighbors, while the optimal amount of each neighbor's contribution is learned during the training phase. We have developed a novel Graph Attention Network model called DGAT that is able to define unequal contribution values for each pair of adjacent nodes in a directed graph. Our evaluation experiments on the Tehran Stock Exchange data show that the introduced prediction model outperforms the state-of-the-art baseline algorithms in terms of accuracy and MCC measures.

In this paper, we study the directed multicut and directed multimultiway cut problems. The input to the directed multi-multiway cut problem is a weighted directed graph G = (V, E) and k sets S1, S2, ..., Sk of vertices. The goal is to find a subset of edges of minimum total weight whose removal will disconnect all the connections between the vertices in each set Si , for 1 ≤ i ≤ k. A special case of this problem is the directed multicut problem whose input consists of a weighted directed graph G = (V, E) and a set of ordered pairs of vertices (s1, t1), ...,(sk, tk). The goal is to find a subset of edges of minimum total weight whose removal will make for any i, 1 ≤ i ≤ k, there is no directed path from si to ti . In this paper, we present two approximation algorithms for these problems. The so called region growing paradigm is modified and used for these two cut problems on directed graphs. using this paradigm, we give an approximation algorithm for each problem such that both algorithms have the approximation factor of O(k) the same as the previous works done on these problems. However, the previous works need to solve k linear programming, whereas our algorithms require only one linear programming. Therefore, our algorithms improve the running time of the previous algorithms.

In this paper, we introduce a new class of association rules (ARs) named “Multi-Relation Association Rules” which in contrast to primitive ARs (that are usually extracted from multi-relational databases), each rule item consists of one entity and several relations. These relations indicate indirect relationship between entities. Consider the following Multi-Relation Association Rule where the first item consists of three relations live in, nearby and humid: “Those who live in a place which is near by a city with humid climate type and also are younger than 20 → their health condition is good”. A new algorithm called MRAR is proposed to extract such rules from directed graphs with labeled edges which are constructed from RDBMSs or semantic web data. Also, the question “how to convert RDBMS data or semantic web data to a directed graph with labeled edges?” is answered. In order to evaluate the proposed algorithm, some experiments are performed on a sample dataset and also a real-world drug semantic web dataset. Obtained results confirm the ability of the proposed algorithm in mining Multi-Relation Association Rules.

Reaction automata direct graph (RADG) is a new technique that uses the automata direct graph method to represent a certain design for encryption and decryption. Jump states are available in the RADG design that enables the encipher to generate different ciphertexts each time from the same plaintext and wherein not a single ciphertext is related to a certain plaintext. This study created a matrix representation for RADG designs that allows the calculation of the number of cases ($F_{Q}$)mathematically possible for any design of the set $Q$. $F_{Q}$ is an important part of the function $mathrm{F}(mathrm{n}, mathrm{m}, lambda)$ that calculates the total number of cases of a certain design for the values $Q, R, sum, psi, J$ and $T$. This paper produces a mathematical equation to calculate $F_{Q}$.

In this article, first we introduce six types of power graphs related to a graph (or directed graph), with the help of set theory. Then we show that these newly defined power graphs are pairwise distinct by a few examples. Finally, we discuss the relation between Eulerian being the base graph and these six power graph types. Moreover, we express the relation between pairwise Eulerian of these power graphs.