Zugl.: Aachen, Techn. Hochsch., Diss., 2009

Techn. Hochsch., Diss., 2005--Aachen.

Seymour’s distance two conjecture states that in any digraph there exists a vertex (a “Seymour vertex”) that has at least as many neighbors at distance two as it does at distance one. We explore the validity of probabilistic statements along lines suggested by Seymour’s conjecture, proving that almost surely there are a “large” number of Seymour vertices in random tournaments and “even more” in general random digraphs.

No description available.

It is known that a Cayley digraph of an abelian group A is isomorphic to a nontrivial wreath product if and only if there is a proper nontrivial subgroup B of A such that the connection set without B is a union of cosets of B in A. We generalize this result to Cayley digraphs of nonabelian groups G by showing that such a digraph is isomorphic to a nontrivial wreath product if and only if there is a proper nontrivial subgroup H of G such that S without H is a union of double cosets of H in G. This result is proven in the more general situation of a double coset digraph (also known as a Sabidussi coset digraph.) We then give applications of this result which include obtaining a graph theoretic definition of double coset digraphs, and determining the relationship between a double coset digraph and its corresponding Cayley digraph. We further expand the result obtained for double coset digraphs to a collection of bipartite graphs called bi-coset graphs and the bipartite equivalent to Cayley graphs called Haar graphs. Instead of considering when this collection of graphs is a wreath product, we consider the more general graph product known as an X-join by showing that a connected bi-coset graph of a group G with respect to some subgroups L and R of G is isomorphic to an X-join of a collection of empty graphs if and only if the connection set is a union of double cosets of some subgroups N containing L and M containing R in G. The automorphism group of such -joins is also found. We also prove that disconnected bi-coset graphs are always isomorphic to a wreath product of an empty graph with a bi-coset graph.

In this dissertation, we study the following two topics, i.e., the union closed set conjecture and the maximum edges cut in connected digraphs. The union-closed-set-conjecture-topic goes as follows. A finite family of finite sets is {\it union closed} if it contains the union of any two sets in it. Let $X_{\mathcal{F}}=\cup_{F\in\mathcal{F}}F$. A union closed family of sets is {\it separating} if for any two distinct elements in $\mathcal{F}$, there is a set in $\mathcal{F}$ containing one of them, but not the other and there does not exist an element which is contained in every set of it. Note that any union closed family $\mathcal{F}$ is a poset with set inclusion as the partial order relation. A separating union closed family $\mathcal{F}$ is {\it irreducible} ({\it normalized}) if $|X_{\mathcal{F}}|$ is the minimum (maximum, resp.) with respect to the poset structure of $\mathcal{F}$. In the part of dissertation related to this topic, we develop algorithms to transfer any given separating union closed family to a/an normalized/irreducible family without changing its poset structure. We also study properties of these two extremal union closed families in connection with the {\it Union Closed Sets Conjecture} of Frankl. Our result may lead to potential full proof of the union closed set conjecture and several other conjectures. The part of the dissertation related to the maximum edge cuts in connected digraphs goes as follows. In a given digraph $D$, a set $F$ of edges is defined to be a {\it directed cut} if there is a nontrivial partition $(X,Y)$ of $V(D)$ such that $F$ consists of all the directed edges from $X$ to $Y$. The maximum size of a directed cut in a given digraph $D$ is denoted by $\Lambda (D)$, and we let $\mathcal{D}(1,1)$ be the set of all digraphs $D$ such that $d^{+}(v)=1$ or $d^{-}(v)=1$ for every vertex $v$ in $D$. In this part of dissertation, we prove that $\Lambda (D) \geq \frac{3}{8}(|E(D)|-1)$ for any connected digraph $D\in\mathcal{D}(1,1)$, which provides a positive answer to a problem of Lehel, Maffray, and Preissmann. Additionally, we consider triangle-free digraphs in $\mathcal{D}(1,1)$ and answer their another question.

