Search

The file attached to this record is the author's final peer reviewed version. The Publisher's final version can be found by following the DOI link. Complexity in water distribution systems (WDSs) poses a challenge for analysis and management of the systems. To reduce the complexity, the recent development of complex network science provides a system decomposition technique that converts a complex WDS with a large number of components into a simple system with a set of interconnected modules. Each module is a subsystem with stronger internal connections than external connections. Thus far, the topological features of the modular structure in WDS have been extensively studied but not the behavioural features, e.g. the hydraulic interdependencies among modules. Therefore, this paper aims to quantitatively measure and graphically visualize the module interdependency in WDSs, which helps understanding the behavioural complexity of WDSs and thus various WDS analyses, such as pipe maintenance, model calibration, rehabilitation, and District Metered Areas planning. Specifically, this study first identifies the WDS’s modular structure then measures how changes in the state of one module (i.e. any single pipe failure or perturbed demand within each module) affect the state of another module. Modular interdependencies are summarized in an interdependency matrix and visualized by the digraph. Four real-world systems are analysed, and three of them shows low interdependencies among most of the modules and there are only a few critical modules whose status changes will substantially affect a number of other modules. Hence, highly interconnected topologies may not result in strong and complex module interdependency, which is a fact that simplifies several WDS analysis for practical applications as discussed in this paper.

We show that the line digraph technique, when iterated, provides dense digraphs, that is, with asymptotically large order for a given diameter (or with small diameter for a given order). This is a well-known result for regular digraphs. In this note we prove that this is also true for non-regular digraphs. This research is supported by projects MINECO MTM2014-60127-P, and 2014SGR1147 of the Catalan Government. This research has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922.

Flowsheeting can be represented by solving a system of nonlinear algebraic equations. The equation-oriented (EO) approach is an important method of process flowsheeting. The EO model, however, can be difficult to solve simultaneously because of the complexity caused by large-scale equations. In this study, a scheme based on the digraph method and Grobner basis is proposed to simplify EO models. By depicting an EO model as a digraph, the equations to be simultaneously solved form a loop in the digraph. To simplify the solving of an EO model, finding the digraph with the least loops is recommended. Topological sorting, depth-first traversal, and back-off-edge judgement are introduced to evaluate the digraph structure. The Grobner basis, an important symbolic computation approach, is used to further eliminate simultaneous equations or indifferent intermediate variables. A representative numerical case study illustrates that the proposed method efficiently reduces the computation cost of EO models.

In this paper, we investigate isomorphic factorizations of the Kronecker product graphs. Using these relations, it is shown that (1) the Kronecker product of the d-out-regular digraph and the complete symmetric digraph is factorized into the line digraph, (2) the Kronecker product of the Kautz digraph and the de Bruijn digraph is factorized into the Kautz digraph, (3) the Kronecker product of binary generalized de Bruijn digraphs is factorized into the binary generalized de Bruijn digraph.

A well-known Theorem of Vizing states that one can colour the edges of a graph by Δ + α colours, such that edges of the same colour form a matching. Here, Δ denotes the maximum degree of a vertex, and α the maximum multiplicity of an edge in the graph. An analogue of this Theorem for directed graphs was proved by Frank. It states that one can colour the arcs of a digraph by Δ + α colours, such that arcs of the same colour form a branching. For a digraph, A denotes the maximum indegree of a vertex, and a the maximum multiplicity of an arc. We prove a common generalization of the above two theorems concerning the colouring of mixed graphs (these are graphs having both directed and undirected edges) in such a way that edges of the same colour form a matching forest.

Let D = ( V , A ) be a digraph with minimum in-degree at least 1 and girth at least l + 1 , where l ≥ 1 . In this work, the following result is proved: a digraph D has a ( k , l ) -kernel if and only if its partial line digraph L D does, where 1 ≤ l k . As a consequence, the h -iterated line digraph L h ( D ) is shown to have a kernel if and only if D has a kernel.

The scrambling index of a primitive digraph D is the smallest positive integer k such that for every pair of vertices u and v , there is a vertex w such that we can get to w from u and v in D by directed walks of length k ; it is denoted by k(D) . In [M. Akelbek, S. Kirkland, Coefficients of ergodicity and the scrambling index, preprint] we gave the upper bound on k(D) in terms of the order and the girth of a primitive digraph D . In this paper, we characterize all the primitive digraphs such that the scrambling index is equal to the upper bound.

