Log in

Relevant bibliographies by topics / Digraphe / Journal articles

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

Journal articles on the topic 'Digraphe'

Author: Grafiati

Published: 4 June 2021

Last updated: 1 February 2022

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 'Digraphe.'

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

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

2

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

3

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

4

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

5

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

6

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

7

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

8

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

9

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

10

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

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

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

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

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

15

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

16

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

17

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

18

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

19

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

20

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

21

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

22

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

23

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

24

Hafeez, Sumaira, and Mehtab Khan. "Computing extremal energy of a class of bicyclic weighted digraphs." Asian-European Journal of Mathematics 13, no. 05 (April 4, 2019): 2050090. http://dx.doi.org/10.1142/s1793557120500904.

Full text

Abstract:

The energy of a weighted digraph [Formula: see text] is the sum of absolute values of real part of its eigenvalues. Recently, the minimal and maximal energy of unicyclic weighted digraphs with cycle weight [Formula: see text] is studied. In this paper, we introduce a class [Formula: see text] of those bicyclic weighted digraphs of fixed order which contain vertex-disjoint weighted cycles of weights [Formula: see text] or [Formula: see text] and [Formula: see text] or [Formula: see text], where [Formula: see text]. We find digraphs in [Formula: see text] under certain conditions on [Formula: see text] and [Formula: see text] with extremal energy.

APA, Harvard, Vancouver, ISO, and other styles

25

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

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

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

28

Junussov, Ibragim A. "Static Consensus in Passifiable Linear Networks." International Journal of Differential Equations 2016 (2016): 1–9. http://dx.doi.org/10.1155/2016/9192127.

Full text

Abstract:

Sufficient conditions of consensus (synchronization) in networks described by digraphs and consisting of identical deterministic SIMO systems are derived. Identical and nonidentical control gains (positive arc weights) are considered. Connection between admissible digraphs and nonsmooth hypersurfaces (sufficient gain boundary) is established. Necessary and sufficient conditions for static consensus by output feedback in networks consisting of certain class of double integrators are rediscovered. Scalability for circle digraph in terms of gain magnitudes is studied. Examples and results of numerical simulations are presented.

APA, Harvard, Vancouver, ISO, and other styles

29

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

30

Jamal, Fareeha, and Mehtab Khan. "Extremal iota energy of a subclass of bicyclic digraphs and sidigraphs." Asian-European Journal of Mathematics 13, no. 07 (June 28, 2019): 2050127. http://dx.doi.org/10.1142/s1793557120501272.

Full text

Abstract:

The iota energy of an [Formula: see text]-vertex digraph [Formula: see text] is defined by [Formula: see text], where [Formula: see text] are eigenvalues of [Formula: see text] and [Formula: see text] is the imaginary part of eigenvalue [Formula: see text] Recently, this concept of iota energy of digraphs is extended to sidigraphs. The iota energy of a sidigraph is defined in an analogous way. In this paper, we consider a class of digraphs with two linear subdigraphs of equal length and find digraphs in this class with extremal iota energy. Furthermore, we take a similar class of sidigraphs and find minimal and maximal iota energy among the sidigraphs in this class.

APA, Harvard, Vancouver, ISO, and other styles

31

Ahmad, Uzma. "The power digraphs associated with generalized dihedral groups." Discrete Mathematics, Algorithms and Applications 07, no. 04 (December 2015): 1550057. http://dx.doi.org/10.1142/s1793830915500573.

Full text

Abstract:

We study the digraphs based on dihedral group [Formula: see text] by using the power mapping, i.e., the set of vertices of these digraphs is [Formula: see text] and the set of edges is [Formula: see text]. These are called the power digraphs and denoted by [Formula: see text]. The cycle and in-degree structure of these digraphs are completely examined. This investigation leads to the derivation of various formulae regarding the number of cycle vertices, the length of the cycles, the number of cycles of certain lengths and the in-degrees of all vertices. We also establish necessary and sufficient conditions for a vertex to be a cycle vertex. The analysis of distance between vertices culminates at different expressions in terms of [Formula: see text] and [Formula: see text] to determine the heights of vertices, components and the power digraph itself. Moreover, all regular and semi-regular power digraphs [Formula: see text] are completely classified.

APA, Harvard, Vancouver, ISO, and other styles

32

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

33

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

34

Pleanmani, Nopparat, and Sayan Panma. "Bounds for the dichromatic number of a generalized lexicographic product of digraphs." Discrete Mathematics, Algorithms and Applications 08, no. 02 (May 26, 2016): 1650034. http://dx.doi.org/10.1142/s1793830916500348.

