Log in

Relevant bibliographies by topics / Digraph / Journal articles

To see the other types of publications on this topic, follow the link: Digraph.

Journal articles on the topic 'Digraph'

Author: Grafiati

Published: 4 June 2021

Last updated: 18 May 2024

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Digraph.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Luo, Mei Jin. "The Upper Bound of Primitive Exponent of a Class of Special Nonnegative Matrix Pairs." Advanced Materials Research 1061-1062 (December 2014): 1100–1103. http://dx.doi.org/10.4028/www.scientific.net/amr.1061-1062.1100.

Full text

Abstract:

There is a one-to-one relationship between nonnegative matrix pairs and two-colored digraph. With the knowledge of graph theory, by studying the associated directed digraph of a class of special nonnegative matrix pairs, that is a class of two-colored digraphs whose uncolored digraph have 3n-1 vertices and consists of one (3n-1)-cycle and one n-cycle are considered. The exponent and characteristic of extreme two-colored digraphs are given.

APA, Harvard, Vancouver, ISO, and other styles

2

RUAN, LU, SHITOU HAN, DEYING LI, HUNG Q. NGO, and SCOTT C. H. HUANG. "TRANSMISSION FAULT-TOLERANCE OF ITERATED LINE DIGRAPHS." Journal of Interconnection Networks 05, no. 04 (December 2004): 475–87. http://dx.doi.org/10.1142/s021926590400126x.

Full text

Abstract:

The main result of this paper states that, if every cyclic modification of a d-regular digraph has super line-connectivity d, then the line digraph also has super line-connectivity d. Since many well-known interconnection network topologies, such as the Kautz digraphs, the de Bruijn digraphs, etc., can be constructed by iterating the line digraph construction, our result leads to several known and new connectivity results for these topologies, as shown later in the paper.

APA, Harvard, Vancouver, ISO, and other styles

3

FERRARA, MICHAEL, MICHAEL JACOBSON, and FLORIAN PFENDER. "Degree Conditions for H-Linked Digraphs." Combinatorics, Probability and Computing 22, no. 5 (August 8, 2013): 684–99. http://dx.doi.org/10.1017/s0963548313000278.

Full text

Abstract:

Given a (multi)digraph H, a digraph D is H-linked if every injective function ι:V(H) → V(D) can be extended to an H-subdivision. In this paper, we give sharp degree conditions that ensure a sufficiently large digraph D is H-linked for arbitrary H. The notion of an H-linked digraph extends the classes of m-linked, m-ordered and strongly m-connected digraphs.First, we give sharp minimum semi-degree conditions for H-linkedness, extending results of Kühn and Osthus on m-linked and m-ordered digraphs. It is known that the minimum degree threshold for an undirected graph to be H-linked depends on a partition of the (undirected) graph H into three parts. Here, we show that the corresponding semi-degree threshold for H-linked digraphs depends on a partition of H into as many as nine parts.We also determine sharp Ore–Woodall-type degree-sum conditions ensuring that a digraph D is H-linked for general H. As a corollary, we obtain (previously undetermined) sharp degree-sum conditions for m-linked and m-ordered digraphs.

APA, Harvard, Vancouver, ISO, and other styles

4

Luo, Mei Jin. "The Primitive Exponent of a Class of Special Nonnegative Matrix Pairs." Advanced Materials Research 915-916 (April 2014): 1296–99. http://dx.doi.org/10.4028/www.scientific.net/amr.915-916.1296.

Full text

Abstract:

There is a one-to-one relationship between nonnegative matrix pairs and two-colored digraph, so the problem of matrices can be changed into that of graphics to be solved. With the knowledge of graph theory, by studying the associated directed digraph of a class of special nonnegative matrix pairs, that is a class of two-colored digraphs whose uncolored digraph have vertices and consists of one-cycle and one-cycle are considered. The exponent and characteristic of extreme two-colored digraphs are given.

APA, Harvard, Vancouver, ISO, and other styles

5

Yang, Xiuliang, and Haobo Yang. "ISOMORPHISMS OF TRANSFORMATION SEMIGROUPS ASSOCIATED WITH SIMPLE DIGRAPHS." Asian-European Journal of Mathematics 02, no. 04 (December 2009): 727–37. http://dx.doi.org/10.1142/s1793557109000601.

Full text

Abstract:

For each simple digraph D, we introduce its associated semigroup S(D) and its widened digraph W(D). We show that, for any two finite simple digraphs D1 and D2, S(D1) and S(D2) are isomorphic as semigroups if and only if W(D1) and W(D2) are isomorphic as digraphs.

APA, Harvard, Vancouver, ISO, and other styles

6

Elmali, Ceren Sultan, Tamer Uğur, and Tuǧçe Kunduraci. "On New Knot Tables." ITM Web of Conferences 22 (2018): 01019. http://dx.doi.org/10.1051/itmconf/20182201019.

Full text

Abstract:

The quasi-pseudo metrics on the vertices of a digraph induces a unique bitopology. In this work, we obtained that a bitopology is associated with any knot km, where k is crossing points of knot and m = 1,2 by using quasi-pseudo metrics on the vertices of a digraph which is called knot digraph by us, when we consider relation between the knot and its graph (knot digraph notation). Also some topological properties of bitopology obtained by using quasipseudo metric and associated with the knot digraphs are investigated.

APA, Harvard, Vancouver, ISO, and other styles

7

Yang, Xiuwen, Xiaogang Liu, and Ligong Wang. "On the sum of the k largest absolute values of Laplacian eigenvalues of digraphs." Electronic Journal of Linear Algebra 39 (July 20, 2023): 409–22. http://dx.doi.org/10.13001/ela.2023.7503.

Full text

Abstract:

Let $L(G)$ be the Laplacian matrix of a digraph $G$ and $S_k(G)$ be the sum of the $k$ largest absolute values of Laplacian eigenvalues of $G$. Let $C_n^+$ be a digraph with $n+1$ vertices obtained from the directed cycle $C_n$ by attaching a pendant arc whose tail is on $C_n$. A digraph is $\mathbb{C}_n^+$-free if it contains no $C_{\ell}^+$ as a subdigraph for any $2\leq \ell \leq n-1$. In this paper, we present lower bounds of $S_n(G)$ of digraphs of order $n$. We provide the exact values of $S_k(G)$ of directed cycles and $\mathbb{C}_n^+$-free unicyclic digraphs. Moreover, we obtain upper bounds of $S_k(G)$ of $\mathbb{C}_n^+$-free digraphs which have vertex-disjoint directed cycles.

APA, Harvard, Vancouver, ISO, and other styles

8

Smerchinskaya, Svetlana O., and Nina P. Yashina. "Preference levels for clusters of alternatives." International Journal of Modeling, Simulation, and Scientific Computing 10, no. 04 (August 2019): 1950019. http://dx.doi.org/10.1142/s1793962319500193.

Full text

Abstract:

In the decision-making tasks for ranking the alternatives and choosing the best ones, procedures on the digraphs are often used. A digraph of the aggregated relation on a set of alternatives for information of experts or criteria is preconstructed. If the digraph does not contain any cycles, then the Demukron algorithm for partitioning the digraph into levels can be used to order the alternatives by preference. This algorithm cannot be applied if there are clusters consisting of equivalent alternatives. In the paper the algorithm for partitioning an arbitrary digraph of into preference levels is proposed. In contrast to the standard procedure, the digraph of the aggregated relation admits the presence of cycles, and, consequently, of equivalent vertexes-alternatives. The vertexes in any cycle of digraph belong to one level of preference.

APA, Harvard, Vancouver, ISO, and other styles

9

Alomari, Omar, Mohammad Abudayah, and Torsten Sander. "The non-negative spectrum of a digraph." Open Mathematics 18, no. 1 (February 19, 2020): 22–35. http://dx.doi.org/10.1515/math-2020-0005.

Full text

Abstract:

Abstract Given the adjacency matrix A of a digraph, the eigenvalues of the matrix AAT constitute the so-called non-negative spectrum of this digraph. We investigate the relation between the structure of digraphs and their non-negative spectra and associated eigenvectors. In particular, it turns out that the non-negative spectrum of a digraph can be derived from the traditional (adjacency) spectrum of certain undirected bipartite graphs.

APA, Harvard, Vancouver, ISO, and other styles

10

Shi, Mei, Weihao Xia, Mingyue Xiao, and Jihui Wang. "The majority coloring of the join and Cartesian product of some digraph." MATEC Web of Conferences 355 (2022): 02004. http://dx.doi.org/10.1051/matecconf/202235502004.

Full text

Abstract:

A majority coloring of a digraph is a vertex coloring such that for every vertex, the number of vertices with the same color in the out-neighborhood does not exceed half of its out-degree. Kreutzer, Oum, Seymour and van der Zyper proved that every digraph is majority 4-colorable and conjecture that every digraph has a majority 3-coloring. This paper mainly studies the majority coloring of the joint and Cartesian product of some special digraphs and proved the conjecture is true for the join graph and the Cartesian product. According to the influence of the number of vertices in digraph, we prove the majority coloring of the joint and Cartesian product of some digraph.

APA, Harvard, Vancouver, ISO, and other styles

11

Luo, Mei Jin. "The Exponent Set of a Class of Two-Colored Digraphs with One Common Vertex." Advanced Materials Research 774-776 (September 2013): 1823–26. http://dx.doi.org/10.4028/www.scientific.net/amr.774-776.1823.

Full text

Abstract:

A two-colored directed digraph D is primitive if and only if there exist nonnegative integers h and k with h+k>0 such that for each pair (i,j) of vertices there is a (h,k)-walk in D from i to j. The exponent of the primitive two-colored digraph D is defined to be the smallest value of h+k over all suchand . With the knowledge of graph theory, a class of two-colored digraphs with two cycles whose uncolored digraph has 3n vertices and consists of one (2n+1)-cycle and one n-cycle is considered.The exponent bound, exponent set and characteristic of extral two-colored digraphs are given.

APA, Harvard, Vancouver, ISO, and other styles

12

Božović, Dragana, and Iztok Peterin. "Efficient Open Domination in Digraph Products." Mathematics 8, no. 4 (April 2, 2020): 496. http://dx.doi.org/10.3390/math8040496.

Full text

Abstract:

A digraph D is an efficient open domination digraph if there exists a subset S of V ( D ) for which the open out-neighborhoods centered in the vertices of S form a partition of V ( D ) . In this work we deal with the efficient open domination digraphs among four standard products of digraphs. We present a method for constructing the efficient open domination Cartesian product of digraphs with one fixed factor. In particular, we characterize those for which the first factor has an underlying graph that is a path, a cycle or a star. We also characterize the efficient open domination strong product of digraphs that have factors whose underlying graphs are uni-cyclic graphs. The full characterizations of the efficient open domination direct and lexicographic product of digraphs are also given.

APA, Harvard, Vancouver, ISO, and other styles

13

UĞUR, Tamer, Ceren Sultan ELMALI, and Ferit YALAZ. "The Reverse Operation Of Knot Digraph Notation." ITM Web of Conferences 22 (2018): 01031. http://dx.doi.org/10.1051/itmconf/20182201031.

Full text

Abstract:

It is well known that bitopologies associated with knot digraphs is finded by using knot digraph notation. In this work, we have developed a method that we called reverse of knot digraph notation to find out which knot belongs to when a bitopology associated with the knot is given.

APA, Harvard, Vancouver, ISO, and other styles

14

Alsatami, Khalid A., Hong-Jian Lai, and Xindong Zhang. "Dicycle Cover of Hamiltonian Oriented Graphs." Journal of Discrete Mathematics 2016 (February 3, 2016): 1–5. http://dx.doi.org/10.1155/2016/7942192.

Full text

Abstract:

A dicycle cover of a digraph D is a family F of dicycles of D such that each arc of D lies in at least one dicycle in F. We investigate the problem of determining the upper bounds for the minimum number of dicycles which cover all arcs in a strong digraph. Best possible upper bounds of dicycle covers are obtained in a number of classes of digraphs including strong tournaments, Hamiltonian oriented graphs, Hamiltonian oriented complete bipartite graphs, and families of possibly non-Hamiltonian digraphs obtained from these digraphs via a sequence of 2-sum operations.