We are considering sequential membrane systems and molecular dynamics from the viewpoint of Markov chain theory. The configuration space of these systems (including the transitions) is a special kind of directed graph, called a pseudo-lattice digraph, which is closely related to the stoichiometric matrix. Taking advantage of the monoidal structure of this space, we introduce the algebraic notion of precycle. A precycle leads to the identification of cycles by means of the concept of defect, which is a set of geometric constraints on configuration space. Two efficient algorithms for evaluating precycles and defects are given: one is an algorithm due to Contejean and Devie, the other is a novel branch-and-bound tree search procedure. Cycles partition configuration space into equivalence classes, called the communicating classes. The structure of the communicating classes in the free regime–where all rules are enabled–is analyzed: testing for communication can be done efficiently. We show how to apply these ideas to a biological regulatory system.

Publisher Summary This chapter provides an overview of the concept of distances in graph theory. A graph is a pair G = (V, E), where V is a set, called set of vertices of the graph G, and E is a set of unordered pairs of vertices, called edges of the graph G. A directed graph (or digraph) is a pair D = (V, E), where V is a set, called set of vertices of the digraph D, and E is a set of ordered pairs of vertices, called arcs of the digraph D. A graph, in which at most one edge may connect any two vertices, is called simple graph. If multiple edges are allowed between vertices, the graph is called multigraph. The graph is called finite (infinite) if the set V of its vertices is finite (infinite, respectively). The order of a finite graph is the number of its vertices; the size of a finite graph is the number of its edges. The chapter also discusses concepts related to distances on vertices of a graph, distance-defined graphs, and distances on trees.

Non-parametric statistical pattern recognition algorithms, such as nearest neighbor algorithms, typically present a trade off between performance and complexity. Here “complexity” refers to computational complexity, which has implications for the size of data sets that can be processed. We present a methodology for the selection of prototypes for a graph-theoretical classifier, the class cover catch digraph. These prototypes, along with certain associated parameters, define the classifier. The methodology is illustrated on several simulated data sets and on two applications: the Sloan Digital Sky Survey and a text classification problem.

We address some complexity questions related to the arc-coloring of directed hypergraphs. Such hypergraphs arise as a generalization of digraphs, by allowing the tail of each arc to consist of more than one node. The related arc-coloring extends the notion of digraph arc-coloring, which has been studied by diverse authors. Using two classical results we easily prove that the optimal coloring of a digraph, as well as the 2-coloring test for every directed hypergraph, require polynomial time. Instead, the k-colorability problem for some fixed degree d is shown to be NP-complete if k⩾d⩾2 and k⩾3, even if the input is restricted to the so-called non-overlapping hypergraphs. We also describe a sub-class of hypergraphs for which the 3-colorability test is polynomially decidable. Some results are rephrased and proved using suitable adjacency matrices, namely walls.

Publisher Summary This chapter gives a detailed account of digraphs (or directed graphs) which is a special class of graphs that represent finite relations geometrically. It provides an understanding of the basic terminology of digraphs and explores weighted digraphs and dags. Both finite relations and digraphs can be implemented in a computer using adjacency matrices and linked lists. Digraphs have applications in computer science, linguistics, genetics, the social sciences, sports, and management science. Vertices with indegrees and outdegrees and the reachability factor stand out among the basic features of digraphs. A digraph consists of a nonempty finite set V of points (called vertices or nodes) and a set E of directed edges joining them. A directed edge from vertex x to vertex y is denoted by the ordered pair. The vertex x is the initial vertex and y is the terminal vertex of the edge. Vertex x is an immediate predecessor of vertex y and y an immediate successor of x. A digraph may have loops but no parallel edges; at the most one edge exists between any two vertices. Every edge in a digraph is unidirectional and the edges in a digraph are never parallel, but always directed.

