In this paper, we give necessary and sufficient conditions for the existence of a decomposition of the λ-fold mixed complete graph into partial orientations of P4 and S3. Simple direct constructions are given in each case.

Let v ∈ Z+ and G be a simple graph. A G-decomposition of Kv is a collection F={F1,F2,...,Ft} of subgraphs of Kv such that every edge of Kv occurs in exactlyone of the subgraphs and every graph Fi ∈ F is isomorphic to G. A G-decomposition of Kv is called balanced if each vertex of Kv occurs in the same number of copies of G. In 2011, Dukes and Malloch provided an existence theory for balanced G-decompositions of Kv. Shortly afterwards, Bonisoli, Bonvicini, and Rinaldi introduced degree- and orbit-balanced G-decompositions. Similar to balanced decompositions,these two types of G-decompositions impose a local structure on the vertices of Kv. In this thesis, we will present an existence theory for degree- and orbit-balanced G-decompositions of Kv. To do this, we will first develop a theory for decomposing Kv into copies of G when G contains coloured loops. This will be followed by a brief discussion about the applications of such decompositions. Finally, we will explore anextension of this problem where Kv is decomposed into a family of graphs. We will examine the complications that arise with families of graphs and provide results for a few special cases. / Graduate

A decomposition D of a graph H by a graph G is a partition of the edge set of H such that the subgraph induced by the edges in each part of the partition is isomorphic to G. The intersection graph I (D)of the decomposition D has a vertex for each part of the partition and two parts A and B are adjacent iff they share a common node in H. If I (D) ≅ H, then D is an automorphic decomposition of H. In this paper we show how automorphic decompositions serve as a common generalization of configurations from geometry and graceful labelings on graphs. We will give several examples of automorphic decompositions as well as necessary conditions for their existence.

Let K(v,w) denote the complete graph on v vertices with a hole of size w (i.e., K(v, w) = Kv\Kw). We give necessary and sufficient conditions for the existence of a minimum 4-cycle covering of K (v,w).

No description available.

Structural Properties of Graphs and Eficient Algorithms: Problems Between Parameters Dušan Knop Parameterized complexity became over last two decades one of the most impor- tant subfield of computational complexity. Structural graph parameters (widths) play important role both in graph theory and (parameterized) algoritmh design. By studying some concrete problems we exhibit the connection between struc- tural graph parameters and parameterized tractability. We do this by examining tractability and hardness results for the Target Set Selection, Minimum Length Bounded Cut, and other problems. In the Minimum Length Bounded Cut problem we are given a graph, source, sink, and a positive integer L and the task is to remove edges from the graph such that the distance between the source and the sink exceeds L in the resulting graph. We show that an optimal solution to the Minimum Length Bounded Cut problem can be computed in time f(k)n, where f is a computable function and k denotes the tree-depth of the input graph. On the other hand we prove that (under assumption that FPT ̸= W[1]) no such algorithm can exist if the parameter k is the tree-width of the input graph. Currently only few such problems are known. The Target Set Selection problem exibits the same phenomenon for the vertex cover number and...

Necessary and sufficient conditions are given for the existence of isomorphic decompositions of the complete bipartite graph, the complete graph with a hole, and the λ-fold complete graph into copies of a 4-cycle with a pendant edge.

A design is a set of points, V, together with a set of subsets of V called blocks. A classic type of design is a balanced incomplete block design, where every pair of points occurs together in a block the same number of times. This ‘balanced’ condition can be replaced with other properties. An adesign is a design where instead every pair of points occurs a different number of times together in a block. The number of times a specified pair of points occurs together is called the pair frequency. Here, a special type of adesign is explored, called a Sarvate-Beam design, named after its founders D.G. Sarvate and W. Beam. In such an adesign, the pair frequencies cover an interval of consecutive integers. Specifically the existence of Sarvate-Beam group divisible designs are investigated. A group divisible design, in the usual sense, is a set of points and blocks where the points are partitioned into subsets called groups. Any pair of points contained in a group have pair frequency zero and pairs of points from different groups have pair frequency one. A Sarvate-Beam group divisible design, or SBGDD, is a group divisible design where instead the frequencies of pairs from different groups form a set of distinct nonnegative consecutive integers. The SBGDD is said to be uniform when the groups are of equal size. The main result of this dissertation is to completely settle the existence question for uniform SBGDDs with blocks of size three where the smallest pair frequency, called the starting frequency, is zero. Higher starting frequencies are also considered and settled for all positive integers except when the SBGDD is partitioned into eight groups where a few possible exceptions remain. A relationship between these designs and graph decompositions is developed and leads to some generalizations. The use of matrices and linear programming is also explored and give rise to related results. / Graduate

Cette thèse porte sur l’étude des propriétés structurelles de graphes dont la compréhension permet de concevoir des algorithmes efficaces pour résoudre des problèmes d’optimisation. Nous nous intéressons plus particulièrement aux méthodes de décomposition des graphes, aux jeux de poursuites et à la notion de convexité. Le jeu de Processus a été défini comme un modèle de la reconfiguration de routage. Souvent, ces jeux où une équipe de chercheurs doit effacer un graphe non orienté sont reliés aux décompositions de graphes. Dans les digraphes, nous montrons que le jeu de Processus est monotone et nous définissons une nouvelle décomposition de graphes que lui est équivalente. Ensuite, nous étudions d’autres décompositions de graphes. Nous proposons un algorithme FPT-unifiée pour calculer plusieurs paramètres de largeur de graphes. En particulier, ceci est le premier FPT-algorithme pour la largeur arborescente q-branché et spéciale d’un graphe. Nous étudions ensuite un autre jeu qui modélise les problèmes de pré-chargement. Nous introduisons la variante en ligne du jeu de surveillance. Nous étudions l’écart entre le jeu de surveillance classique et ses versions connecté et en ligne, en fournissant de nouvelles bornes. Nous définissons ensuite un cadre général pour l’étude des jeux poursuite-évasion. Cette méthode nous permet de donner les premiers résultats d’approximation pour certains de ces jeux. Finalement, nous étudions un autre paramètre lié à la convexité des graphes et à la propagation d’infection dans les réseaux, le nombre enveloppe. Nous fournissons plusieurs résultats de complexité en fonction des structures des graphes et en utilisant des décompositions de graphes. / This thesis focuses on the study of structural properties of graphs whose understanding enables the design of efficient algorithms for solving optimization problems. We are particularly interested in methods of decomposition, pursuit-evasion games and the notion of convexity. The Process game has been defined as a model for the routing reconfiguration problem in WDM networks. Often, such games where a team of searchers have to clear an undirected graph are closely related to graph decompositions. In digraphs, we show that the Process game is monotone and we define a new equivalent digraph decomposition. Then, we further investigate graph decompositions. We propose a unified FPT-algorithm to compute several graph width parameters. This algorithm turns to be the first FPT-algorithm for the special and the q-branched tree-width of a graph. We then study another pursuit-evasion game which models prefetching problems. We introduce the more realistic online variant of the Surveillance game. We investigate the gap between the classical Surveillance Game and its connected and online versions by providing new bounds. We then define a general framework for studying pursuit-evasion games, based on linear programming techniques. This method allows us to give first approximation results for some of these games. Finally, we study another parameter related to graph convexity and to the spreading of infection in networks, namely the hull number. We provide several complexity results depending on the graph structures making use of graph decompositions. Some of these results answer open questions of the literature.