APA, Harvard, Vancouver, ISO, and other styles

15

Harutyunyan, Ararat, P. Mark Kayll, Bojan Mohar, and Liam Rafferty. "Uniquely D-colourable Digraphs with Large Girth." Canadian Journal of Mathematics 64, no. 6 (December 1, 2012): 1310–28. http://dx.doi.org/10.4153/cjm-2011-084-9.

Full text

Abstract:

Abstract Let C and D be digraphs. A mapping f : V(D) →V(C) is a C-colouring if for every arc uv of D, either f (u) f (v) is an arc of C or f (u) = f (v), and the preimage of every vertex of C induces an acyclic subdigraph in D. We say that D is C-colourable if it admits a C-colouring and that D is uniquely C-colourable if it is surjectively C-colourable and any two C-colourings of D differ by an automorphism of C. We prove that if a digraph D is not C-colourable, then there exist digraphs of arbitrarily large girth that are D-colourable but not C-colourable. Moreover, for every digraph D that is uniquely D-colourable, there exists a uniquely D-colourable digraph of arbitrarily large girth. In particular, this implies that for every rational number r ≥ 1, there are uniquely circularly r-colourable digraphs with arbitrarily large girth.

APA, Harvard, Vancouver, ISO, and other styles

16

Samadi, Babak, and Ismael G. Yero. "On the Packing Partitioning Problem on Directed Graphs." Mathematics 9, no. 23 (December 6, 2021): 3148. http://dx.doi.org/10.3390/math9233148.

Full text

Abstract:

This work is aimed to continue studying the packing sets of digraphs via the perspective of partitioning the vertex set of a digraph into packing sets (which can be interpreted as a type of vertex coloring of digraphs) and focused on finding the minimum cardinality among all packing partitions for a given digraph D, called the packing partition number of D. Some lower and upper bounds on this parameter are proven, and their exact values for directed trees are given in this paper. In the case of directed trees, the proof results in a polynomial-time algorithm for finding a packing partition of minimum cardinality. We also consider this parameter in digraph products. In particular, a complete solution to this case is presented when dealing with the rooted products.

APA, Harvard, Vancouver, ISO, and other styles

17

Amjadi, Jafar, and Fatemeh Pourhosseini. "Signed double Roman domination numbers in digraphs." Annals of the University of Craiova - Mathematics and Computer Science Series 48, no. 1 (June 30, 2021): 194–205. http://dx.doi.org/10.52846/ami.v48i1.1305.

Full text

Abstract:

"Let $D=(V,A)$ be a finite simple digraph. A signed double Roman dominating function (SDRD-function) on the digraph $D$ is a function $f:V(D)\rightarrow\{-1,1,2, 3\}$ satisfying the following conditions: (i) $\sum_{x\in N^-[v]}f(x)\ge 1$ for each $v\in V(D)$, where $N^-[v]$ consist of $v$ and all in-neighbors of $v$, and (ii) if $f(v)=-1$, then the vertex $v$ must have at least two in-neighbors assigned 2 under $f$ or one in-neighbor assigned 3, while if $f(v)=1$, then the vertex $v$ must have at least one in-neighbor assigned 2 or 3. The weight of a SDRD-function $f$ is the value $\sum_{x\in V(D)}f(x)$. The signed double Roman domination number (SDRD-number) $\gamma_{sdR}(D)$ of a digraph $D$ is the minimum weight of a SDRD-function on $D$. In this paper we study the SDRD-number of digraphs, and we present lower and upper bounds for $\gamma_{sdR}(D)$ in terms of the order, maximum degree and chromatic number of a digraph. In addition, we determine the SDRD-number of some classes of digraphs."

APA, Harvard, Vancouver, ISO, and other styles

18

KUO, JYHMIN. "ON THE TWIN DOMINATION NUMBER IN GENERALIZED DE BRUIJN AND GENERALIZED KAUTZ DIGRAPHS." Discrete Mathematics, Algorithms and Applications 02, no. 02 (June 2010): 199–205. http://dx.doi.org/10.1142/s1793830910000577.

Full text

Abstract:

Let V and A denote the vertex and edge sets of a digraph G. A set T ⊆V is a twin dominating set of G if for every vertex v ∈ V - T, there exist u, w ∈ T (possibly u = w) such that arcs (u, v), (v, w) ∈ A. The twin domination number γ*(G) of G is the cardinality of a minimum twin dominating set of G. In this note, we investigate the twin domination numbers of generalized de Bruijn digraph and generalized Kautz digraph. The bounds of twin domination number of special generalized Kautz digraphs are given.

APA, Harvard, Vancouver, ISO, and other styles

19

Zhao, Jinxing, and Guixin Deng. "Digraph from power mapping on noncommutative groups." Journal of Algebra and Its Applications 19, no. 05 (May 3, 2019): 2050084. http://dx.doi.org/10.1142/s021949882050084x.

Full text

Abstract:

Let [Formula: see text] be a group and [Formula: see text] be a positive integer. The [Formula: see text]-power digraph [Formula: see text] is consisting of vertex set [Formula: see text] and there is a directed edge from [Formula: see text] to [Formula: see text] if and only if [Formula: see text]. We study the [Formula: see text]-power digraph on the semiproduct of cyclic groups. In particular, we obtain the distribution of indegree and cycles, and determine the structure of trees attached with vertices of power digraph. Finally, we establish a necessary and sufficient condition for isomorphism of digraphs [Formula: see text] and [Formula: see text].

APA, Harvard, Vancouver, ISO, and other styles

20

Honda, Keisuke. "Kana digraphs and morea." Written Language and Literacy 10, no. 1 (October 30, 2007): 65–82. http://dx.doi.org/10.1075/wll.10.1.05hon.

Full text

Abstract:

The Japanese kana script represents morae by assigning either graphs or digraphs. Kana digraphs are characteristic in that they each comprise two mora-bearing graphs and yet correspond to single morae. This paper develops a structural analysis of kana digraphs, in which the monomoraic value of every digraph is consistently derived from the bimoraic value of a two-graph string. It is argued that the derivational process involves two events, namely cancellation of moraicity in the first mora and amalgamation of all relevant segments into the resultant single mora. This accounts for the observed fact that each constituent of a kana digraph regularly corresponds to one portion of a single mora. The validity of the analysis is supported by evidence drawn from two orthographic phenomena, namely positioning of diacritics and use of a common constituent in digraphs denoting partially isomorphic morae.

APA, Harvard, Vancouver, ISO, and other styles

21

KANG, DONG YEAP. "Sparse Highly Connected Spanning Subgraphs in Dense Directed Graphs." Combinatorics, Probability and Computing 28, no. 3 (November 5, 2018): 423–64. http://dx.doi.org/10.1017/s0963548318000469.

Full text

Abstract:

Mader proved that every strongly k-connected n-vertex digraph contains a strongly k-connected spanning subgraph with at most 2kn - 2k2 edges, where equality holds for the complete bipartite digraph DKk,n-k. For dense strongly k-connected digraphs, this upper bound can be significantly improved. More precisely, we prove that every strongly k-connected n-vertex digraph D contains a strongly k-connected spanning subgraph with at most kn + 800k(k + Δ(D)) edges, where Δ(D) denotes the maximum degree of the complement of the underlying undirected graph of a digraph D. Here, the additional term 800k(k + Δ(D)) is tight up to multiplicative and additive constants. As a corollary, this implies that every strongly k-connected n-vertex semicomplete digraph contains a strongly k-connected spanning subgraph with at most kn + 800k2 edges, which is essentially optimal since 800k2 cannot be reduced to the number less than k(k - 1)/2.We also prove an analogous result for strongly k-arc-connected directed multigraphs. Both proofs yield polynomial-time algorithms.

APA, Harvard, Vancouver, ISO, and other styles

22

Sheikholeslami, Seyed Mahmoud, Nasrin Dehgardi, Lutz Volkmann, and Dirk Meierling. "The Roman bondage number of a digraph." Tamkang Journal of Mathematics 47, no. 4 (December 30, 2016): 421–31. http://dx.doi.org/10.5556/j.tkjm.47.2016.2100.

Full text

Abstract:

Let $D=(V,A)$ be a finite and simple digraph. A Roman dominating function on $D$ is a labeling $f:V (D)\rightarrow \{0, 1, 2\}$ such that every vertex with label 0 has an in-neighbor with label 2. The weight of an RDF $f$ is the value $\omega(f)=\sum_{v\in V}f (v)$. The minimum weight of a Roman dominating function on a digraph $D$ is called the Roman domination number, denoted by $\gamma_{R}(D)$. The Roman bondage number $b_{R}(D)$ of a digraph $D$ with maximum out-degree at least two is the minimum cardinality of all sets $A'\subseteq A$ for which $\gamma_{R}(D-A')>\gamma_R(D)$. In this paper, we initiate the study of the Roman bondage number of a digraph. We determine the Roman bondage number in several classes of digraphs and give some sharp bounds.

APA, Harvard, Vancouver, ISO, and other styles

23

Chen, Danmei. "Upper Bounds of the Generalized Competition Indices of Symmetric Primitive Digraphs with d Loops." Symmetry 15, no. 7 (July 2, 2023): 1348. http://dx.doi.org/10.3390/sym15071348.

Full text

Abstract:

A digraph (D) is symmetric if (u,v) is an arc of D and if (v,u) is also an arc of D. If a symmetric digraph is primitive and contains d loops, then it is said to be a symmetric primitive digraph with d loops. The m-competition index (generalized competition index) of a digraph is an extension of the exponent and the scrambling index. The m-competition index has been applied to memoryless communication systems in recent years. In this article, we assume that Sn(d) represents the set of all symmetric primitive digraphs of n vertices with d loops, where 1≤d≤n. We study the m-competition indices of Sn(d) and give their upper bounds, where 1≤m≤n. Furthermore, for any integer m satisfying 1≤m≤n, we find that the upper bounds of the m-competition indices of Sn(d) can be reached.

APA, Harvard, Vancouver, ISO, and other styles

24

Cary, Michael. "Vertices with the second neighborhood property in Eulerian digraphs." Opuscula Mathematica 39, no. 6 (2019): 765–72. http://dx.doi.org/10.7494/opmath.2019.39.6.765.

Full text

Abstract:

The Second Neighborhood Conjecture states that every simple digraph has a vertex whose second out-neighborhood is at least as large as its first out-neighborhood, i.e. a vertex with the Second Neighborhood Property. A cycle intersection graph of an even graph is a new graph whose vertices are the cycles in a cycle decomposition of the original graph and whose edges represent vertex intersections of the cycles. By using a digraph variant of this concept, we prove that Eulerian digraphs which admit a simple cycle intersection graph not only adhere to the Second Neighborhood Conjecture, but that local simplicity can, in some cases, also imply the existence of a Seymour vertex in the original digraph.

APA, Harvard, Vancouver, ISO, and other styles

25

Johnson, Peter D. "Unordered Love in infinite directed graphs." International Journal of Mathematics and Mathematical Sciences 15, no. 4 (1992): 753–56. http://dx.doi.org/10.1155/s0161171292000978.

Full text

Abstract:

A digraphD=(V,A)has the Unordered Love Property (ULP) if any two different vertices have a unique common outneighbor. If both(V,A)and(V,A−1)have the ULP, we say thatDhas the SDULP.A love-master inDis a vertexν0connected both ways to every other vertex, such thatD−ν0is a disjoint union of directed cycles.The following results, more or less well-known for finite digraphs, are proven here forDinfinite: (i) ifDis loopless and has the SDULP, then eitherDhas a love-master, orDis associable with a projective plane, obtainable by takingVas the set of points and the sets of outneighbors of vertices as the lines; (ii) every projective plane arises from a digraph with the SDULP, in this way.

APA, Harvard, Vancouver, ISO, and other styles

26