This chapter discusses that a model of the processor, although can be tested in a stand-alone fashion, does not really come to life until it is coupled with a module capable of providing it input and observing its output. An experimental frame module is a coupled-model, which when coupled to a model, generates input external events, monitors its running, and processes its output .The design of an experimental frame reflects the objectives one has in experimenting with a model. Thus, the same model is coupled to different experimental frame modules that observe it under different conditions. Conversely, the same experimental frame module may be employed to experiment with different models under the same conditions. The chapter explains the way to construct an experimental frame module to measure turnaround time and throughput in any of the simple computer architecture models. A discrete event system specification (DEVS)-Scheme simulation displays all the messages as they are processed. This aids understanding of the simulation process. With regard to model verification, it permits step-by-step tracking of the events, and hence, makes for quicker discovery of sources of error.

Let D be a digraph with n vertices: we give sufficient conditions and conjectures on the number of arcs of D to insure that D has a directed cycle or a directed path of given length l , with more emphasis on the cases l = n, n - 1 or l small. We study the case where D is any digraph and the case where D is strong.

A digraph is said to be k-ply hamiltonian if it admits k arc-disjoint Hamilton circuits. In this paper we determine when the Cayley digraph Cay(S) is 2-ply hamiltonian in the case where S is a two-element generating set for an abelian group. This result has several applications; for example, it can be used to determine when the Cartesian product DC r × DC s of two circuits is decomposable into two Hamilton circuits. We also study infinite digraphs, and characterize those infinite vertex transitive digraphs which can be decomposed into an infinite number of Hamilton paths.

Publisher Summary This chapter presents a stochastic compartmental model of preinfarction angina. A stochastic compartmental model (a Markov model with continuous time parameter) is used to estimate the illness–death transitions. The digraph (directed graph) of the model is a flow chart that shows the compartments (boxes) and the transfers (segments) between them. The digraph must be realistic and should contain a sufficient number of compartments and transfers to answer the question of interest. If the model is too complicated, then it may not be possible to estimate all of the model parameters. With an illness–death process, at least two illness compartments (transient states) are required, one to represent the high-risk (critical) state and another to represent the low-risk (stable) state. The transfer from the critical state to the stable state is called recovery and the transfer from stable to critical is called relapse. For the purposes of this study, the disease of interest is preinfarction angina. The chapter presents a flow diagram depicting transitions through disease states. It also discusses the lumped model.

This chapter discusses the Cayley graphs. Cayley gave the visualization of the multiplication table of a finite group H, which is called “a Cayley diagram.” This is a digraph having one vertex for each element of H, where it is convenient to use the same symbol for an element and its corresponding vertex. With each generator R i of H, a certain set of directed and colored edges is associated, the direction is indicated by an arrow, and the subscript i of the generator is indicated by using the i th color. Two vertices, P and Q, are joined by an edge of the i th color and directed from P to Q. If n 1 is the period of R 1 , the edges showing the first color form cyclically directed n 1 -gons. However, to avoid 2-circuits consisting of two oppositely directed edges joining the same two vertices, single undirected edge should be used whenever a generator is involutory.

Let p be a prime. We prove that every vertex transitive digraph of order pk, k ≤ 3 is a Cayley digraph and we construct a non-Cayley vertex transitive graph of order pk for each k ≥ 4. We prove that every connected vertex transitive graph of order pk, K ≤ 3, is hamiltonian.

In this article we determine a number of arcs guaranteeing the existence of a path of length l in an oriented graph (or antisymmetric digraph) which is strong or not. The given condition is shown to be best possible except for a strong oriented graph with strictly more than 2l -2 vertices, in which case we suggest a conjecture.

We answer a question of B. Bollobas and we determine the minimum number of arcs in a diagraph with given minimum indegree and outdegree guaranteeing this digraph to be Hamiltonian or strongly Hamilton-connected.

Publisher Summary The digraphs considered in the chapter have multiple edges and loops. The outdegree and the indegree of a vertex x in D are denoted by d + (x; D) and d - (x; D), respectively. V (D) and E (D) are the mean the vertex set and the edge set of D. The maximum number of edge-disjoint paths from x to y in D is denoted by λ (x, y ; D). It is considered that k i ɛ E (D) be an edge from x i to y i for i = 1,2, and y 1 = x 2 . Then D k l k 2 may arise from D by deleting k l and k 2 and by adding a new edge from xl to y2. Every finite n-edge-connected digraph is obtained from K 1 by alternately adding edges and applying 0 n .

