<p>Usmereni stepeni graf ~G(G) grupe G uveli su Kelarev i Quinn [37] kao digraf sa skupom cvorova G u kome je x ! y ako je y stepen elementa x, a stepeni graf G(G) je odgovarajuci prost graf, i njega su prvi proucavali Chakrabarty, Ghosh i Sen [17]. Obogaceni stepeni graf G e(G) od G, koji je uveden u [1], je prost graf&nbsp; sa istim skupom cvorova u kome su dva cvora susedna ako su oba stepeni nekog elementa te grupe.U disertaciji su predstavljeni dokazi iz [12] i [73] da se, za konacnu stepenoasocijativnu lupu G sa inverzima, ~ G(G), G(G) i G e(G) medusobno odreduju. Ovo povlaci da sva tri navedena grafa pridruzena konacnoj grupi u istoj meri odreduju razne osobine te grupe, kao sto su broj elemenata bilo kog reda i nilpotentnost te grupe. Dokazano je da, u slucaju torziono slobodne grupe u kojoj je svaki nejedinicni element sadrzan u jedinstvenoj maksimalnoj ciklicnoj podgrupi, stepeni graf odreduje usmereni stepeni graf, sto je rezultat rada [14], i analogno je dokazano i za torziono slobodne grupe klase nilpotentnosti klase 2. Pruzen je dokaz da je svaki automorzam stepenog grafa stepeno-asocijativne lupe sa inverzima automorzam obogacenog grafa. Dat je opis obogacenih stepenih grafova konacnih Abelovih grupa. Prezentirano je nekoliko potrebnih uslova da graf bude obogaceni stepeni graf neke konacne grupe, kao i algoritam koji za obogaceni stepeni graf konacne nilpotentne grupe daje obogaceni stepeni graf njene podgrupe Sylowa.Komutirajuci graf grupe je prost graf ciji je skup cvorova nosac grupe, i u kome su dva elementa susedna ako komutiraju. U disertaciji je predstavljen dokaz Bernharda Neumanna [54] da, ako komutirajuci graf grupe nema beskonacan nezavisan skup, onda on nema ni proizvoljno velike konacne nezavisne skupove. Okarakterisane su nilpotentne grupe ciji stepeni graf nema beskonacni nezavisni skup, sto je rezultat rada [1]. Prezentovan je dokaz Shitova [69] da je hromatski broj stepenog grafa stepeno-asocijativnog grupoida najvise prebrojiv, i dokazano je da je hromatski broj obogacenog stepenog grafa stepeno-asocijativne lupe sa inverzima takode<br />najvise prebrojiv. Izlozen je dokaz iz [1] da je stepeni graf svake grupe ogranicenog eksponenta perfektan, i data je karakterizacija konacnih nilpotentnih grupa ciji je obogaceni stepeni graf perfektan.</p> / <p>The directed power graph ~G(G) of a group G was introduced by Kelarev and Quinn [37] as the digraph with its vertex set G in which x ! y if y is a power of x.The power graph G(G) is the underlying simple graph, and it was rst studied by Chakrabarty, Ghosh and Sen [17]. The enhanced power graph G e(G) of G, which was introduced in [1], is the simple graph with the same vertex set in which two vertices are adjacent if they are powers of one element.In this thesis are presented the proofs from [12] and [73] that, for&nbsp; any powerassociative loop G with inverses,~ G(G), G(G) and G e(G) determine each other. It follows that each of these three graphs associated to a nite group provides the same amount of information about the group, such as the number of elements of any order and nilpotency of the group. It is also proved that, in the case of a torsionfree group in which every non-identity element is contained in a unique maximal cyclic subgroup, the power graph determines the directed power graph, which is a result from [14], and the same is proved for torsion-free groups of nilpotency class 2.It is proved that&nbsp; an automorphism of the power graph of a power-associative loop with inverses is an automorphism of the enhanced power graph. A description of enhanced power graphs of abelian groups is given. Several necessary conditions for a graph to be the enhanced power graph of a nite group are presented, as well as an algorithm which, given the enhanced power graph of a nite nilpotent group, constructs the enhanced power graph of&nbsp; the Sylow subgroup. The commuting graph of a group is the simple graph whose vertex set is the universe of the group, and in which two elements are adjacent if they commute. In the thesis is presented the proof by Bernhard Neumann [54] that, if the commuting graph of a group doesn&#39;t have any innite independent set, then there is a nite bound on cardinality of its independent sets. Nilpotent groups whose power graphs don&#39;t have any innite independent set are characterized, which is a result from [1]. The proof of Shitov [69] that the chromatic number of the power graph of a power-associative groupoid is at most countable is presented, and it is proved that the chromatic number of the enhanced power graph of power-associative loops with inverses are at most countable too. The proof from [1] that the power graph of any group of nite exponent is presented, and nite nilpotent groups whose enhanced power graph is&nbsp; perfect are characterized.</p>

