Chordal graphs are an important class of perfect graphs. The beautiful theory surrounding their study varies from natural applications to elegant characterizations in terms of forbidden subgraphs, subtree representations, vertex orderings, and to linear time recognition algorithms. Haskins and Rose introduced the class of chordal digraphs as a digraph analogue of chordal graphs. Chordal digraphs can be defined in terms of vertex orderings and several results about chordal graphs can be extended to chordal digraphs. However, a forbidden subdigraph characterization of chordal digraphs is not known and finding such a characterization seems to be a difficult problem. Meister and Telle studied semi-complete chordal digraphs and gave a forbidden subdigraph characterization of this class of digraphs. In this thesis, we study chordal digraphs within the classes of quasi-transitive, extended semi-complete, and locally semi-complete digraphs. For each of these classes we obtain a forbidden subdigraph characterization of digraphs which are chordal. We also introduce in this thesis a new variant of chordal digraphs called semi-strict chordal digraphs. We obtain a forbidden subdigraph characterization of semi-strict chordal digraphs for each of the classes of semi-complete, quasi-transitive, extended semi-complete, and locally semi-complete digraphs. / Graduate

No description available.

No description available.

This paper discusses the direct product cancellation of digraphs. We define the exact conditions on G such that GxK=HxK implies G=H. We focus first on simple equations such as GxK_2=HxK_2 where K_2 denotes a single arc and then extend this to the more general situation, GxK = HxK. Our results are achieved by using a “factorial” operation on graphs, which is in some sense analogous to the factorial of an integer.

We focus on first-order definability in the quasiordered class of finite digraphs ordered by embeddability. At first we will prove definability of each digraph up to size three. We will need to add to the quasiorder structure some digraphs as constants, so we try to find the needed set of constants as small as possible with small digraph as well. Gradually we make instruments that we can use to express the inner structure of each digraphs in the language of embeddability. At the end we investigate definability in the closely related lattice of universal classes of digraphs. We show that the set of finitely generated and also the set of finitely axiomatizable universal classes are definable subsets of the lattice.

In 1997, Drs. G. R. Blakley and I. Borosh published two papers whose stated purpose was to present a general formulation of the notion of a code that depends only upon a code's structure and not its functionality. In doing so, they created a further generalization--the idea of a precode. Recently, Drs. Blakley, Borosh, and A. Klappenecker have worked on interpreting the structures and results in these pioneering papers within the framework of category theory. The purpose of this dissertation is to further the above work. In particular, we seek to accomplish the following tasks within the ``general theory of codes.' 1. Rewrite the original two papers in terms of the alternate representations of precodes as bipartite digraphs and Boolean matrices. 2. Count various types of bipartite graphs up to isomorphism, and count various classes of codes and precodes up to isomorphism. 3. Identify many of the classical objects and morphisms from category theory within the categories of codes and precodes. 4. Describe the various ways of constructing a code from a precode by ``splitting' the precode. Identify important properties of these constructions and their interrelationship. Discuss the properties of the constructed codes with regard to the factorization of homomorphisms through them, and discuss their relationship to the code constructed from the precode by ``smashing.' 5. Define a parametrization of a precode and give constructions of various parametrizations of a given precode, including a ``minimal' parametrization. 6. Use the computer algebra system, Maple, to represent and display a precode and its companion, opposite, smash, split, bald-split, and various parametrizations. Implement the formulae developed for counting bipartite graphs and precodes up to isomorphism.

Research Doctorate - Doctor of Philosophy (PhD) / Interconnection networks form an important research area which has received much attention, both in theoretical research and in practice. Design of interconnection networks is much concerned with the topology of networks. The topology of a network is usually studied in terms of extremal graph theory. Consequently, from the extremal graph theory point of view, designing the topology of a network involves various extremal graph problems. One of these problems is the well-known fundamental problem called the degree/diameter problem, which is to determine the largest (in terms of the number of vertices) graphs or digraphs of given maximum degree and given diameter. General upper bounds, called Moore bounds, exist for the largest possible order of such graphs and digraphs of given maximum degree ∆ (respectively, out-degree d) and diameter D. However, quite a number of open problems regarding the degree/diameter problem do still exist. Some of these problems, such as constructing a Moore graph of degree ∆ = 57 and diameter D = 2, have been open for over 50 years. Another extremal graph problem regarding the design of the topology of a network is called the construction of EX graphs, which is to obtain graphs of the largest size (in terms of the number of edges), given order and forbidden cycle lengths. In this thesis, we obtain large graphs whose sizes either improve the lower bound of the size of EX graphs, or even reach the optimal value. We deal with designing the topology of a network, but we are also interested in the issue of fault tolerance of interconnection networks. This leads us to another extremal graph problem, that is, connectivity. In this thesis, we provide an overview of the current state of research in connectivity of graphs and digraphs. We also present our contributions to the connectivity of general regular graphs with small diameter, and the connectivity of EX graphs.

We consider the computational complexity of evaluating the Tutte polynomial of three particular classes of greedoid, namely rooted graphs, rooted digraphs and binary greedoids. Furthermore we construct polynomial-time algorithms to evaluate the Tutte polynomial of these classes of greedoid when they're of bounded tree-width. We also construct a Möbius function formulation for the characteristic polynomial of a rooted graph and determine the computational complexity of computing the coefficients of the Tutte polynomial of a rooted graph.