Publisher Summary This chapter presents some results involving graphs and inverse semigroups that stimulate a wider study of graphs and semigroups. A graph D = (G, E) means a digraph such that the vertex-set V (D) = G and the arc-family A ( D ) = E⊆ G X G, is presented. An inverse semigroup is an ordered pair (S, . ), where S is a non-empty set and ‘ . ’ is a binary operation such that: ‘.’ is associative, and for every a ɛ S, there exists uniquely an a * ɛ S such that aa * a = a and a*aa* = a *. The chapter explores some inverse subsemigroup of Q, which possesses interesting properties. To do this, the concept of an ideal of a graph is introduced.

D(n,p), 2≤p≤n, n≥3, is the digraph with n vertices deduced from a directed cycle by changing the orientation of p - 1 consecutive edges. For every n and p, we give the minimum number of edges in the digraph D of order n, insuring the existence of D(n,p) in D.

In this article we study the minimum number of circuits covering the vertices of a strong digraph G denoted by c(G). We first prove that this parameter is not greater than the maximum order of an induced subdigraph of G without circuits. We give and study a conjecture in the case where the two parameters are equal. Then generalizing Meyniel's theorem we give conditions on the total degrees of the vertices of G implying a bound on c(G). in both studies we also consider the special case of antisymmetric digraphs. Dans cet article, nous etudions le nombre minimun de circuits couvrant les sommets d'un graphe oriente fortement connexe, et l'appelons c(G). Nous montrons d'abord que ce parametre est inferieur ou egal au nombre maximum de sommets d'un sous-graphe de G ne contenant pas de circuit. Nous donnons une conjecture dans le cas ou ces deux parametres sont egaux et I'etudions dans quelques cas. Ensuite, generalisant le theoreme de Meyniel, nous montrons que des conditions sur les degres des sommets de G donnent une borne sur c(G). A chaque fois, nous etudions le cas particulier des graphes antisymetriques.

This paper presents a method to design synchronized concurrent system which preserves well behaviour under all execution situations. Computational structures are developed with bipolar synchronisation scheme (BP-scheme) as its underlying digraph- BP-scheme is a variety of modified Petri nets and convertible with free choice net. Therefore much important properties of system designed with proposed methods Are inherented from net theory and can be expected without lengthly derivation. The design is program orientated. Basic structural components are developed in simple as well as macro–version. These components are adequate for program modelling of systems which inherent well behaviour of composed components. The model can be expressed in macro or microversions consistently to suit both the top—down and bottom–up design procedures. Examples are given to illustrate the method.