We investigate power graphs of quasigroups. The power graph of a quasigroup takes the elements of the quasigroup as its vertices, and there is an edge from one element to a second distinct element when the second is a left power of the first. We first compute the power graphs of small quasigroups (up to four elements). Next we describe quasigroups whose power graphs are directed paths, directed cycles, in-stars, out-stars, and empty. We do so by specifying partial Cayley tables, which cannot always be completed in small examples. We then consider sinks in the power graph of a quasigroup, as subquasigroups give rise to sinks. We show that certain structures cannot occur as sinks in the power graph of a quasigroup. More generally, we show that certain highly connected substructures must have edges leading out of the substructure. We briefly comment on power graphs of Bol loops.

Molecular biology has entered an era of systematic and automated experimentation. High-throughput techniques have moved biology from small-scale experiments focused on specific genes and proteins to genome and proteome-wide screens. One result of this endeavor is the compilation of complex networks of interacting proteins. Molecular biologists hope to understand life's complex molecular machines by studying these networks. This thesis addresses tree open problems centered upon their analysis and quality assessment. First, we introduce power graph analysis as a novel approach to the representation and visualization of biological networks. Power graphs are a graph theoretic approach to lossless and compact representation of complex networks. It groups edges into cliques and bicliques, and nodes into a neighborhood hierarchy. We demonstrate power graph analysis on five examples, and show its advantages over traditional network representations. Moreover, we evaluate the algorithm performance on a benchmark, test the robustness of the algorithm to noise, and measure its empirical time complexity at O (e1.71)- sub-quadratic in the number of edges e. Second, we tackle the difficult and controversial problem of data quality in protein interaction networks. We propose a novel measure for accuracy and completeness of genome-wide protein interaction networks based on network compressibility. We validate this new measure by i) verifying the detrimental effect of false positives and false negatives, ii) showing that gold standard networks are highly compressible, iii) showing that authors' choice of confidence thresholds is consistent with high network compressibility, iv) presenting evidence that compressibility is correlated with co-expression, co-localization and shared function, v) showing that complete and accurate networks of complex systems in other domains exhibit similar levels of compressibility than current high quality interactomes. Third, we apply power graph analysis to networks derived from text-mining as well to gene expression microarray data. In particular, we present i) the network-based analysis of genome-wide expression profiles of the neuroectodermal conversion of mesenchymal stem cells. ii) the analysis of regulatory modules in a rare mitochondrial cytopathy: emph{Mitochondrial Encephalomyopathy, Lactic acidosis, and Stroke-like episodes} (MELAS), and iii) we investigate the biochemical causes behind the enhanced biocompatibility of tantalum compared with titanium.