Khoeilar, R., and S. M. Sheikholeslami. "Rainbow reinforcement numbers in digraphs." Asian-European Journal of Mathematics 10, no. 01 (March 2017): 1750004. http://dx.doi.org/10.1142/s1793557117500048.

Full text

Abstract:

Let [Formula: see text] be a finite and simple digraph. A [Formula: see text]-rainbow dominating function ([Formula: see text]RDF) of a digraph [Formula: see text] is a function [Formula: see text] from the vertex set [Formula: see text] to the set of all subsets of the set [Formula: see text] such that for any vertex [Formula: see text] with [Formula: see text] the condition [Formula: see text] is fulfilled, where [Formula: see text] is the set of in-neighbors of [Formula: see text]. The weight of a [Formula: see text]RDF [Formula: see text] is the value [Formula: see text]. The [Formula: see text]-rainbow domination number of a digraph [Formula: see text], denoted by [Formula: see text], is the minimum weight of a [Formula: see text]RDF of [Formula: see text]. The [Formula: see text]-rainbow reinforcement number [Formula: see text] of a digraph [Formula: see text] is the minimum number of arcs that must be added to [Formula: see text] in order to decrease the [Formula: see text]-rainbow domination number. In this paper, we initiate the study of [Formula: see text]-rainbow reinforcement number in digraphs and we present some sharp bounds for [Formula: see text]. In particular, we determine the [Formula: see text]-rainbow reinforcement number of some classes of digraphs.

APA, Harvard, Vancouver, ISO, and other styles

27

Gärtner, Fabian, and Peter F. Stadler. "Direct Superbubble Detection." Algorithms 12, no. 4 (April 17, 2019): 81. http://dx.doi.org/10.3390/a12040081.

Full text

Abstract:

Superbubbles are a class of induced subgraphs in digraphs that play an essential role in assembly algorithms for high-throughput sequencing data. They are connected with the remainder of the host digraph by a single entrance and a single exit vertex. Linear-time algorithms for the enumeration superbubbles recently have become available. Current approaches require the decomposition of the input digraph into strongly-connected components, which are then analyzed separately. In principle, a single depth-first search could be used, provided one can guarantee that the root of the depth-first search (DFS)-tree is not itself located in the interior or the exit point of a superbubble. Here, we describe a linear-time algorithm to determine suitable roots for a DFS-forest that is guaranteed to identify the superbubbles in a digraph correctly. In addition to the advantages of a more straightforward implementation, we observe a nearly three-fold gain in performance on real-world datasets. We present a reference implementation of the new algorithm that accepts many commonly-used input formats for digraphs. It is available as open source from github.

APA, Harvard, Vancouver, ISO, and other styles

28

Donsig, Allan P. "Algebraic orders and chordal limit algebras." Proceedings of the Edinburgh Mathematical Society 41, no. 3 (October 1998): 465–85. http://dx.doi.org/10.1017/s0013091500019830.

Full text

Abstract:

We develop an isomorphism invariant for limit algebras: an extension of Power's strong algebraic order on the scale of the K0-group (Power, J. Operator Theory 27 (1992), 87–106). This invariant is complete for a certain family of limit algebras: inductive limits of digraph algebras (a.k.a. finite dimensional CSL algebras) satisfying two conditions: (1) the inclusions of the digraph algebras respect the order-preserving normalisers, and (2) the digraph algebras have chordal digraphs. The first condition is also used to show that the invariant depends only on the limit algebra and not the direct system. We give an intrinsic characterisation of the limit algebra and not the direct system. We give an intrinsic characterisation of the limit algebras satisfying both (1) and (2).

APA, Harvard, Vancouver, ISO, and other styles

29

Li, Ruijuan, Yanqin Cao, and Xinhong Zhang. "On kernels by rainbow paths in arc-coloured digraphs." Open Mathematics 19, no. 1 (January 1, 2021): 268–83. http://dx.doi.org/10.1515/math-2021-0019.

Full text

Abstract:

Abstract In 2018, Bai, Fujita and Zhang [Discrete Math. 341 (2018), no. 6, 1523–1533] introduced the concept of a kernel by rainbow paths (for short, RP-kernel) of an arc-coloured digraph D D , which is a subset S S of vertices of D D such that ( a a ) there exists no rainbow path for any pair of distinct vertices of S S , and ( b b ) every vertex outside S S can reach S S by a rainbow path in D D . They showed that it is NP-hard to recognize whether an arc-coloured digraph has an RP-kernel and it is NP-complete to decide whether an arc-coloured tournament has an RP-kernel. In this paper, we give the sufficient conditions for the existence of an RP-kernel in arc-coloured unicyclic digraphs, semicomplete digraphs, quasi-transitive digraphs and bipartite tournaments, and prove that these arc-coloured digraphs have RP-kernels if certain “short” cycles and certain “small” induced subdigraphs are rainbow.

APA, Harvard, Vancouver, ISO, and other styles

30

FENG, ZHIGANG, and GANG CHEN. "ON THE MINKOWSKI DIMENSION OF FUNCTIONAL DIGRAPH." Fractals 11, no. 01 (March 2003): 87–92. http://dx.doi.org/10.1142/s0218348x03001616.

Full text

Abstract:

Functional digraphs are sometimes fractal sets. As a special kind of fractal sets, the dimension properties of the functional digraph are studied in this paper. Firstly, the proof of a Minkowski dimension theorem is discussed and a new proof is given. Secondly, according to this dimension theorem, the Minkowski dimensions of the digraphs of the sum, deviation, product and quotient of two functions are discussed. And the relations between these Minkowski dimensions and the Minkowski dimensions of the digraphs of the two functions are established. In the conclusion, the maximum Minkowski dimension of the two functional digraphs plays a decisive part in the Minkowski dimensions of the digraphs of the sum, deviation, product and quotient of two functions.

APA, Harvard, Vancouver, ISO, and other styles

31

Shi, Haizhong, and Yue Shi. "Random graph languages." Discrete Mathematics, Algorithms and Applications 09, no. 02 (April 2017): 1750020. http://dx.doi.org/10.1142/s1793830917500203.

Full text

Abstract:

There tend to be no related researches regarding the relationships between graph theory and languages ever since the concept of graph-semigroup was first proposed in 1991. In 2011, after finding out the inner co-relations among digraphs, undirected graphs and languages, we proposed certain concepts including undirected graph language and digraph language; moreover, in 2014, we proposed a broaden concept–(V,R)-language and proved: (1) both undirected graph language and digraph language are (V,R)-languages; (2) both undirected graph language and digraph language are regular languages; (3) natural languages are regular languages. In this paper, we propose a new concept–Random Graph Language and build the relationships between random graph and language, which provides researchers with the possibility to do research about languages by using random graph theory.

APA, Harvard, Vancouver, ISO, and other styles

32

H Ahmed, E. EL Kholy,. "Operations on Digraphs and Digraph Folding." International Journal of Innovative Research in Computer and Communication Engineering 3, no. 7 (July 30, 2015): 6657–70. http://dx.doi.org/10.15680/ijircce.2015.0307140.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

BERTOLAZZI, PAOLA, ROBERT F. COHEN, GIUSEPPE DI BATTISTA, ROBERTO TAMASSIA, and IOANNIS G. TOLLIS. "HOW TO DRAW A SERIES-PARALLEL DIGRAPH." International Journal of Computational Geometry & Applications 04, no. 04 (December 1994): 385–402. http://dx.doi.org/10.1142/s0218195994000215.

Full text

Abstract:

Upward and dominance drawings of acyclic digraphs find important applications in the display of hierarchical structures such as PERT diagrams, subroutine-call charts, and is-a relationships. The combinatorial model underlying such hierarchical structures is often a series-parallel digraph. In this paper the problem of constructing upward and dominance drawings of series-parallel digraphs is investigated. We show that the area requirement of upward and dominance drawings of series-parallel digraphs crucially depends on the choice of planar embedding. Also, we present efficient sequential and parallel algorithms for drawing series-parallel digraphs. Our results show that while series-parallel digraphs have a rather simple and well understood combinatorial structure, naive drawing strategies lead to drawings with exponential area, and clever algorithms are needed to achieve optimal area.

APA, Harvard, Vancouver, ISO, and other styles

34

Fomichev, V. M., and V. M. Bobrov. "〈2〉-exponents of shift register transformations nonlinearity dipgraphs." Prikladnaya Diskretnaya Matematika, no. 55 (2022): 77–87. http://dx.doi.org/10.17223/20710410/55/5.

Full text

Abstract:

The matrix-graph approach is used to estimate the set of essential and non-linear variables of coordinate functions of the product of transformations of vector spaces. For essential variables, estimates are obtained by multiplying binary mixing matrices (or digraphs) of multiplied transformations, for non-linear variables - by multiplying ternary non-linearity matrices of multiplied transformations or their corresponding non-linearity digraphs, the arcs of which are labeled by the numbers of the set {0,1, 2}. For degrees of a given transformation, the area of non-trivial estimates is limited: for a set of essential variables, by the exponential of the mixing matrix (digraph); for a set of nonlinear variables, the 〈2〉-exponent of the matrix (digraph) of nonlinearity. For the class of transformations of binary shift registers, an attainable estimate of 〈2〉-exponents is obtained, expressed in terms of the length of the shift register and the set of numbers of essential and nonlinear variables of the feedback function. For register transformations whose non-linearity digraph has a loop, an exact formula for the 〈2〉-exponent is obtained. The results can be used to evaluate the nonlinearity characteristics of cryptographic functions built on the basis of iterations of register transformations.

APA, Harvard, Vancouver, ISO, and other styles

35

Malvestuto, Francesco M. "A new notion of convexity in digraphs with an application to Bayesian networks." Discrete Mathematics, Algorithms and Applications 09, no. 02 (April 2017): 1750016. http://dx.doi.org/10.1142/s1793830917500161.

Full text

Abstract:

We introduce a new notion of convexity in digraphs, which we call incoming-path convexity, and prove that the incoming-path convexity space of a digraph is a convex geometry (that is, it satisfies the Minkowski–Krein–Milman property) if and only if the digraph is acyclic. Moreover, we prove that incoming-path convexity is adequate to characterize collapsibility of models generated by Bayesian networks. Based on these results, we also provide simple linear algorithms to solve two topical problems on Markov properties of a Bayesian network (that is, on conditional independences valid in a Bayesian network).

APA, Harvard, Vancouver, ISO, and other styles

36

Sarma, Bhaba, and Kalyan Sinha. "The P_0^+-matrix completion problem." Electronic Journal of Linear Algebra 29 (September 20, 2015): 120–43. http://dx.doi.org/10.13001/1081-3810.2997.

Full text

Abstract:

A real n by n matrix B is a P_0^+ -matrix if for each k in {1, 2, . . . , n} every k by k principal minor of B is nonnegative, and at least one k by k principal minor is positive. A digraph D is said to have P_0^+-completion if every partial P_0^+-matrix specifying D can be completed to a P_0^+ -matrix. In this paper, we study the P_0^+-completion problem, give necessary conditions for a digraph to have P_0^+-completion, and single out those digraphs of order at most four that have P_0^+-completion.

APA, Harvard, Vancouver, ISO, and other styles

37

Meijin Luo, Yusong Lu. "The Primitive Exponent Set of a Class of Representative Twocolored Digraph in Graph Theory." Journal of Electrical Systems 20, no. 2 (April 4, 2024): 271–81. http://dx.doi.org/10.52783/jes.1173.

Full text

Abstract:

Graph is simple and intuitive. It can be used to solve many problems in computer science. For a kind of representativedigraph, the edges (arcs) of the digraph are colored with red and blue colors. The range of the primitive exponent are discussed indifferent cases, and the extremal two-colored digraphs are found by coloring all arcs with two colors. Finally, the primitive exponentset is given. The results can provide a reference for the study of primitive exponent of three-colored digraph and the application ofgraph coloring in computer science, such as communication network and coding cache.

APA, Harvard, Vancouver, ISO, and other styles

38

Sarma, Bhaba Kumar, and Kalyan Sinha. "The positive Q-matrix completion problem." Discrete Mathematics, Algorithms and Applications 07, no. 04 (December 2015): 1550052. http://dx.doi.org/10.1142/s1793830915500524.