A directed graph G is said to be kernel-perfect if every G-subgraph possesses a kernel (= a stable dominating subset). Graphs without circuits, graphs without odd circuits are known to be kernel-perfect (Von Neumann and Morgenstern, and Richardson), and so are symmetric or transitive graphs. I present here the current state of research in kernel theory; the most significant results are the proofs of kernel-perfectness of G in each of the following cases: Theorem 2.2. G is a right- (or left-)pretransitive digraph. Theorem 3.3. (see [5]). Every odd circuit of G (not elementary in general) v 1 …v 2p+1 v 1 , possesses two crossing short chords (that means there exist two arcs of G of the form (v v u q+2 ) and (v q+1 , v q+3 ). Theorem 4.2. Every circuit of G possesses at least one symmetrical arc. Theorem 4.3. Every odd circuit of G possesses at least two symmetrical arcs. Theorems 3.3 and 4.3 are particuliar cases of an interesting conjecture proposed by H. Meyniel. Somes curious kernel-critical graphs are exhibited.

We study the connectivity of digraphs having a transitive group of automorphisms. As an application we prove that a vertex-transitive digraph of order n and degree 2r has girth not exceeding [n/r]. This result has the following consequence. Let G be a finite group of order n and S be a subset of G with cardinality s. Then 1 is the product of a sequence of elements of S with length not exceeding [n/s].

The authors continue their study of extremal problems of Turan type for directed graphs with multiple edges, now permitting any finite non-negative integer multiplicity. Having proved earlier (for the case of multiplicity at most 1) that there exists , for any family of “sample” digraphs, a matrix which represents the structure of an “asymptotically extremal sequence” of digraphs (containing none of the sample digraphs, and having a total number of arcs asymptotic to the maximum), they address themselves to the inverse problem: is every matrix so realized for some finite family of sample digraphs? They prove that this is indeed true for “dense” matrices - having certain integer entries, and such that an associated quadratic form attains its maximum for the standard simplex uniquely at an interior point.

Publisher Summary This chapter discusses structural models and graph theory. A structural model is a mathematical model for an empirical situation, which utilizes some aspect of graph theory, implicitly or explicitly. The realm of research activity is naturally divided into two worlds— the abstract and the empirical. The abstract world is generally regarded as the domain of the mathematician, logician, or purely theoretical physicist, while the empirical world is inhabited by experimental scientist of many varieties—physical, social, and others. In a confrontation between these two worlds, the mathematician's theorems become predictions about the real world, which can be tested by the scientist. If the predictions are entirely incorrect, the model cannot be used. The lower level of the abstract world deals with the foundations of mathematics, axioms, and logic. The chapter describes a few graph theoretic models in the social sciences and the theorems stemming from them. A connected functional digraph consists of exactly one directed cycle, together with a rooted tree oriented toward each point of the cycle.

We consider the problem of finding two disjoint directed paths with prescribed ends in a semicomplete digraph. The problem is NP - complete for general digraphs as proved in [4]. We obtain best possible sufficient conditions in terms of connectivity for a semicomplete digraph to be 2-linked (i.e., it contains two disjoint paths with prescribed ends for any four given endvertices). We also consider the algorithmically equivalent problem of finding a cycle through two given disjoint edges in a semicomplete digraph. For this problem it is shown that if D is a 5–connected semicomplete digraph, then D has a cycle through any two disjoint edges, and this result is best possible in terms of the connectivity. In contrast to this we prove that if T is a 3–connected tournament, then T has a cycle through any two disjoint edges. This is best possible, too. Finally we give best possible sufficient conditions in terms of local connectivities for a tournament to contain a cycle through af given pair of disjoint edges.

The Ferrers dimension dF(G) of a digraph G being the smallest number of Ferrers diagraphs whose intersection is G (the Ferrers dimension is known to generalize the poset dimension), two characterizations of dF(G) are given. In particular, the problem of finding the Ferrers dimension of a digraph is shown to be polynomially reducible to the problem of finding the threshold dimension of a graph.

The study applies nested arrays to previous works on the structure of systems on state-space form. The state-space form maps into a digraph, represented by a boolean matrix. Computational methods for potential controllability, cyclic components, loops, decomposition and piecewise eigenvalue calculation serve as examples. Data are kept in nested arrays and manipulated in the Nested Interactive Array Language (Nial). The nested array approach keeps subsystems distinct, and piecewise analyses can be done in parallel. The approach is more intuitive than previously possible.

Publisher Summary This chapter discusses structural models and graph theory. One approach to develop geometric models of complex systems is known as structural modeling. A structural model is any model that represents a complex system as a set of elements with relations linking some or all of them and places the emphasis on the geometry or structure rather than on quantitative aspects of the relationships. Thus, a structural model can usually be depicted as a graph or digraph. In building a structural model for a complex system, there are several distinct steps, each of which should be carried out systematically. From a structural model, conclusions can be derived in two ways: (1) by proving theorems about digraphs and applying them or (2) by plugging inputs into a computer. Both procedures give feedback to the model user, which can be used to modify the model and to give insights about the complex system.

This chapter focuses on the applications of graphs. A capacitated network—capacitated transportation network—is a quadruple 〈 A, Q, c, R + 〉, where 〈A, Q〉 is a digraph, R + is the set of nonnegative real numbers, and c: Q → R + is a function. The degree of a node is defined as the number of edges incident with it and subsets of nodes that have the same degree. If some nodes were still not matched, then new subsets would have to be generated. The order of a node is defined as the number of edges in the smallest circuit through this node. Subsets of nodes having the same order can be put in correspondence. If a node of G is already matched to a node of G*, then nodes that are the immediate neighbors of the identified nodes form corresponding subsets. In general, the algorithm terminates when every node in G has been paired off with a node in G * or when two corresponding subsets of nodes of G and G * are found to differ in the number of nodes they contain. If the former is the case, then graphs G and G * are isomorphic, but if it is the latter, then isomorphism is impossible. A further use of the citation digraph is in establishing the absolute importance of a document. Documents that are in little demand can be cleared from the open shelves to give readier access to those for which a strong demand exists. One measure of the importance of a document d k is the number of other documents that cite it directly or indirectly.

Publisher Summary This chapter describes graph theory. A directed graph—digraph, oriented graph—is the ordered pair D = 〈A, R〉, where A is a set of nodes—points, vertices—and R is a relation in A, that is, R is a set of ordered pairs, which are called arcs—lines, pointers. If G = 〈A, R〉 is a digraph, and Y is a subset of A, then digraph G' = 〈Y, (Y × Y) ⋂ R〉 is a subdigraph of G; it is a proper subdigraph if G ≠ G′. If Q is a subset of R, then a digraph G″ = 〈A, Q〉 is a partial digraph of G. The concept of a partial subdigraph is an obvious extension. In a digraph, node b is reachable from node a if there exists a path from a to b. If node a in digraph D is reachable from no other node in D and no other node is reachable from a, then a is an isolated node. However, a node that does not have zero indegree and does not lie on a cycle cannot belong to a node base. All node bases of a digraph have the same number of elements. Two digraphs are isomorphic if some permutation of the rows and corresponding columns in the adjacency matrix of one of the digraphs produces the adjacency matrix of the other, that is, isomorphic digraphs are identical except for the identifying names carried by their nodes.

Publisher Summary The labeled enumeration problems always appear to be much easier to solve than the corresponding unlabeled problems. For example, the number of labeled graphs is instantly found from first principles, while the determination of the number of unlabeled graphs requires a considerable amount of combinatorial theory, including Polya's Theorem. This chapter presents a selected sample of some of the outstanding and interesting solutions to labeled enumeration problems in graph theory, including the determination of the number of labeled graphs, connected graphs, blocks, eulerian graphs, fc-colored graphs, acyclic digraphs, trees, and eulerian trails in an eulerian digraph.

We give a method for constructing infinite families of dense (or eventually likely dense) Cayley digraphs of finite Abelian groups. The diameter of the digraphs is obtained by means of the related {\em minimum distance diagrams}. A {\em dilating} technique for these diagrams, which can be used for any degree of the digraph, is applied to generate the digraphs of the family. Moreover, two infinite families of digraphs with distinguished metric properties will be given using these methods. The first family contains digraphs with asymptotically large ratio between the order and the diameter as the degree increases (moreover it is the first known asymptotically dense family). The second family, for fixed degree $d=3$, contains digraphs with the current best known density.

© 2021 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/ In this paper, we deal with a simple geometric problem: Is it possible to partition a rectangle into k non-congruent rectangles of equal area? This problem is motivated by the so-called ‘Mondrian art problem’ that asks a similar question for dissections with rectangles of integer sides. Here, we generalize the Mondrian problem by allowing rectangles of real sides. In this case, we show that the minimum value of k for a rectangle to have a ‘perfect Mondrian partition’ (that is, with non-congruent equalarea rectangles) is seven. Moreover, we prove that such a partition is unique (up to symmetries) and that there exist exactly two proper perfect Mondrian partitions for k = 8. Finally, we also prove that any square has a perfect Mondrian decomposition for k = 7. The research of the first author has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922.

In this paper we study the edge-magicness of graphs with equal size and order, and we use such graphs and digraph products in order to construct labelings of different classes and of different graphs. We also study super edge-magic labelings of 2-regular graphs with exactly two components and their implications to other labelings. The strength of the paper lays on the techniques used, since they are not only used in order to provide labelings of many different types of families of graphs, but they also show interesting relations among well studied types of labelings. We are able to obtain, in this way, deep results relating different types of labelings. The research conducted in this document by the first and third authors has been supported by the Spanish Research Council under project MTM2011-28800-C02-01 and by the Catalan Research Council under grant 2009SGR1387.