abstract: A tiling is a collection of vertex disjoint subgraphs called tiles. If the tiles are all isomorphic to a graph $H$ then the tiling is an $H$-tiling. If a graph $G$ has an $H$-tiling which covers all of the vertices of $G$ then the $H$-tiling is a perfect $H$-tiling or an $H$-factor. A goal of this study is to extend theorems on sufficient minimum degree conditions for perfect tilings in graphs to directed graphs. Corrádi and Hajnal proved that every graph $G$ on $3k$ vertices with minimum degree $delta(G)ge2k$ has a $K_3$-factor, where $K_s$ is the complete graph on $s$ vertices. The following theorem extends this result to directed graphs: If $D$ is a directed graph on $3k$ vertices with minimum total degree $delta(D)ge4k-1$ then $D$ can be partitioned into $k$ parts each of size $3$ so that all of parts contain a transitive triangle and $k-1$ of the parts also contain a cyclic triangle. The total degree of a vertex $v$ is the sum of $d^-(v)$ the in-degree and $d^+(v)$ the out-degree of $v$. Note that both orientations of $C_3$ are considered: the transitive triangle and the cyclic triangle. The theorem is best possible in that there are digraphs that meet the minimum degree requirement but have no cyclic triangle factor. The possibility of added a connectivity requirement to ensure a cycle triangle factor is also explored. Hajnal and Szemerédi proved that if $G$ is a graph on $sk$ vertices and $delta(G)ge(s-1)k$ then $G$ contains a $K_s$-factor. As a possible extension of this celebrated theorem to directed graphs it is proved that if $D$ is a directed graph on $sk$ vertices with $delta(D)ge2(s-1)k-1$ then $D$ contains $k$ disjoint transitive tournaments on $s$ vertices. We also discuss tiling directed graph with other tournaments. This study also explores minimum total degree conditions for perfect directed cycle tilings and sufficient semi-degree conditions for a directed graph to contain an anti-directed Hamilton cycle. The semi-degree of a vertex $v$ is $min{d^+(v), d^-(v)}$ and an anti-directed Hamilton cycle is a spanning cycle in which no pair of consecutive edges form a directed path. / Dissertation/Thesis / Ph.D. Mathematics 2013

Indiana University-Purdue University Indianapolis (IUPUI) / Subnetwork or path mining is an emerging data mining problem in many areas including scientific and commercial applications. Graph modeling is one of the effective ways in representing real world networks. Many natural and man-made systems are structured in the form of networks. Traditional machine learning and data mining approaches assume data as a collection of homogenous objects that are independent of each other whereas network data are potentially heterogeneous and interlinked. In this paper we propose a novel algorithm to find subnetworks and Maximal paths from a weighted, directed network represented as a graph. The main objective of this study is to find meaningful Maximal paths from a given network based on three key parameters: node weight, edge weight, and direction. This algorithm is an effective way to extract Maximal paths from a network modeled based on a user’s interest. Also, the proposed algorithm allows the user to incorporate weights to the nodes and edges of a biological network. The performance of the proposed technique was tested using a Colorectal Cancer biological network. The subnetworks and paths obtained through our network mining algorithm from the biological network were scored based on their biological significance. The subnetworks and Maximal paths derived were verified using MetacoreTM as well as literature. The algorithm is developed into a tool where the user can input the node list and the edge list. The tool can also find out the upstream and downstream of a given entity (genes/proteins etc.) from the derived Maximal paths. The complexity of finding the algorithm is found to be O(nlogn) in the best case and O(n^2 logn) in the worst case.

A new connection between combinatorics and noncommutative algebra is established by relating a certain class of directed graphs to noncommutative Koszul algebras. The directed graphs in this class are called full graphs and are defined by a set of criteria on the edges. The structural properties of full graphs are studied as they relate to the edge criteria. A method is introduced for generating a Koszul algebra Lambda from a full graph G. The properties of Lambda are examined as they relate to the structure of G, with special attention being given to the construction of a projective resolution of certain semisimple Lambda-modules based on the structural properties of G. The characteristics of the Koszul algebra Lambda that is derived from the product of two full graphs G' and G' are studied as they relate to the properties of the Koszul algebras Lambda' and Lambda' derived from G' and G'. / Ph. D.

Graph augmentation concerns the addition of edges to a graph to satisfy some connectivity property of a graph. Previous research in this field has been preoccupied with edge augmentation; however the research in this document focuses on the addition of vertices to a graph to satisfy a specific connectivity property: ensuring that all the nodes of the graph are contained within cycles. A distinction is made between graph augmentation (edge addition), and graph enlargement (vertex addition). This document expands on previous research into a graph matching problem known as the “shoe matching problem” and the role of a graph enlargement algorithm in finding this solution. The aim of this research was to develop new and efficient algorithms to solve the graph enlargement problem as applied to the shoe matching problem and to improve on the naïve algorithm of Sanders. Three new algorithms focusing on graph enlargement and the shoe matching problem are presented, with positive results overall. The new enlargement algorithms: cost-optimised, matrix, and subgraph, succeeded in deriving the best result (least number of total nodes required) in 37%, 53%, and 57% of cases respectively (measured across 120 cases). In contrast, Sanders’s algorithm has a success rate of only 20%; thus the new algorithms have a varying success rate of approximately 2 to 3 times that of Sanders’s algorithm. / Computing / M. Sc. Computing