Le but principal de cette thèse est de présenter des conditions suffisantes pour garantir l'existence de subdivisions dans les graphes dirigés. Bien que ce genre de questions soit assez bien maitrisé dans le cas des graphes non orientés, très peu de résultats sont connus sur le sujet des graphes dirigés. La conjecture la plus célèbre du domaine est sans doute celle attribuée à Mader en 1985 qui dit qu'il existe une fonction f tel que tout graphe dirigé de degré sortant minimal supérieur à f(k) contient le tournoi transitif sur k sommets comme subdivision. Cette question est toujours ouverte pour k=5. Cette thèse présente quelques résultats intermédiaires tendant vers cette conjecture. Il y est d'abords question de montrer l'existence de subdivisions de graphes dirigés autre que les tournois, en particulier les arborescences entrantes. Il y a aussi la preuve que les graphes dirigés de grand degré sortant contiennent des immersions de grand tournois transitifs, question qui avait été posée en 2011 par DeVos et al. En regardant un autre paramètre, on montre aussi qu'un grand nombre chromatique permet de forcer des subdivisions de certains cycles orientés, ainsi que d'autre structures, pour des graphes dirigés fortement connexes. Cette thèse présente également la preuve de la conjecture de Erd\H{o}s-Sands-Sauer-Woodrow qui dit que les tournois dont les arcs peuvent être partitionnés en k graphes dirigés transitifs peuvent être dominé par un ensemble de sommet dont la taille dépend uniquement de k. Pour finir, cette thèse présente la preuve de deux résultats, un sur l'orientation des hypergraphes et l'autre sur la coloration AVD,utilisant la technique de compression d'entropie. / The main purpose of the thesis was to exhibit sufficient conditions on digraphs to find subdivisions of complex structures. While this type of question is pretty well understood in the case of (undirected) graphs, few things are known for the case of directed graphs (also called digraphs). The most notorious conjecture is probably the one due to Mader in 1985. He asked if there exists a function f such that every digraph with minimum outdegree at least f(k) contains a subdivision of the transitive tournament on k vertices. The conjecture is still wide open as even the existence of f(5) remains open. This thesis presents some weakening of this conjecture. Among other results, we prove that digraphs with large minimum outdegree contain large in-arborescences. We also prove that digraphs with large minimum outdegree contain large transitive tournaments as immersions, which was conjectured by DeVos et al. in 2011. Changing the parameter, we also prove that large chromatic number can force subdivision of cycles and other structures in strongly connected digraphs. This thesis also presents the proof of the Erd\H{o}s-Sands-Sauer-Woodrow conjecture that states that the domination number of tournaments whose arc set can be partitioned into k transitive digraphs only depends on k. The conjecture, asked in 1982, was still open for k=3. Finally this thesis presents proofs for two results, one about orientation of hypergraphs and the other about AVD colouring using the recently developed probabilistic technique of entropy compression.

Nesta tese estudamos dois problemas em digrafos: um problema de empacotamento e um problema de contagem. Estudamos o problema de empacotamento máximo de arborescências no digrafo aleatório D(n,p), onde cada possvel arco é inserido aleatoriamente ao acaso com probabilidade p = p(n). Denote por (D(n,p)) o maior inteiro possvel 0 tal que, para todo 0 l , temos ^(l-1)_i=0 (l-i)|{v in d^in(v) = i}| Provamos que a quantidade máxima de arborescências em D(n,p) é (D(n,p)) assintoticamente quase certamente. Nós também mostramos estimativas justas para (D(n, p)) para todo p [0, 1]. As principais ferramentas que utilizamos são relacionadas a propriedades de expansão do D(n, p), o comportamento do grau de entrada do digrafo aleatório e um resultado clássico de Frank que serve como ligação entre subpartições em digrafos e a quantidade de arborescências. Para o problema de contagem, estudamos a densidade de subtorneios fortemente conexos com 5 vértices em torneios grandes. Determinamos a densidade assintótica máxima para 5 torneios bem como as famlias assintóticas extremais de cada torneios. Como subproduto deste trabalho caracterizamos torneios que são blow-ups recursivos de um circuito orientado com 3 vértices como torneios que probem torneios especficos de tamanho 5. Como principal ferramenta para esse problema utilizados a teoria de álgebra de flags e configurações combinatórias obtidas através do método semidefinido. / In this thesis we study two problems dealing with digraphs: a packing problem and a counting problem. We study the problem of packing the maximum number of arborescences in the random digraph D(n,p), where each possible arc is included uniformly at random with probability p = p(n). Let (D(n,p)) denote the largest integer 0 such that, for all 0 l , we have ^(l-1)_i=0 (l-i)|{v in d^in(v) = i}|. We show that the maximum number of arc-disjoint arborescences in D(n, p) is (D(n, p)) asymptotically almost surely. We also give tight estimates for (D(n, p)) for every p [0, 1]. The main tools that we used were expansion properties of random digraphs, the behavior of in-degree of random digraphs and a classic result by Frank relating subpartitions and number of arborescences. For the counting problem, we study the density of fixed strongly connected subtournaments on 5 vertices in large tournaments. We determine the maximum density asymptotically for five tournaments as well as unique extremal sequences for each tournament. As a byproduct of this study we also characterize tournaments that are recursive blow-ups of a 3-cycle as tournaments that avoid three specific tournaments of size 5. We use the theory of flag algebras as a main tool for this problem and combinatorial settings obtained from semidefinite method.