Explore the vast range of titles available.

A digraph group is a group defined by non-empty presentation with the property that each relator is of the form $R(x, y)$ , where x and y are distinct generators and $R(\\cdot , \\cdot )$ is determined by some fixed cyclically reduced word $R(a, b)$ that involves both a and b. Associated with each such presentation is a digraph whose vertices correspond to the generators and whose arcs correspond to the relators. In this article, we consider digraph groups for strong digraphs that are digon-free and triangle-free. We classify when the digraph group is finite and show that in these cases it is cyclic, giving its order. We apply this result to the Cayley digraph of the generalized quaternion group, to circulant digraphs, and to Cartesian and direct products of strong digraphs.

Chordal graphs are important in structural graph theory. Chordal digraphs are a digraph analogue of chordal graphs and have been a subject of active studies recently. Unlike chordal graphs, chordal digraphs lack many structural properties such as forbidden subdigraph or representation characterizations. In this paper we introduce the notion of semi-strict chordal digraphs which form a class strictly between chordal digraphs and chordal graphs. Semi-strict chordal digraphs have rich structural properties. We characterize semi-strict chordal digraphs in terms of knotting graphs, a notion analogous to the one introduced by Gallai for the study of comparability graphs. We also give forbidden subdigraph characterizations of semi-strict chordal digraphs within the classes of locally semicomplete digraphs and weakly quasi-transitive digraphs.

Abstract-A digraph that has arcs of two colours is called a two-coloured digraph. In this case, the colours used are red and black. Let d and k be non-negative integers, where d represents the number of red arcs and k represents the number of black arcs. A (d, k)-walk on the two-coloured digraph is defined as a walk with d red arcs and k black arcs. The smallest integer sum of d and k such that there is a (d, k)-walk from vertex y to vertex z is called the exponent number of two-coloured digraph, whereas the smallest integer sum of d and k such that there is (d, k)-walk from each vertex to vertex vx is called the inner local exponent of a vertex vx. This article discusses the inner local exponent of a two-cycle non-Hamiltonian twocoloured digraph with cycle lengths n and 3n +1. This digraph has exactly four red arcs. The four red arcs are combined consecutively or alternately when there is one allied vertex.

The primary objective of this paper, is to introduce eight types of topologies on a finite digraphs and state the implication between these topologies. Also we used supra open digraphs to introduce a new types for approximation rough digraphs.

Endowing the set of functional graphs (FGs) with the sum (disjoint union of graphs) and product (standard direct product on graphs) operations induces on FGs a structure of a commutative semiring R. The operations on R can be naturally extended to the set of univariate polynomials R[X] over R. This paper provides a polynomial time algorithm for deciding if equations of the type AX=B have solutions when A is just a single cycle and B a set of cycles of identical size. We also prove a similar complexity result for some variants of the previous equation. Final version accepted by DMTCS; added a linefeed before 'Clearly' in the before last page, as asked by the editor

A new domination parameter in a fuzzy digraph is proposed to espouse a contribution in the domain of domination in a fuzzy graph and a directed graph. Let GD*=V,A be a directed simple graph, where V is a finite nonempty set and A=x,y:x,y∈V,x≠y. A fuzzy digraph GD=σD,μD is a pair of two functions σD:V→0,1 and μD:A→0,1, such that μDx,y≤σDx∧σDy, where x,y∈V. An edge μDx,y of a fuzzy digraph is called an effective edge if μDx,y=σDx∧σDy. Let x,y∈V. The vertex σDx dominates σDy in GD if μDx,y is an effective edge. Let S⊆V, u∈V and v∈S. A subset σDS⊆σD is a dominating set of GD if, for every σDu∈σD\\σDS, there exists σDv∈σDS, such that σDv dominates σDu. The minimum dominating set of a fuzzy digraph GD is called the domination number of a fuzzy digraph and is denoted by γGD. In this paper, the concept of domination in a fuzzy digraph is introduced, the domination number of a fuzzy digraph is characterized, and the domination number of a fuzzy dipath and a fuzzy dicycle is modeled.

