Mathematical tools for the future: Graph Theory and graphicable algebras

Mathematical tools for the future: Graph Theory and graphicable algebras Juan N´ u˜ nez1, Marithania Silvero and Mar´ ıa Trinidad Villar2 jn[email protected] [email protected] [email protected] Departamento de Geometr´ ıa y Topolog´ ıa. Facultad de Matem´ aticas. Universidad de Sevilla. Aptdo. 1160. 41080-Seville (Spain). Abstract. This study constitutes the continuation of innovative research in Discrete Mathematics introduced in earlier papers on algebras in general, regarding the use of graphs to study the particular case of graphicable algebras, which form a subset of evolution algebras. Evolution algebras are particularly interesting since they are intrinsically linked with other mathematical fields, such as group theory, stochastics processes, and dynamical systems, for instance. Our advances in this study are obtained by setting a natural correspondence between evolution algebras and direct graphs, in order to translate the general concepts of graphicable algebras: subalgebra, ideal, centralizer, normalizer... to the language of graphs. These translations will enable advances in the application of these algebras to various branches of Mathematics. Abbreviated Title: Mathematical tools for the future: Graph Theory and graphicable algebras. Keywords: Graphicable Algebras; Evolution Algebras; Evolution Operator; Directed Graphs; Pseudo-graphs. 2010 Mathematics Subject Classification: 17D99; 05C20; 05C50. 1Partially supported by MTM2010-19336, FEDER and P.A.I. Group FQM-326 2Partially supported by P.A.I Group FQM-164 1. Introduction In this paper we deal with the class of graphicable algebras, which constitutes a subset of evolution algebras. The main goal is to deal with the study of the particular connection between graphicable algebras and Graph Theory by adding new results to those already known, which can be found in the final chapter of [1], where one can also find related open problems, some of which are solved in this paper. Note that this supposes the introduction of innovative research in Discrete Mathematics regarding the use of graphs to solve certain open problems related to the theory of non-associative algebras. The concept of evolution algebra (non-associative algebras satisfying the condition ei·ej= 0, whenever ei,ejare two distinct basis elements) is relatively recent and lies between algebras and dynamical systems. These algebras, which were first introduced by J. P. Tian, and then jointly presented with Vojtechovsky in 2006 [2], and later appeared as a book by Tian in 2008 [1], have many connections with other mathematical fields, including group theory, stochastic processes, dynamical systems, knot theory, and 3-manifolds (see [3]). Indeed, evolution algebras were based on the self-reproduction rule of non-Mendelian genetics [4]. As Tian exposes in [1], mathematicians and geneticists once used non-associative algebras to study Mendelian genetics. It was Mendel [5] who first exploited symbols that are algebraically suggestive to express his genetic laws. In fact, these symbols were later termed Mendelian algebras by several authors. In the 1920s and 1930s, general genetic algebras were introduced. Apparently, Serebrowsky [6] was the first to give an algebraic interpretation of the sign ”x”, which indicated sexual reproduction, and to give a mathematical formulation of Mendel’s laws. Glivenkov [7] introduced the so-called Mendelian algebras for diploid populations with one locus or two unlinked loci. Independently, Kostitzin [8] also introduced a symbolic multiplication to express Mendel’s laws. The systematic study of algebras occurring in genetics can be attributed to Etherington. In [9], he succeeded in giving a precise mathematical formulation of Mendel’s laws in terms of non-associative algebras. Moreover, several examples from biology, physics and mathematics, including topology and stochastic processes, have triggered motivated the development of the theory of evolution algebras. An in-depth study of these examples is given in Chapter 2 of [1]. Our motivation for using Graph Theory as a tool to study evolution algebras is now explained. The representation of these algebras through graphs may facilitate the study of algebras by taking advantage of their properties. This representation was used by Tian in a certain degree when he dealt with Feynman graphs, which can be associated with algebraic structures, to study elementary particle physics. Let us recall that a Feynman graph [10] is a graph, each edge of which topologically represents a propagation of a free elementary particle, and each vertex 1 of which represents an interaction of elementary particles. This graph may have some extraordinary edges, called external edges, in addition to the ordinary edges, which are called internal edges. Every external edge has only one end point. A vertex is called an external vertex if at least one external edge is incident with it. Vertices other than external vertices are called internal vertices. According to the total number nof external edges, connected Feynman graphs have various names: vacuum polarization graphs, tadpole graphs, self-energy graphs, vertex graphs, two-particle scattering graphs and one-particle production graphs depending on whether nis 10,1,2,3,4or 5, respectively. Under this definition, Tian proved, with an example, that the algebra corresponding to a self-energy Feynman graph is an evolution quotient algebra. The structure of the paper is as follows: Section 2 recalls some preliminaries on graphicable algebras and on Graph Theory. In Section 3, Graph Theory is used as a tool to obtain new results on graphicable algebras which could provide steps forward in the knowledge of evolution algebras in the future. In this section, the proofs of several result obtained by Tian in [1] are further improved. Section 4 is devoted to conclusions and to specifying open problems from this study. Finally, the authors would like to point out that although the paper deals with the link between graphicable algebras and graphs, definitions and examples which relax the definition given of graphicable algebras have been included throughout the paper. This flexibility enables more to be studied about graphs and algebras, and it is our intention to consider algebras and graphs them in future work. Hence, the category of these algebras would contain more graphs and the relation between these algebras and graphs would not be isomorphic, but instead homomorphic, which might be highly interesting. 2. Preliminaries This section is devoted to recalling some basic notions on the concepts dealt with in the paper. For a more general overview on evolution algebras and on Graph Theory, the reader can consult, for instance, [1, 2] and [11], respectively. 2.1. Evolution algebras To begin with, it is convenient to note that henceforth, all of the evolution algebras considered in the paper will be finite (in fact, it is proved in [1] that there is no principal difference between finite and infinite cases). Let Ebe an algebra (not necessarily associative) over a field Kequipped with multiplication, and let ei, i ∈Λbe a basis of E. Therefore, ei·ej=Pk∈Λak ij ek, for certain ak ij ∈K, where only finitely many structure constants ak ij are non-zero for a fixed i, j ∈Λ. 2 Under these conditions, Tian defined an evolution algebra as that which verifies ak ij = 0, whenever i6=j. Upon renaming the structure constants, we can write ei·ei=Pv j=1 aji ej. In the particular case where aij =aji, for i, j ∈Λ,i6=jand aii = 0, for every i∈Λ, this is called by us S-evolution algebra. As an example, the algebra Ewith basis {e1, e2, e3}and multiplication defined by e1·e1=e1+e2,e2·e2=−e1−e2,e3·e3=−e2+e3, is an evolution algebra. It is interesting to point out here that there already exist several papers in the literature linking Lie algebras and Graph Theory (see [12, 13] for instance). In this respect, note that evolution algebras are not obviously Lie algebras. Conversely, Lie algebras are not evolution algebras as can be seen in the following example: the simple Lie algebra of dimension 3and law e1·e2= 2 e2,e1·e3=−2e3, e2·e3=e1is not an evolution algebra. Let us remember that a Lie algebra L over a field Kis a vector space over Kendowed with a second inner law, known as bracket product, which verifies the following three properties: 1. Bilinear: [u, v +z] = [u, v]+[u, z]; [u+v, z]=[u, z]+[v, z]; [αu, βv] = αβ[u, v],∀α, β ∈K,∀u, v, z ∈ L. 2. Anti-commutative: [v, u] = −[u, v],∀u, v ∈ L. 3. Jacobi identity: [[u, v], w] + [[v, w], u] + [[w, u], v] = 0,∀u, v, w ∈ L. In this definition, [v, u]is the usual form used in Lie theory for denoting vu. Let us also recall that there are two types of trivial evolution algebras: zero evolution algebras and non-zero trivial evolution algebras. If the defining relations are given by ei·ej= 0, for i6=jand any e2 i=ei·ei= 0, the evolution algebra generated by these generators is said to be a zero evolution algebra. If the defining relations are given by ei·ej= 0 for i6=jand e2 i=k ei, then the evolution algebra is said to be a non-zero trivial evolution algebra. To avoid triviality, in this paper it is always assumed that an evolution algebra is not a zero algebra in this paper. Tian [1] and Tian and Vojtechovsky [2] show a complete study of the algebraic properties of an evolution algebra. Indeed, they prove that: 1. In general, evolution algebras are not associative. 2. Evolution algebras are commutative and flexible algebras. Let us recall that any algebra is said to be flexible if it satisfies x·(y·x) = (x·y)·x, for all elements x, y. 3. Evolution algebras are not power-associative in general, which means that (ei·ei)·(ei·ei) = ((ei·ei)·ei)·eiis not always verified. 4. The direct sum of evolution algebras is also an evolution algebra. Clearly the dimension of the sum is the sum of the dimensions of the summands. 5. Evolution algebras have a unitary element if and only if they are non-zero trivial algebras. 3 It is also important to note that in [1], Tian considers an element on the basis of an evolution algebra either as an allele in genetics, or a state in stochastic processes, and addresses the timing of the appearance of a state in the next step of the process. If Eis an evolution algebra with a generator set ei|i∈Λ, then the linear map L:E7→ E|L(ei) = e2 i=Pkakiek, for all i∈Λis called the evolution operator of E. 2.2. Graphicable algebras In his book [1] Tian introduced the concept of graphicable algebra as follows: a commutative non-associative algebra Ais called graphicable if it has a set of generators V={e1, e2, . . . , er}with the two defining relations e2 i=X ek∈Vi ek, ei·ej= 0, i 6=j;i, j = 1,2, . . . , r, where Viis a subset of V. It is immediate to see that any graphicable algebra Ais an evolution algebra, although the converse is not true in general. In the particular case that aij =aji for i6=j;i, j = 1,2, . . . , r, and aii = 0 for every i= 1,2, . . . , r, we call this graphicable algebra is called an S-graphicable algebra. Therefore, the family of evolution algebras can be classified as in the following diagram: Evolution Algebras S−Evolution Algebras Graphicable Algebras S−Graphicable Algebras 2.3. Graph Theory terminology With respect to Graph Theory, the primary concepts of simple graph, directed graph, loop, pseudograph, multigraph, neighbour, degree of a vertex in a simple graph and in-degree of and out-degree of a vertex in a directed graph are supposed. Figure 1 shows an example of a multigraph. 4 v1 v2 v3 v4 v5 Figure 1: A multigraph. In this paper a particular type of graph appears: cubic graphs, which are regular graphs of degree 3, such as the Petersen graph, which is a 3-regular graph with 10 vertices and 15 edges, and is most commonly drawn as a pentagon containing a pentagram, with five spokes, and the Heawood graph, which is an undirected 3-regular graph with 14 vertices and 21 edges (see Subsection 3.1). The concept of the adjacency matrix of a graph proves itself to be of great use in this paper. Let Gbe a graph with nvertices v1, v2, . . . , vn. The adjacency matrix of G, with respect to this particular listing of the vertices of G, is the n×n matrix M(G) = (mij)where the (i, j)th entry mij is the number of edges joining the vertex vito the vertex vj. As an example, the adjacency matrix of the multigraph in Figure 1 can be seen in Figure 2.      01101 10100 11020 00202 10020      Figure 2: The adjacency matrix of the multigraph in Figure 1. A well-known result is the so-called first theorem of Graph Theory or Handshaking Lemma which states for any simple graph with redges and nvertices v1, . . . , vn, that n X i=1 δ(vi)=2rholds, where δ(vi)denotes the degree of the vertex vi. 5 As an immediate consequence, in any simple graph G, there is an even number of vertices of an odd degree. A version of this result related to graphicable algebras will is shown in Section 3. 3. Graph Theory: a tool to study graphicable algebras As pointed out in the Introduction, this paper deals with the study of the particular connection between graphicable algebras and Graph Theory. Graph Theory is used here as a tool in order to facilitate the study of graphicable algebras by applying the properties of Graph Theory in their corresponding associated graphs to add new results to those already known about these algebras. 3.1. Graphs and graphicable algebras Henceforth directed graphs are considered to have the possibility of containing loops. Given a graph G= (V, E)there always exists an evolution algebra A(G) associated to G. Definition 1. [1] Let G= (V, E)be a graph, Vbe the set of vertices of G, and Ebe the set of edges of G. An algebra A(G) = hV|Riis designed as follows: V={e1, e2, . . . , er}is taken as the generator set and R=   e2 i=X ek∈Γ(ei) ek;ei·ej= 0,i6=j; 1≤i, j ≤r    is taken as as the set of defining relations, where Γ(ei)is the set of neighbours of ei. The algebra A(G)is clearly an evolution algebra. However, in [1], there is no definition of a graph associated to an evolution algebra A. The definition is therefore introduced below: Definition 2. Given an n-dimensional evolution algebra A, the matrix associated to Ais that matrix L(A)whose elements are, in columns, the coefficients of the fields ejof the basis of Ain the expressions of the brackets e2 j, for 1≤j≤n. From previous definitions, an evolution algebra Ahas an associated weighted directed graph, which may or may not contain loops, G(A)=(V, E), as follows: Vis the set of generators of the algebra and Eis the set of edges linking eiwith vertices in Γ(ei)for each ei. The weight of each edge represents the coefficient 6 which appears in the corresponding bracket in the law of the algebra. Moreover, in the particular case of graphicable algebras, all of these weights are equal to 1 and hence are omitted in the graph. For instance, Figure 3 represents the graphs associated with the trivial evolution algebras A1and A2, that have the following laws, respectively A1:ei·ej= 0 (i6=j)A2:ei·ej= 0 (i6=j) e2 i= 0 (∀i)e2 i=kiei(∀i) . . . e1e2en . . . e1e2en A1A2 k1k2kn Figure 3: The trivial algebras A1and A2. For a graphicable algebra, A, the graph associated to A,G(A), has a binary adjacency matrix. Example 3. Let Abe the graphicable algebra with generator set {e1, e2, e3, e4} with the defining relations e2 1=e1+e2, e2 2=e2+e3, e2 3=e3+e4. The matrix L(A)associated to this algebra is: L(A)≡     1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 0     The graph whose adjacency matrix is L(A)is shown in Figure 4. In [1], the graphicable algebras associated to the complete graphs, the cycles, and the paths of nvertices, Kn,Cnand Pnrespectively, are illustrated. All three 7 e3e4 e2e1 Figure 4: The pseudograph with adjacency matrix L(A). are S-graphicable algebras. The S-graphicable algebras associated to certain regular graphs with degree 3in each vertex, such as the Petersen graph and the Heawood graph are represented here, for instance, the bipartite complete graph Km,n and the wheel graph Wn=Cn+v, respectively. Note that although p(mod p) normally implies 0, from now on, p(mod p) will be denoted as p. Example 4. For the graph below, Figure 5, e1e2 e4 e3 e5e6 Figure 5: A3-regular graph with six vertices. it is not difficult to define its associated S-graphicable algebra with generator set {e1, . . . , e6}and defining relations e2 1=e2+e3+e5, e2 2=e1+e4+e6, e2 3=e1+e4+e5, e2 4=e2+e3+e6, e2 5=e1+e3+e6, e2 6=e2+e4+e5. Example 5. Similarly, for the following cubic graph Q3in Figure 6, it is also easy to define its associated S-graphicable algebra with generator set {e1, . . . , e8}and defining relations 8 Definition 15. Let Abe an S−graphicable algebra with ngenerators, G=G(A) be its associated simple graph, and degrees be d1≥d2≥. . . ≥dn. The n−tuple (d1, d2, . . . , dn)is called the degree sequence of A. A non-necessarily strictly decreasing integer sequence Dis said to be realizable if there exists an S−graphicable algebra whose degree sequence is D. A definition for directed graphs given in [14] can now be to the case of graphicable algebras with ngenerators which have an associated directed graph with loops. Definition 16. Abi-degree sequence (d+, d−) = ({d+ 1, d+ 2, . . . , d+ n},{d− 1, d− 2,..., d− n})of non-negative integers is called a bi-graphical sequence if there exists a graphicable algebra Awith ngenerators V={e1, e2, . . . , en}, such that the outdegree and in-degree sequences together form (d+, d−)(that is, the out-degree of generator ejis d+ jand its in-degree is d− j). In this case, it is said that (d+, d−)is realizable by the graphicable algebra A, and Arealizes (d+, d−). Although the degree sequence is a graph invariant, it does not, in general, uniquely identify a graph; in some cases, non-isomorphic graphs can have the same degree sequence. For S-graphicable algebras, the same conclusion can be drawn, but it is interesting to use the Havel-Hakimi algorithm ([15]) to determine the family of S−graphicable algebras of a given dimension. One process of obtaining a set of S-graphicable algebras of dimension ncan be schematized as follows: 1. Let D= (d1, d2, . . . , dn)be an n−tuple of non-necessarily strictly decreasing integers. 2. Apply the Havel-Hakimi algorithm ([15]) to determine whether Dis the sequence degree of a simple graph G. (a) If Dis the sequence degree of a graph G, then consider the adjacency matrix M(G)and the corresponding graphicable algebra A(G)whose evolution operator is given by M(G). (b) If Dis not the sequence degree of any graph G, then there does not exist a graphicable algebra with sequence degree D. For graphicable algebras which have associated directed graphs without loops, an analogous procedure can be followed by using the Havel-Hakimi-type algorithm to realize bi-graphical degree sequences of directed graphs, as designed by P. L. Erd¨ os, I. Mikl´ os and Z. Toroczkai ([14]). 15 In order to determine the complete family of graphicable algebras of a given dimension, the method is finished when graphicable algebras with associated directed graphs with loops are obtained. In the references 5, 13 and 17 listed in [14], the first steps in this research are clarified, although the corresponding algorithms are not shown. Example 17. Let S= (4,3,3,2,2) be a non-decreasing sequence of integers. By applying the Havel-Hakimi algorithm it is shown that there exists a unique graph, Gof Figure 9, whose degree sequence is Sand adjacency matrix is the following:       01111 10100 11010 10101 10010       The S-graphicable algebra associated to Gshown in Figure 9 has the following relations: e2 1=e2+e3+e4+e5, e2 2=e1+e3, e2 3=e1+e2+e4, e2 4=e1+e3+e5, e2 5=e1+e4. e1 e2 e3 e4 e5 G Figure 9: The only graph with degree sequence S. 16 Example 18. Let R= (4,3,3,2,2,1,1) be another non-decreasing sequence of integers. By applying the Havel-Hakimi algorithm it is shown that there exist at least two non-isomorphic graphs, G1and G2of Figure 10, whose degree sequence is R. e1e2 e3 e4 e5 G1 e3 e5 G2 e1 e2 e7 e4 e6 e6 e7 Figure 10: Two non-isomorphic graphs G1and G2with degree sequence R. The adjacency matrix for G1is           0000010 0010000 0100001 0000101 0001011 1000101 0011110           The S−graphicable algebra associated to G1has the following relations: e2 1= + e6, e2 2=e3, e2 3=e2+e7, e2 4=e5+e6, e2 5=e4+e6+e7, e2 6=e1+e5+e7, e2 7=e3+e4+e5+e6. 17 The adjacency matrix for G2is           0100000 1000000 0000101 0000011 0010011 0001101 0011110           The S−graphicable algebra associated to G2has the following relations: e2 1=e2, e2 2=e1, e2 3=e5+e7, e2 4=e6+e7, e2 5=e3+e6+e7, e2 6=e4+e5+e7, e2 7=e3+e4+e5+e6. 3.2. The evolution operator In [1], the evolution operator Lof a graphicable algebra Ais used as a tool to study some properties of the graph Gsuch that A(G) = A. The notion of the graph determined by an evolution algebra by using the evolution operator of such an algebra is now introduced. We consider this concept to be appropriate for use when dealing with non-associative algebras in general. Definition 19. Let Ebe an evolution algebra with finite generator set {ei|i= 1,2, . . . , n}and let L:E 7→ E | L(ei) = e2 i=Pkakiek, for all i= 1,2, . . . , n be its evolution operator. The graph associated to E,G(E), is the weighted graph with vertex set V(E) = {v1, v2, . . . , vn}and adjacency matrix (aki), k, i ∈ {1,2, . . . , n}. Example 20. Let L1be the evolution algebra given by the following relations: e2 1=e2, e2 2= 2 e2+e3, e2 3=e3+ 2 e4, e2 4=−e1. 18 The adjacency matrix of G(L1)is given by     0 0 0 −1 1 2 0 0 0 1 1 0 0 0 2 0     ⇓ e3 e4 e2 e1 −1 2 2 Example 21. Let L2be the S−evolution algebra given by the following relations e2 1= 2e2+ 3e3, e2 2= 2e1, e2 3= 3e1. The adjacency matrix of G(L2)is given by   0 2 3 2 0 0 3 0 0   4 Certain conclusions and open problems As a conclusion, the authors would like to point out that, although in this paper Graph Theory has been used as a tool to deal with graphicable algebras as a previous step to tackle, in a similar way, the study of evolution algebras, more results on graphicable algebras can be obtained in the future. Indeed, research in this area continues. Now, as open problems on this research, we have: 19 • As Tian states in [1], the first question to address is whether every statement or problem in graph theory can be translated into the language of evolution algebras. If this is indeed the case, then a brand new algebraic graph theory emerges, which will doubtless bring a new and significant approach to studying computer science. • As is currently appreciated, in general, non-associative algebras are not easy to study. We consider that Graph Theory can also provide a tool to study these algebras by using graphicable and evolution algebras in a similar way to that indicated here, due to a natural correspondence between evolution algebras and direct graphs. • Finally, since the mathematical objects of genetic evolution are discrete spaces or graph-like spaces, it is natural to consider that the study of the connection between evolution algebras and Graph Theory could be relevant, owing to the utility of evolution algebras in genetic evolution. This constitutes another of the many open problems in the study of these two applications and contributes towards the understanding of the significance of these algebras in natural phenomena. To finish the paper, let us emphasize the great importance, in our opinion, that evolution algebras in general and graphicable algebras in particular hold, above all for their potential interesting applications in a wide variety of mathematical fields. Indeed, as Tian himself pointed out in his book [1] . . . evolution algebras are ones in which the multiplication tables are of a special type. They are motivated by evolution laws of genetics. Thus, reproduction in genetics is represented by multiplication in algebra. Apart from that, regarding Markovian transition probabilities, the properties of algebras are associated with properties of Markov chains, which allows us to develop an algebra theory at deeper hierarchical levels than standard algebras. After introducing several new algebraic concepts, evolution algebras provide a theoretical framework to unify many phenomena. Among the further research topics related to evolution algebras and other fields, the most significant topic perhaps is to develop a continuous evolution algebra theory for continuous time dynamical systems . . . Acknowledgements The authors want to thank the referee for the helpful comments and useful suggestions, which have allowed us to improve the quality of this paper. 20 References: [1] Tian, J.P., Evolution Algebras and their Applications, Lecture Notes in Mathematics, Vol 1921. Springer-Verlag, Berl´ ın, 2008. [2] Tian, J.P. and Vojtechovsky, P., Mathematical concepts of evolution algebras in non-mendelian genetics, Quasigroups Related Systems 14:1 (2006), 111- 122. [3] Tian, J.P. and Xiao S.L., Continuous-time Markov process on graphs, Stochastic Analysis and Applications 24:5 (2006), 953-972. [4] Isaacson, D. and Madsen, R. Markov Chains Theory and Applications, John Wiley and Sons, New York, 1976. [5] Mendel, G., Experiments in plant-hybridization, Classic Papers in Genetics, Prentice-Hall Inc. 1959. [6] Serebrowsky, A., On the properties of the Mendelian equations, Doklady A.N.SSSR. 2(1934), 33-36 (in Russian). [7] Glivenkov, V., Algebra Mendelienne, Comptes rendus (Doklady) de Acad. des Sci. de URSS 4:13 (1936), 385-386 (in Russian). [8] Kostitzin, V.A., Sur les coefficients mendeliens d’heredite, Comptes rendus de Acad. des Sci. 206 (1938), 883-885. [9] Etherington, I.M.H., Non-associative algebra and the symbolism of genetics, Proc. Roy. Soc. Edinburgh B 61 (1941), 24-42. [10] Nakanishi, N., Graph Theory and Feynman Integrals. Gordon and Breach Science Publishers, New York, 1971. [11] Clark, J. and Holton, D.A. A first look at Graph Theory, World Scientific, 1991. [12] Boza, L., Fedriani, E.M., N´ u˜ nez, J., Pacheco, A.M. and Villar, M.T., Directed Pseudographs and Lie Algebras over Z/3Z, Programme and Abstracts of the 22nd British Combinatorial Conference (BCC 2009), University of St. Andrews, 5 - 10th July 2009, 57. [13] N´ u˜ nez, J., Pacheco, A.M. and Villar, M.T., Study of a family of Lie algebras over Z/3Z,International Journal of Mathematics and Statistics (IJMS), Special volume 7:W10 (2010), 40-45. 21 [14] Erd¨ os, P. L., Mikl´ os, I. and Toroczkai, Z. A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs. The Electronic Journal of Combinatorics 17 (2010) ]R66, 1-10. [15] Hakimi, S. L., On the realizability of a set of integers as degrees of vertices of a graph. SIAM J. Appl. Math. 10 (1962), 496-506. 22