Full text

Abstract:

A real [Formula: see text] matrix is a [Formula: see text]-matrix if for [Formula: see text] the sum of all [Formula: see text] principal minors is positive. A digraph [Formula: see text] is said to have positive [Formula: see text]-completion if every partial positive [Formula: see text]-matrix specifying [Formula: see text] can be completed to a positive [Formula: see text]-matrix. In this paper, necessary conditions for a digraph to have positive [Formula: see text]-completion are obtained and sufficient conditions for a digraph to have positive [Formula: see text]-completion are provided. The digraphs of order at most 4 that include all loops and have positive [Formula: see text]-completion are characterized. Tournaments whose complements have positive [Formula: see text]-completion are singled out. Further, some comparisons between the [Formula: see text]-matrix and positive [Formula: see text]-matrix completion problems have been made.

APA, Harvard, Vancouver, ISO, and other styles

39

Bravo, Diego, and Juan Rada. "Nonderogatory Unicyclic Digraphs." International Journal of Mathematics and Mathematical Sciences 2007 (2007): 1–8. http://dx.doi.org/10.1155/2007/46851.

Full text

Abstract:

A digraph is nonderogatory if its characteristic polynomial and minimal polynomial are equal. We find a characterization of nonderogatory unicyclic digraphs in terms of Hamiltonicity conditions. An immediate consequence of this characterization ia that the complete product of difans and diwheels is nonderogatory.

APA, Harvard, Vancouver, ISO, and other styles

40

Ridley, Dennis R., and B. Malcolm Lively. "English Letter Frequencies and Their Applications: Part II—Digraph Frequencies." Psychological Reports 95, no. 3 (December 2004): 787–94. http://dx.doi.org/10.2466/pr0.95.3.787-794.

Full text

Abstract:

This article continues the presentation of new data regarding the frequencies of English letters organized by word length and letter position. Digraphs (defined here as all two-letter combinations) were the objects of study. The frequencies of digraphs were derived from a sample of 320,780 English words (including 6505 different words), which were credibly demonstrated by Whissell to be a parsimonious representation of modern English word usage. A total of 997,380 digraphs were counted and sorted by locations according to word length and digraph positions within words. As assessed by the Whissell source, the data about digraphs presented accurately represent the frequencies with which digraphs occur in modern English. How these data can provide a resource for reading research and practice is explored.

APA, Harvard, Vancouver, ISO, and other styles

41

Granot, D., F. Granot, and W. R. Zhu. "Naturally submodular digraphs and forbidden digraph configurations." Discrete Applied Mathematics 100, no. 1-2 (March 2000): 67–84. http://dx.doi.org/10.1016/s0166-218x(99)00167-5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

MASK, ABBY GAIL, JONI SCHNEIDER, and XINGDE JIA. "EXTREMAL CAYLEY DIGRAPHS OF FINITE ABELIAN GROUPS." Journal of Interconnection Networks 12, no. 01n02 (March 2011): 125–35. http://dx.doi.org/10.1142/s0219265911002873.

Full text

Abstract:

Cayley digraphs of finite abelian groups are often used to model communication networks. Because of their applications, extremal Cayley digraphs have been studied extensively in recent years. Given any positive integers d and k. Let m*(d, k) denote the largest positive integer m such that there exists an m-element finite abelian group Γ and a k-element subset A of Γ such that diam ( Cay (Γ, A)) ≤ d, where diam ( Cay (Γ, A)) denotes the diameter of the Cayley digraph Cay (Γ, A) of Γ generated by A. Similarly, let m(d, k) denote the largest positive integer m such that there exists a k-element set A of integers with diam (ℤm, A)) ≤ d. In this paper, we prove, among other results, that [Formula: see text] for all d ≥ 1 and k ≥ 1. This means that the finite abelian group whose Cayley digraph is optimal with respect to its diameter and degree can be a cyclic group.

APA, Harvard, Vancouver, ISO, and other styles

43

Guo, Krystal. "Spectral Bound for Separations in Eulerian Digraphs." Electronic Journal of Linear Algebra 32 (February 6, 2017): 291–300. http://dx.doi.org/10.13001/1081-3810.3244.

Full text

Abstract:

The spectra of digraphs, unlike those of graphs, is a relatively unexplored territory. In a digraph, a separation is a pair of sets of vertices D and Y such that there are no arcs from D and Y. For a subclass of Eulerian digraphs, a bound on the size of a separation is obtained in terms of the eigenvalues of the Laplacian matrix. An infinite family of tournaments, namely, the Paley digraphs, where the bound holds with equality, is also given.

APA, Harvard, Vancouver, ISO, and other styles

44

Li, Honghai, and Teng Yu. "Hermitian Adjacency Spectrum of Cayley Digraphs over Dihedral Group." Algebra Colloquium 27, no. 01 (February 25, 2020): 121–30. http://dx.doi.org/10.1142/s1005386720000103.

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

45

HUANG, HAO, JIE MA, ASAF SHAPIRA, BENNY SUDAKOV, and RAPHAEL YUSTER. "Large Feedback Arc Sets, High Minimum Degree Subgraphs, and Long Cycles in Eulerian Digraphs." Combinatorics, Probability and Computing 22, no. 6 (September 12, 2013): 859–73. http://dx.doi.org/10.1017/s0963548313000394.

Full text

Abstract:

A minimum feedback arc set of a directed graph G is a smallest set of arcs whose removal makes G acyclic. Its cardinality is denoted by β(G). We show that a simple Eulerian digraph with n vertices and m arcs has β(G) ≥ m2/2n2+m/2n, and this bound is optimal for infinitely many m, n. Using this result we prove that a simple Eulerian digraph contains a cycle of length at most 6n2/m, and has an Eulerian subgraph with minimum degree at least m2/24n3. Both estimates are tight up to a constant factor. Finally, motivated by a conjecture of Bollobás and Scott, we also show how to find long cycles in Eulerian digraphs.

APA, Harvard, Vancouver, ISO, and other styles

46