Les deux problèmes majeurs considérés dans cette thèse : le b-coloration problème et le graphe emballage problème. 1. Le b-coloration problème : Une coloration des sommets de G s'appelle une b-coloration si chaque classe de couleur contient au moins un sommet qui a un voisin dans toutes les autres classes de couleur. Le nombre b-chromatique b(G) de G est le plus grand entier k pour lequel G a une b-coloration avec k couleurs. EL Sahili et Kouider demandent s'il est vrai que chaque graphe d-régulier G avec le périmètre au moins 5 satisfait b(G) = d + 1. Blidia, Maffray et Zemir ont montré que la conjecture d'El Sahili et de Kouider est vraie pour d ≤ 6. En outre, la question a été résolue pour les graphes d-réguliers dans des conditions supplémentaires. Nous étudions la conjecture d'El Sahili et de Kouider en déterminant quand elle est possible et dans quelles conditions supplémentaires elle est vrai. Nous montrons que b(G) = d + 1 si G est un graphe d-régulier qui ne contient pas un cycle d'ordre 4 ni d'ordre 6. En outre, nous fournissons des conditions sur les sommets d'un graphe d-régulier G sans le cycle d'ordre 4 de sorte que b(G) = d + 1. Cabello et Jakovac ont prouvé si v(G) ≥ 2d3 - d2 + d, puis b(G) = d + 1, où G est un graphe d-régulier. Nous améliorons ce résultat en montrant que si v(G) ≥ 2d3 - 2d2 + 2d alors b(G) = d + 1 pour un graphe d-régulier G. 2. Emballage de graphe problème : Soit G un graphe d'ordre n. Considérer une permutation σ : V (G) → V (Kn), la fonction σ* : E(G) → E(Kn) telle que σ *(xy) = σ *(x) σ *(y) est la fonction induite par σ. Nous disons qu'il y a un emballage de k copies de G (dans le graphe complet Kn) s'il existe k permutations σi : V (G) → V (Kn), où i = 1, …, k, telles que σi*(E(G)) ∩ σj (E(G)) = ɸ pour i ≠ j. Un emballage de k copies d'un graphe G est appelé un k-placement de G. La puissance k d'un graphe G, noté par Gk, est un graphe avec le même ensemble de sommets que G et une arête entre deux sommets si et seulement si le distance entre ces deux sommets est au plus k. Kheddouci et al. ont prouvé que pour un arbre non-étoile T, il existe un 2-placement σ sur V (T). Nous introduisons pour la première fois le problème emballage marqué de graphe dans son graphe puissance / Two problems are considered in this thesis: the b-coloring problem and the graph packing problem. 1. The b-Coloring Problem : A b-coloring of a graph G is a proper coloring of the vertices of G such that there exists a vertex in each color class joined to at least a vertex in each other color class. The b-chromatic number of a graph G, denoted by b(G), is the maximum number t such that G admits a b-coloring with t colors. El Sahili and Kouider asked whether it is true that every d-regular graph G with girth at least 5 satisfies b(G) = d + 1. Blidia, Maffray and Zemir proved that the conjecture is true for d ≤ 6. Also, the question was solved for d-regular graphs with supplementary conditions. We study El Sahili and Kouider conjecture by determining when it is possible and under what supplementary conditions it is true. We prove that b(G) = d+1 if G is a d-regular graph containing neither a cycle of order 4 nor of order 6. Then, we provide specific conditions on the vertices of a d-regular graph G with no cycle of order 4 so that b(G) = d + 1. Cabello and Jakovac proved that if v(G) ≥ 2d3 - d2 + d, then b(G) = d + 1, where G is a d-regular graph. We improve this bound by proving that if v(G) ≥ 2d3 - 2d2 + 2d, then b(G) = d+1 for a d-regular graph G. 2. Graph Packing Problem : Graph packing problem is a classical problem in graph theory and has been extensively studied since the early 70's. Consider a permutation σ : V (G) → V (Kn), the function σ* : E(G) → E(Kn) such that σ *(xy) = σ *(x) σ *(y) is the function induced by σ. We say that there is a packing of k copies of G into the complete graph Kn if there exist k permutations σ i : V (G) → V (Kn), where i = 1,…, k, such that σ*i (E(G)) ∩ σ*j (E(G)) = ɸ for I ≠ j. A packing of k copies of a graph G will be called a k-placement of G. The kth power Gk of a graph G is the supergraph of G formed by adding an edge between all pairs of vertices of G with distance at most k. Kheddouci et al. proved that for any non-star tree T there exists a 2-placement σ on V (T). We introduce a new variant of graph packing problem, called the labeled packing of a graph into its power graph

Molecular biology has entered an era of systematic and automated experimentation. High-throughput techniques have moved biology from small-scale experiments focused on specific genes and proteins to genome and proteome-wide screens. One result of this endeavor is the compilation of complex networks of interacting proteins. Molecular biologists hope to understand life's complex molecular machines by studying these networks. This thesis addresses tree open problems centered upon their analysis and quality assessment. First, we introduce power graph analysis as a novel approach to the representation and visualization of biological networks. Power graphs are a graph theoretic approach to lossless and compact representation of complex networks. It groups edges into cliques and bicliques, and nodes into a neighborhood hierarchy. We demonstrate power graph analysis on five examples, and show its advantages over traditional network representations. Moreover, we evaluate the algorithm performance on a benchmark, test the robustness of the algorithm to noise, and measure its empirical time complexity at O (e1.71)- sub-quadratic in the number of edges e. Second, we tackle the difficult and controversial problem of data quality in protein interaction networks. We propose a novel measure for accuracy and completeness of genome-wide protein interaction networks based on network compressibility. We validate this new measure by i) verifying the detrimental effect of false positives and false negatives, ii) showing that gold standard networks are highly compressible, iii) showing that authors' choice of confidence thresholds is consistent with high network compressibility, iv) presenting evidence that compressibility is correlated with co-expression, co-localization and shared function, v) showing that complete and accurate networks of complex systems in other domains exhibit similar levels of compressibility than current high quality interactomes. Third, we apply power graph analysis to networks derived from text-mining as well to gene expression microarray data. In particular, we present i) the network-based analysis of genome-wide expression profiles of the neuroectodermal conversion of mesenchymal stem cells. ii) the analysis of regulatory modules in a rare mitochondrial cytopathy: emph{Mitochondrial Encephalomyopathy, Lactic acidosis, and Stroke-like episodes} (MELAS), and iii) we investigate the biochemical causes behind the enhanced biocompatibility of tantalum compared with titanium.