Full text

Abstract:

A subset [Formula: see text] is acyclic if it induces an acyclic subdigraph of a digraph [Formula: see text] and the dichromatic number [Formula: see text] of [Formula: see text] is defined to be the minimum integer [Formula: see text] such that [Formula: see text] can be partitioned into [Formula: see text] 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.

APA, Harvard, Vancouver, ISO, and other styles

35

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

36

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

37

Skilton, D. K. "Digraphs with eulerian chains." Journal of the Australian Mathematical Society. Series A. Pure Mathematics and Statistics 41, no. 3 (December 1986): 298–303. http://dx.doi.org/10.1017/s1446788700033735.

Full text

Abstract:

AbstractAn eulerian chain in a directed graph is a continuous directed route which traces every arc of the digraph exactly once. Such a route may be finite or infinite, and may have 0, 1 or 2 end vertices. For each kind of eulerian chain, there is a characterization of those diagraphs possessing such a route. In this survey paper we strealine these characterizations, and then synthesize them into a single description of all digraphs having some eulerian chain. Similar work has been done for eulerian chains in undirected graphs, so we are able to compare corresponding results for graphs and digraphs.

APA, Harvard, Vancouver, ISO, and other styles

38

GREEN, DAVID G. "CONNECTIVITY AND THE EVOLUTION OF BIOLOGICAL SYSTEMS." Journal of Biological Systems 02, no. 01 (March 1994): 91–103. http://dx.doi.org/10.1142/s0218339094000088.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

39

WEI, YANGJIANG, GAOHUA TANG, and JIZHU NAN. "THE ITERATION DIGRAPHS OF GROUP RINGS OVER FINITE FIELDS." Journal of Algebra and Its Applications 13, no. 05 (February 25, 2014): 1350162. http://dx.doi.org/10.1142/s0219498813501624.

Full text

Abstract:

For a finite commutative ring R and a positive integer k ≥ 2, we construct an iteration digraph G(R, k) whose vertex set is R and for which there is a directed edge from a ∈ R to b ∈ R if b = ak. In this paper, we investigate the iteration digraphs G(𝔽prCn, k) of 𝔽prCn, the group ring of a cyclic group Cn over a finite field 𝔽pr. We study the cycle structure of G(𝔽prCn, k), and explore the symmetric digraphs. Finally, we obtain necessary and sufficient conditions on 𝔽prCn and k such that G(𝔽prCn, k) is semiregular.

APA, Harvard, Vancouver, ISO, and other styles

40

Dehgardi, Nasrin, Maryam Atapour, and Abdollah Khodkar. "Twin signed k-domination numbers in directed graphs." Filomat 31, no. 20 (2017): 6367–78. http://dx.doi.org/10.2298/fil1720367d.

Full text

Abstract:

Let D = (V;A) be a finite simple directed graph (digraph). A function f : V ? {-1,1} is called a twin signed k-dominating function (TSkDF) if f (N-[v]) ? k and f (N+[v]) ? k for each vertex v ? V. The twin signed k-domination number of D is ?* sk(D) = min{?(f)?f is a TSkDF of D}. In this paper, we initiate the study of twin signed k-domination in digraphs and present some bounds on ?* sk(D) in terms of the order, size and maximum and minimum indegrees and outdegrees, generalising some of the existing bounds for the twin signed domination numbers in digraphs and the signed k-domination numbers in graphs. In addition, we determine the twin signed k-domination numbers of some classes of digraphs.

APA, Harvard, Vancouver, ISO, and other styles

41

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

42

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

43

EĞECIOĞLU, ÖMER, JEFFREY B. REMMEL, and S. GILL WILLIAMSON. "A CLASS OF GRAPHS WHICH HAS EFFICIENT RANKING AND UNRANKING ALGORITHMS FOR SPANNING TREES AND FORESTS." International Journal of Foundations of Computer Science 15, no. 04 (August 2004): 619–48. http://dx.doi.org/10.1142/s0129054104002650.

Full text

Abstract:

Remmel and Williamson recently defined a class of directed graphs, called filtered digraphs, and described a natural class of bijections between oriented spanning forests of these digraphs and associated classes of functions [12]. Filtered digraphs include many specialized graphs such as complete k-partite graphs. The Remmel-Williamson bijections provide explicit formulas for various multivariate generating functions for the oriented spanning forests which arise in this context. In this paper, we prove another important property of these bijections, namely, that it allows one to construct efficient algorithms for ranking and unranking spanning trees or spanning forests of filtered digraphs G. For example, we show that if G=(V,E) is a filtered digraph and SP(G) is the collection of spanning trees of G, then our algorithm requires O(|V|) operations of sum, difference, product, quotient, and comparison of numbers less than or equal |SP(G)| to rank or unrank spanning trees of G.