A Cayley digraph Cay ( G , S ) of a group G with respect to a subset S of G is called a CI-digraph if for every Cayley digraph Cay ( G , T ) isomorphic to Cay ( G , S ) , there exists an α ∈ Aut ( G ) such that S α = T . For a positive integer m , G is said to have the m -DCI property if all Cayley digraphs of G with out-valency m are CI-digraphs. Li (European J Combin 18:655–665, 1997) gave a necessary condition for cyclic groups to have the m -DCI property, and in this paper, we find a necessary condition for dihedral groups to have the m -DCI property. Let D 2 n be the dihedral group of order 2 n , and assume that D 2 n has the m -DCI property for some 1 ≤ m ≤ n - 1 . It is shown that n is odd, and if further p + 1 ≤ m ≤ n - 1 for an odd prime divisor p of n , then p 2 ∤ n . Furthermore, if n is a power of a prime q , then D 2 n has the m -DCI property if and only if either n = q , or q is odd and 1 ≤ m ≤ q .

Y. Manoussakis (J. Graph Theory 16, 1992, 51-59) proposed the following conjecture. ıt Let$D$be a 2-strongly connected digraph of order$n$such that for all distinct pairs of non-adjacent vertices$x$ ,$y$and$w$ ,$z$ , we have$d(x)+d(y)+d(w)+d(z)\\geq 4n-3$ . Then$D$is Hamiltonian. In this paper, we confirm this conjecture. Moreover, we prove that if a digraph$D$satisfies the conditions of this conjecture and has a pair of non-adjacent vertices$\\{x,y\\}$such that$d(x)+d(y)\\leq 2n-4$ , then$D$contains cycles of all lengths$3, 4, \\ldots , n$ . Comment: 24 pages

In this paper, we define and characterize the embedding of edges and higher-order entities in directed graphs (digraphs) and relate these embeddings to those of nodes. Our edge-centric approach consists of the following: (a) Embedding line digraphs (or their iterated versions); (b) Exploiting the rank properties of these embeddings to show that edge/path similarity can be posed as a linear combination of node similarities; (c) Solving scalability issues through digraph sparsification; (d) Evaluating the performance of these embeddings for classification and clustering. We commence by identifying the motive behind the need for edge-centric approaches. Then we proceed to introduce all the elements of the approach, and finally, we validate it. Our edge-centric embedding entails a top-down mining of links, instead of inferring them from the similarities of node embeddings. This analysis is key to discovering inter-subgraph links that hold the whole graph connected, i.e., central edges. Using directed graphs (digraphs) allows us to cluster edge-like hubs and authorities. In addition, since directed edges inherit their labels from destination (origin) nodes, their embedding provides a proxy representation for node classification and clustering as well. This representation is obtained by embedding the line digraph of the original one. The line digraph provides nice formal properties with respect to the original graph; in particular, it produces more entropic latent spaces. With these properties at hand, we can relate edge embeddings to node embeddings. The main contribution of this paper is to set and prove the linearity theorem, which poses each element of the transition matrix for an edge embedding as a linear combination of the elements of the transition matrix for the node embedding. As a result, the rank preservation property explains why embedding the line digraph and using the labels of the destination nodes provides better classification and clustering performances than embedding the nodes of the original graph. In other words, we do not only facilitate edge mining but enforce node classification and clustering. However, computing the line digraph is challenging, and a sparsification strategy is implemented for the sake of scalability. Our experimental results show that the line digraph representation of the sparsified input graph is quite stable as we increase the sparsification level, and also that it outperforms the original (node-centric) representation. For the sake of simplicity, our theorem relies on node2vec-like (factorization) embeddings. However, we also include several experiments showing how line digraphs may improve the performance of Graph Neural Networks (GNNs), also following the principle of maximum entropy.