Typescript (photocopy). / Digitized by Kansas Correctional Industries

This paper uncovers the relationship between stock markets and exchange rates in seven countries by employing stable aggregate currency (SAC) for the period of 1973- 2004. Ordinary Least Squares (OLS) regression, time series methods, and directed acyclic graphs are applied to the daily data on stock market indices and exchange rates. The findings based on regression analysis show that exchange rate exposure of stock markets is statistically significant when stock indexes in SAC are used. Using an innovation accounting technique, we confirm that stock markets and exchange rates are correlated. Moreover, in most cases stock markets are more exogenous than foreign currency markets, which explains the relatively high percentage of uncertainty in the foreign currency market. Overall, SAC-based models give relatively more accurate and robust results than those which employ stock indices in local currencies, because it is more accurate to convert both variables into the same denominator.

Thesis (B.A.)--Haverford College, Dept. of Computer Science, 2004. / Includes bibliographical references.

Thesis (Ph. D.)--University of Washington, 2005. / Vita. Includes bibliographical references (p. 94-95).

Graphs are mathematical abstractions that are useful for solving many types of problems in computer science. In this dissertation, when we talk of graphs we refer to directed graphs (digraphs), which consist of a set of nodes and a set of edges between the nodes, where each edge has a direction. Numerous implementations of graphs exist in computer science however, there is a need for more systematic and complete categorisation of implementations together with some proof of correctness. Completeness is an issue because other studies only tend to discuss the useful implementations and completely or partially ignore the rest. There is also a need for a treatment of graph representations using triples instead pairs as the base component. In this dissertation, a solution to each of these deficiencies is presented. This dissertation is a taxonomic approach towards a comprehensive treatment of digraph representations. The difficulty of comparing implementations with each other is overcome by a creating a taxonomy of digraph implementations. Taxonomising digraph representations requires a systematic analysis of the two main building blocks of digraphs implementations namely maps and sets. The analysis presented in the first part of the dissertation includes a definition of the abstract data types to represent maps and sets together with a comprehensive and systematic collection of algorithms and data-structures required for the implementations thereof. These algorithms are then written and re-written in a common notation and are examined for any essential com¬ponents, differences, variations and common features. Based on this analysis the maps and sets taxonomies are presented. After the completion of maps and sets implementation foundations the dissertation continues with the main contribution: a systematic collection and implementation of other operators used for the manipulation of the base triple components of digraphs and the derivation of the the final taxonomy of digraphs by integrating the maps and sets implementations with the operators on the sets of triples. With the digraph taxonomy we can finally see relationships between implementations and we also can easily establish their similarities and differences. Furthermore, the taxonomy is also useful for further discussions, analysis and visualisation of the complete implementation topography of digraph implementations. / Dissertation (MSc (Computer Science))--University of Pretoria, 2006. / Computer Science / unrestricted

This thesis concerns an active research area within fractal geometry. In the first part, in Chapters 2 and 3, for directed graph iterated function systems (IFSs) defined on ℝ, we prove that a class of 2-vertex directed graph IFSs have attractors that cannot be the attractors of standard (1-vertex directed graph) IFSs, with or without separation conditions. We also calculate their exact Hausdorff measure. Thus we are able to identify a new class of attractors for which the exact Hausdorff measure is known. We give a constructive algorithm for calculating the set of gap lengths of any attractor as a finite union of cosets of finitely generated semigroups of positive real numbers. The generators of these semigroups are contracting similarity ratios of simple cycles in the directed graph. The algorithm works for any IFS defined on ℝ with no limit on the number of vertices in the directed graph, provided a separation condition holds. The second part, in Chapter 4, applies to directed graph IFSs defined on ℝⁿ . We obtain an explicit calculable value for the power law behaviour as r → 0⁺ , of the qth packing moment of μ[subscript(u)], the self-similar measure at a vertex u, for the non-lattice case, with a corresponding limit for the lattice case. We do this (i) for any q ∈ ℝ if the strong separation condition holds, (ii) for q ≥ 0 if the weaker open set condition holds and a specified non-negative matrix associated with the system is irreducible. In the non-lattice case this enables the rate of convergence of the packing L[superscript(q)]-spectrum of μ[subscript(u)] to be determined. We also show, for (ii) but allowing q ∈ ℝ, that the upper multifractal q box-dimension with respect to μ[subscript(u)], of the set consisting of all the intersections of the components of F[subscript(u)], is strictly less than the multifractal q Hausdorff dimension with respect to μ[subscript(u)] of F[subscript(u)].