Aboulker, Pierre, and Quentin Vermande. "Various Bounds on the Minimum Number of Arcs in a $k$-Dicritical Digraph." Electronic Journal of Combinatorics 31, no. 1 (January 26, 2024). http://dx.doi.org/10.37236/11549.

Full text

Abstract:

The dichromatic number $\vec{\chi}(G)$ of a digraph $G$ is the least integer $k$ such that $G$ can be partitioned into $k$ acyclic digraphs. A digraph is $k$-dicritical if $\vec{\chi}(G) = k$ and each proper subgraph $H$ of $G$ satisfies $\vec{\chi}(H) \leq k-1$. We prove various bounds on the minimum number of arcs in a $k$-dicritical digraph, a structural result on $k$-dicritical digraphs and a result on list-dicolouring. We characterise $3$-dicritical digraphs $G$ with $(k-1)|V(G)| + 1$ arcs. For $k \geq 4$, we characterise $k$-dicritical digraphs $G$ on at least $k+1$ vertices and with $(k-1)|V(G)| + k-3$ arcs, generalising a result of Dirac. We prove that, for $k \geq 5$, every $k$-dicritical digraph $G$ has at least $(k-\frac 1 2 - \frac 1 {k-1}) |V(G)| - k(\frac 1 2 - \frac 1 {k-1})$ arcs, which is the best known lower bound. We prove that the number of connected components induced by the vertices of degree $2(k-1)$ of a $k$-dicritical digraph is at most the number of connected components in the rest of the digraph, generalising a result of Stiebitz. Finally, we generalise a Theorem of Thomassen on list-chromatic number of undirected graphs to list-dichromatic number of digraphs.

APA, Harvard, Vancouver, ISO, and other styles

47

Severino, Michael. "A Construction of Uniquely $n$-Colorable Digraphs with Arbitrarily Large Digirth." Electronic Journal of Combinatorics 24, no. 2 (April 13, 2017). http://dx.doi.org/10.37236/4823.

Full text

Abstract:

A natural digraph analogue of the graph-theoretic concept of an `independent set' is that of an `acyclic set', namely a set of vertices not spanning a directed cycle. Hence a digraph analogue of a graph coloring is a decomposition of the vertex set into acyclic sets and we say a digraph is uniquely $n$-colorable when this decomposition is unique up to relabeling. It was shown probabilistically in [A. Harutyunyan et al., Uniquely $D$-colorable digraphs with large girth, Canad. J. Math., 64(6): 1310-1328, 2012] that there exist uniquely $n$-colorable digraphs with arbitrarily large girth. Here we give a construction of such digraphs and prove that they have circular chromatic number $n$. The graph-theoretic notion of `homomorphism' also gives rise to a digraph analogue. An acyclic homomorphism from a digraph $D$ to a digraph $H$ is a mapping $\varphi: V(D) \rightarrow V(H)$ such that $uv \in A(D)$ implies that either $\varphi(u)\varphi(v) \in A(H)$ or $\varphi(u)=\varphi(v)$, and all the `fibers' $\varphi^{-1}(v)$, for $v \in V(H)$, of $\varphi$ are acyclic. In this language, a core is a digraph $D$ for which there does not exist an acyclic homomorphism from $D$ to a proper subdigraph of itself. Here we prove some basic results about digraph cores and construct highly chromatic cores without short cycles.

APA, Harvard, Vancouver, ISO, and other styles

48

Liu, Juan, Hong Yang, Hong-Jian Lai, and Xindong Zhang. "Trail-Connected Digraphs with Given Local Structures." Journal of Interconnection Networks 22, no. 01 (January 15, 2022). http://dx.doi.org/10.1142/s0219265921420160.

Full text

Abstract:

For a digraph [Formula: see text], if [Formula: see text] contains a spanning closed trail, then [Formula: see text] is supereulerian. If for any pairs vertices [Formula: see text] and [Formula: see text] of [Formula: see text], [Formula: see text] contains both a spanning [Formula: see text]-trail and a spanning [Formula: see text]-trail, then [Formula: see text] is strongly trail-connected. If [Formula: see text] is a strongly trail-connected digraph, then [Formula: see text] is a supereulerian digraph. Algefari et al. proved that every symmetrically connected digraph and every partially symmetric digraph are supereulerian. In this paper, we prove that every symmetrically connected digraph and every partially symmetric digraph are strongly trail-connected digraphs.

APA, Harvard, Vancouver, ISO, and other styles

49

"Bipolar Fuzzy Soft Digraph." International Journal of Recent Technology and Engineering 8, no. 3 (September 30, 2019): 8901–13. http://dx.doi.org/10.35940/ijrte.c5528.098319.

Full text

Abstract:

Fuzzy sets and soft sets are two different tools for representing uncertainty and vagueness. In this paper , we combine the concepts of bipolar fuzzy soft sets and digraph theory and we introduce the notions of Bipolar fuzzy soft digraphs, Bipolar fuzzy soft subgraph in digraph and some operations in Bipolar fuzzy soft digraph.

APA, Harvard, Vancouver, ISO, and other styles

50

Tuite, James. "The structure of digraphs with excess one." Journal of Graph Theory, February 19, 2024. http://dx.doi.org/10.1002/jgt.23082.

Full text

Abstract:

AbstractA digraph is ‐geodetic if for any (not necessarily distinct) vertices there is at most one directed walk from to with length not exceeding . The order of a ‐geodetic digraph with minimum out‐degree is bounded below by the directed Moore bound . The Moore bound can be met only in the trivial cases and , so it is of interest to look for ‐geodetic digraphs with out‐degree and smallest possible order , where is the excess of the digraph. Miller, Miret and Sillasen recently ruled out the existence of digraphs with excess one for and and for and . We conjecture that there are no digraphs with excess one for and in this paper we investigate the structure of minimal counterexamples to this conjecture. We severely constrain the possible structures of the outlier function and prove the nonexistence of certain digraphs with degree three and excess one, as well closing the open cases and left by the analysis of Miller et al. We further show that there are no involutary digraphs with excess one, that is, the outlier function of any such digraph must contain a cycle of length .

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!