This thesis considers spectral approaches to finding maximum cocliques in graphs. We focus on the relation between the eigenspaces of a graph and the size and location of its maximum cocliques. Our main result concerns the computational problem of finding the size of a maximum coclique in a graph. This problem is known to be NP-Hard for general graphs. Recently, Codenotti et al. showed that computing the size of a maximum coclique is still NP-Hard if we restrict to the class of circulant graphs. We take an alternative approach to this result using quotient graphs and coding theory. We apply our method to show that computing the size of a maximum coclique is NP-Hard for the class of Cayley graphs for the groups $\mathbb{Z}_p^n$ where $p$ is any fixed prime. Cocliques are closely related to equitable partitions of a graph, and to parallel faces of the eigenpolytopes of a graph. We develop this connection and give a relation between the existence of quadratic polynomials that vanish on the vertices of an eigenpolytope of a graph, and the existence of elements in the null space of the Veronese matrix. This gives a us a tool for finding equitable partitions of a graph, and proving the non-existence of equitable partitions. For distance-regular graphs we exploit the algebraic structure of association schemes to derive an explicit formula for the rank of the Veronese matrix. We apply this machinery to show that there are strongly regular graphs whose $\tau$-eigenpolytopes are not prismoids. We also present several partial results on cocliques and graph spectra. We develop a linear programming approach to the problem of finding weightings of the adjacency matrix of a graph that meets the inertia bound with equality, and apply our technique to various families of Cayley graphs. Towards characterizing the maximum cocliques of the folded-cube graphs, we find a class of large facets of the least eigenpolytope of a folded cube, and show how they correspond to the structure of the graph. Finally, we consider equitable partitions with additional structural constraints, namely that both parts are convex subgraphs. We show that Latin square graphs cannot be partitioned into a coclique and a convex subgraph.

L’utilisation de l’algèbre pour résoudre des problèmes de graphes a conduit au développement de trois branches : théorie spectrale des graphes, géométrie et combinatoire des groupes et études des invariants de graphes. La notion de graphe d’expansions (invariant de graphes) est relativement récente, elle a été développée afin d’étudier la robustesse des réseaux de télécommunication. Il s’avère que la construction de familles infinies de graphes expanseurs est un problème difficile. Cette thèse traite principalement de la construction de nouvelles familles de tels graphes. Les graphes expanseurs possèdent des nombreuses applications en informatique, notamment dans la construction de certains algorithmes, en théorie de la complexité, sur les marches aléatoires (random walk), etc. En informatique théorique, ils sont utilisés pour construire des familles de codes correcteurs d’erreur. Comme nous l’avons déjà vu les familles d’expanseurs sont difficiles à construire. La plupart des constructions s'appuient sur des techniques algébriques complexes, principalement en utilisant des graphes de Cayley et des produit Zig-Zag. Dans cette thèse, nous présentons une nouvelle méthode de construction de familles infinies d’expanseurs en utilisant les G-graphes. Ceux-ci sont en quelque sorte une généralisation des graphes de Cayley. Plusieurs nouvelles familles infinies d’expanseurs sont construites, notamment la première famille d’expanseurs irréguliers. / Applying algebraic and combinatorics techniques to solve graph problems leads to the birthof algebraic and combinatorial graph theory. This thesis deals mainly with a crossroads questbetween the two theories, that is, the problem of constructing infinite families of expandergraphs.From a combinatorial point of view, expander graphs are sparse graphs that have strongconnectivity properties. Expanders constructions have found extensive applications in bothpure and applied mathematics. Although expanders exist in great abundance, yet their explicitconstructions, which are very desirable for applications, are in general a hard task. Mostconstructions use deep algebraic and combinatorial approaches. Following the huge amountof research published in this direction, mainly through Cayley graphs and the Zig-Zagproduct, we choose to investigate this problem from a new perspective; namely by usingG-graphs theory and spectral hypergraph theory as well as some other techniques. G-graphsare like Cayley graphs defined from groups, but they correspond to an alternative construction.The reason that stands behind our choice is first a notable identifiable link between thesetwo classes of graphs that we prove. This relation is employed significantly to get many newresults. Another reason is the general form of G-graphs, that gives us the intuition that theymust have in many cases such as the relatively high connectivity property.The adopted methodology in this thesis leads to the identification of various approaches forconstructing an infinite family of expander graphs. The effectiveness of our techniques isillustrated by presenting new infinite expander families of Cayley and G-graphs on certaingroups. Also, since expanders stand in no single stem of graph theory, this brings us toinvestigate several closely related threads from a new angle. For instance, we obtain newresults concerning the computation of spectra of certain Cayley and G-graphs, and theconstruction of several new infinite classes of integral and Hamiltonian Cayley graphs.

L’objectif principal de cette thèse est d’étudier le problème du contrôle de suivi distribué pour les systèmes de formation de multi-robots à contrainte non holonomique. Ce contrôle vise à entrainer une équipe de robots mobile de type monocycle pour former une configuration de formation désirée avec son centroïde se déplaçant avec une autre trajectoire de référence dynamique et pouvant être spécifié par le leader virtuel ou humain. Le problème du contrôle de suivi a été résolu au cours de cette thèse en développant divers contrôleurs distribués pratiques avec la considération d’un taux de convergence plus rapide, une précision de contrôle plus élevée, une robustesse plus forte, une estimation du temps de convergence explicite et indépendante et moins de coût de communication et de consommation d’énergie. Dans la première partie de la thèse nous étudions d’abord au niveau du chapitre 2 la stabilité à temps fini pour les systèmes de formation de multi-robots. Une nouvelle classe de contrôleur à temps fini est proposée dans le chapitre 3, également appelé contrôleur à temps fixe. Nous étudions les systèmes dynamiques de suivi de formation de multi-robots non holonomiques dans le chapitre 4. Dans la deuxième partie, nous étudions d'abord le mécanisme de communication et de contrôle déclenché par l'événement sur les systèmes de suivi de la formation de multi-robots non-holonomes au chapitre 5. De plus, afin de développer un schéma d'implémentation numérique, nous proposons une autre classe de contrôleurs périodiques déclenchés par un événement basé sur un observateur à temps fixe dans le chapitre 6. / The main aim of this thesis is to study the distributed tracking control problem for the multi-robot formation systems with nonholonomic constraint, of which the control objective it to drive a team of unicycle-type mobile robots to form one desired formation configuration with its centroid moving along with another dynamic reference trajectory, which can be specified by the virtual leader or human. We consider several problems in this point, ranging from finite-time stability andfixed-time stability, event-triggered communication and control mechanism, kinematics and dynamics, continuous-time systems and hybrid systems. The tracking control problem has been solved in this thesis via developing diverse practical distributed controller with the consideration of faster convergence rate, higher control accuracy, stronger robustness, explicit and independent convergence time estimate, less communication cost and energy consumption.In the first part of the thesis, we first study the finite-time stability for the multi-robot formation systems in Chapter 2. To improve the pior results, a novel class of finite-time controller is further proposed in Chapter 3, which is also called fixed-time controller. The dynamics of nonholonomic multi-robot formation systems is considered in Chapter 4. In the second part, we first investigate the event-triggered communication and control mechanism on the nonholonomic multi-robot formation tracking systems in Chapter 5. Moreover, in order to develop a digital implement scheme, we propose another class of periodic event-triggered controller based on fixed-time observer in Chapter 6.