The thesis consists of a collection of my contributions to universal algebra. Motivated by the Constraint Satisfaction Problem (CSP), we study the algebras of polymorphisms of relational structures. We begin by showing by an algebraic argument (and a bit of calculus) that random relational structures' CSP is almost always NP-complete. We then study digraphs with a Maltsev polymorphism, and conclude that such digraphs must also have a majority polymorphism. Next, we show how to use absorption tech- niques to prove that congruence modular reflexive digraphs must have an NU operation. We close our work by giving an algebraic proof of a result (first obtained by graph theorists) that 3-conservative relational structures with only unary and binary relations either define NP-complete CSP, or CSP for them can be solved by the local consistency algorithm. 1

Dans ce travail, nous considérons le problème suivant : étant donné un graphe orienté D, contient-il une subdivision d’un digraphe fixé F ? Nous pensons qu’il existe une dichotomie entre les instances polynomiales et NP-complètes. Nous donnons plusieurs exemples pour les deux cas. En particulier, sauf pour cinq instances, nous sommes capable de classer tous les digraphes d’ordre 4. Alors que toutes les preuves NP-complétude sont faites par réduction de une version du problème 2-linkage en digraphes, nous utilisons différents outils algorithmiques pour prouver la solvabilité en temps polynomial de certains cas, certains d’entre eux impliquant des algorithmes relativement complexes. Les techniques varient des simples algorithmes de force brute, aux algorithmes basés sur des calculs maximale de flot, et aux décompositions en anses des digraphes fortement connexes, entre autres. Pour terminer, nous traitons le cas particulier où F étant une union disjointe de cycles dirigés. En particulier, nous montrons que les cycles dirigés de longueur au moins 3 possède la Propriété d’Erdos-Pósa : pour tout n, il existe un entier tn tel que pour tout digraphe D, soit D a n cycles dirigés disjoints de longueur au moins 3, soit il y a un ensemble T d’au plus tn sommets qui intersecte tous les cycles dirigés de longueur au moins 3. De ce résultat, nous déduisons que si F est l’union disjointe de cycles dirigés de longueur au plus 3, alors on peut décider en temps polynomial si un digraphe contient une subdivision de F. / In this work, we consider the following problem: Given a directed graph D, does it contain a subdivision of a prescribed digraph F? We believe that there is a dichotomy between NP-complete and polynomial-time solvable instances of this problem. We present many examples of both cases. In particular, except for five instances, we are able to classify all the digraphs F of order 4.While all NP-hardness proofs are made by reduction from some version of the 2-linkage problem in digraphs, we use different algorithmic tools for proving polynomial-time solvability of certain instances, some of them involving relatively complicated algorithms. The techniques vary from easy brute force algorithms, algorithms based on maximum-flow calculations, handle decompositions of strongly connected digraphs, among others. Finally, we treat the very special case of F being the disjoint union of directed cycles. In particular, we show that the directed cycles of length at least 3 have the Erdos-Pósa Property: for every n, there exists an integer tn such that for every digraph D, either D contains n disjoint directed cycles of length at least 3, or there is a set T of tn vertices that meets every directed cycle of length at least 3. From this result, we deduce that if F is the disjoint union of directed cycles of length at most 3, then one can decide in polynomial time if a digraph contains a subdivision of F.

We discuss results dealing with universal cycles (ucycles) and s-overlap cycles, and contribute to the body of those results by proving existence of universal cycles of naturally labeled posets (NL posets), s-overlap cycles of words of weight k, and juggling patterns. The result on posets is, to the best of our knowledge, the first demonstration of the existence of a ucycle whose length is unknown.

Within population biology, models are often analyzed for the net reproduction number or other generalized target reproduction numbers, which describe the growth or decline of the population based on specific mechanisms. This is useful in determining the strength and efficiency of control measures for inhibiting or enhancing population growth. The literature contains many algebraic and combinatorial approaches for deriving the net reproduction number and generalized target reproduction numbers from digraphs and associated matrices. Finding, categorizing, and counting the permutations of disjoint cycles, or cycles unions is a requirement of the Cycle Union approach by Lewis et al. (2019). These cycles and subsequent cycle unions can be found via the digraphs and associated matrices. We developed cycle counting patterns for targeting fertilities within Leslie Matrices, Lefkovitch Matrices, Sub-Diagonal Lower Triangle Transition Matrices, and Lower Triangle Transition Matrices to serve as a foundation for future work. Presented are the counting patterns and closed-form summations of the cycle unions.