APA, Harvard, Vancouver, ISO, and other styles

44

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

45

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

46

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

47

Qi, Xingqin, Edgar Fuller, Rong Luo, Guodong Guo, and Cunquan Zhang. "Laplacian Energy of Digraphs and a Minimum Laplacian Energy Algorithm." International Journal of Foundations of Computer Science 26, no. 03 (April 2015): 367–80. http://dx.doi.org/10.1142/s0129054115500203.

Full text

Abstract:

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 [Formula: see text] and directed Laplacian energy [Formula: see text] using the second spectral moment of [Formula: see text] for a digraph [Formula: see text] with [Formula: see text] vertices, where [Formula: see text] is the diagonal out-degree matrix, and [Formula: see text] with [Formula: see text] whenever there is an arc [Formula: see text] from the vertex [Formula: see text] to the vertex [Formula: see text] 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.

APA, Harvard, Vancouver, ISO, and other styles

48

Zhang, Xinhong, Caijuan Xue, and Ruijuan Li. "The domination number of round digraphs." Open Mathematics 18, no. 1 (January 1, 2020): 1625–34. http://dx.doi.org/10.1515/math-2020-0084.

Full text

Abstract:

Abstract The concept of the domination number plays an important role in both theory and applications of digraphs. Let D = ( V , A ) D=(V,A) be a digraph. A vertex subset T ⊆ V ( D ) T\subseteq V(D) is called a dominating set of D, if there is a vertex t ∈ T t\in T such that t v ∈ A ( D ) tv\in A(D) for every vertex v ∈ V ( D ) \ T v\in V(D)\backslash T . The dominating number of D is the cardinality of a smallest dominating set of D, denoted by γ ( D ) \gamma (D) . In this paper, the domination number of round digraphs is characterized completely.

APA, Harvard, Vancouver, ISO, and other styles

49

Muranov, Yuri V., and Anna Szczepkowska. "Path homology theory of edge-colored graphs." Open Mathematics 19, no. 1 (January 1, 2021): 706–23. http://dx.doi.org/10.1515/math-2021-0049.

Full text

Abstract:

Abstract In this paper, we introduce the category and the homotopy category of edge-colored digraphs and construct the functorial homology theory on the foundation of the path homology theory provided by Grigoryan, Muranov, and Shing-Tung Yau. We give the construction of the path homology theory for edge-colored graphs that follows immediately from the consideration of natural functor from the category of graphs to the subcategory of symmetrical digraphs. We describe the natural filtration of path homology groups of any digraph equipped with edge coloring, provide the definition of the corresponding spectral sequence, and obtain commutative diagrams and braids of exact sequences.

APA, Harvard, Vancouver, ISO, and other styles

50

Sheikholeslami, Seyed Mahmoud, Asghar Bodaghli, and Lutz Volkmann. "Twin signed Roman domination numbers in directed graphs." Tamkang Journal of Mathematics 47, no. 3 (September 30, 2016): 357–71. http://dx.doi.org/10.5556/j.tkjm.47.2016.2035.

Full text

Abstract:

Let $D$ be a finite simple digraph with vertex set $V(D)$ and arc set $A(D)$. A twin signed Roman dominating function (TSRDF) on the digraph $D$ is a function $f:V(D)\rightarrow\{-1,1,2\}$ satisfying the conditions that (i) $\sum_{x\in N^-[v]}f(x)\ge 1$ and $\sum_{x\in N^+[v]}f(x)\ge 1$ for each $v\in V(D)$, where $N^-[v]$ (resp. $N^+[v]$) consists of $v$ and all in-neighbors (resp. out-neighbors) of $v$, and (ii) every vertex $u$ for which $f(u)=-1$ has an in-neighbor $v$ and an out-neighbor $w$ for which $f(v)=f(w)=2$. The weight of an TSRDF $f$ is $\omega(f)=\sum_{v\in V(D)}f(v)$. The twin signed Roman domination number $\gamma_{sR}^*(D)$ of $D$ is the minimum weight of an TSRDF on $D$. In this paper, we initiate the study of twin signed Roman domination in digraphs and we present some sharp bounds on $\gamma_{sR}^*(D)$. In addition, we determine the twin signed Roman domination number of some classes of digraphs.

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!