This work deals with the concept of Cayley graphs and related properties.
A Cayley graph is a graph whose vertex set is a group G and two vertices u and v are adjacent if and only if uv−1 is an element of a given subset S of G.
After describing general properties of Cayley graphs, such as its automorphism group and the structure of the graph when G is a free group or when G is a finite group, we focus on three main topics related to the concept of Cayley graph.
The first one is a special class of these graphs: complete rotational Cayley graphs; which are Cayley graphs admitting a particular automorphism ω such that, for some ordering of S = {si : 0 ≤ i ≤ d − 1}, ω(xsi ) = ω(x)si+1 for any x ∈ G and any i ∈ Zd .
Of great interest are the Cayley graphs defined by transpositions (i.e. S is a set of transpositions). These graphs, with the additional property of being rotational, are completely characterized by a theorem which states that they are essentially of two kinds: modified bubble-sort graphs and Cartesian products of isomorphic modified bubble-sort graph; and generalized star graphs GST(t+q, q) with t and q relatively prime and Cartesian products of isomorphic generalized star graphs GST(t+q, q) with t and q relatively prime.
The second topic deals with what is generally known as the maximum clique problem, which asks for a clique of maximum cardinality; where a clique is a subset of the vertex set such that the induced subgraph is complete. We have distinguished between maximal clique (i.e. a clique that is not a proper subset of any other clique) and maximum clique (i.e. a maximal clique that has the maximum cardinality) and we have analyzed some results that construct a maximal clique in the Cayley graph of square order.
Moreover, we have studied some bounds for the clique number (the size of the maximum clique in the graph), the independent number (the cardinality of the largest coclique in the graph) and the chromatic number (the minimum number of colors required to obtain a proper coloring of the graph) obtained with the eigenvalues of the graph (i.e. the eigenvalues of the adjacency matrix of the graph).
This is the reason why we have introduced, as the last main topic, the spectrum of Cayley graphs. In order to obtain information about the spectrum of a Cayley graph, we have to investigate the structure of the group G; in particular its representations. In fact there is a fundamental theorem which describes the spectrum of the Cayley graph, more generally a Cayley color graph, using the distinct irreducible characters of G.
After that, we have considered the maximum clique problem in the case of rotational Cayley graphs. First of all we have investigate the case in which the graph is defined by transpositions. After that we have construct some rotational Cayley graphs not generated by transpositions and we have computed the corresponding spectrum.
In the appendices there are definitions and main properties about presentation of finite groups and representation theory, two subjects that are foundamental for studying the concepts presented in this work.
Tra gli argomenti considerati ormai classici nell’ambito della teoria dei grafi rientrano senz’altro i problemi di colorazione e i problemi di decomposizione.
Per quanto riguarda i primi si parla addirittura di teoria cromatica dei grafi, distinguendo in genere se si considerano colorazioni sui vertici o sugli spigoli. Nei problemi di decomposizione si studia la possibilità di spezzare un grafo assegnato in “pezzi” dotati di particolari proprietà. Di fatto si può pensare che le due tipologie di problemi siano facce diverse della stessa medaglia. In altre parole per una assegnata colorazione di un grafo si può andare ad esaminare la struttura costituita dai sottografi determinati dagli oggetti (vertici o spigoli) che hanno ricevuto lo stesso colore. Viceversa, data una decomposizione di un grafo, si può pensare che i sottografi della decomposizione in esame siano oggetti di colore assegnato in una colorazione di qualche tipo (sui vertici o sugli spigoli).
Per quanto riguarda la colorazione sugli spigoli, un risultato fondamentale si deve a Vizing [4] il quale dimostrò una relazione che lega il numero di colori necessari per determinare una colorazione con la valenza massima dei vertici del grafo in esame. Questo teorema consente di suddividere i grafi in due categorie: i grafi di Classe 1 e di Classe 2. I primi sono tali per cui il numero di colori necessari è pari alla valenza massima dei vertici, i secondi invece necessitano di un colore ulteriore rispetto al valore del grado massimo dei vertici del grafo.
Di notevole importanza è il concetto di 1-fattorizzazione, con il quale si intende la possibilità di decomporre il grafo dato in sottografi ricoprenti regolari di grado 1 tali che, a due a due, siano privi di archi comuni e la loro unione sia il grafo in esame. Il legame tra 1-fattorizzazione e colorazione sugli spigoli emerge in particolare quando si analizzano i grafi regolari; infatti per questi ultimi essere di Classe 1 equivale ad essere 1-fattorizzabili. Affinchè un grafo sia 1-fattorizzabile è necessario, come verrà meglio spiegato nel Cap. 3, che sia regolare e abbia un numero pari di vertici.
Non tutti i grafi regolari però risultano 1-fattorizzabili, come si vede analizzando, ad esempio, il grafo di Petersen. Nasce quindi il problema di determinare una condizione sufficiente che indichi se il grafo è 1-fattorizzabile (e quindi di Classe 1). In particolare è stata sviluppata l’idea che se un grafo regolare ha valenza “abbastanza” alta, allora è 1-fattorizzabile.
Qual’è un valore adeguato per la soglia minima della valenza? È in questo contesto che viene formulata la cosiddetta “congettura della 1-fattorizzazione”, che a tutt’oggi non ha ancora un controesempio:
se G è un grafo regolare di grado d su 2n vertici tale che
• d ≥ n – 1, se n è pari
• d ≥ n,, se n è dispari
allora G è 1-fattorizzabile. Nel tempo si sono dimostrati vari risultati che tendono ad abbassare la soglia, avvicinandosi sempre più a quella della congettura. In questa tesi verranno riportati i risultati relativi ai grafi regolari di grado d = 2n – 1, d = 2n – 2, d = 2n – 3, d = 2n – 4 e d = 2n – 5 presenti in [3] e in [1].
Verranno presentati anche teoremi dovuti a Chetwynd ed Hilton nei quali la congettura in esame è stata dimostrata per d ≥ 6/7 |V (G)|∼0.857 |V (G)| in [1] e d ≥ 1/2(√7 – 1)|V (G)|∼ 0.823 |V (G)| in [2]. Infine verranno elencati alcuni risultati recenti che migliorano la soglia minima che deve soddisfare la valenza del grafo affinchè quest’ultimo sia 1-fattorizzabile.
[1] A. G. Chetwynd, A. J. W. Hilton, Regular graphs of high degree are 1-fatorizable. Proc. London Math. Soc. 3(2), 193-206 (1985)
[2] A. G. Chetwynd, A. J. W. Hilton, 1-factorizing regular graphs of high degree-an improved buond. Discrete Mathematics 75, 103-112 (1989)
[3] W. D. Wallis, One-Factorizations (Kluwer Academic Publishers, Dordrecht, 1997)
[4] V. G. Vizing, On an estimate of the chromatic class of p-graph [Russian]. Discretyni Analiz 3, 25-30 (1964)
È noto che alcune sequenze di quattro elementi, che sono le basi azotate A, C, G, T (cioè adenina, citosina, guanina e timina) da cui è formato il DNA, si ripetono nel genoma umano molte volte. A causa della struttura del DNA, differenti sequenze che sono equivalenti a meno di rotazione ciclica e complementazione inversa, determinano lo stesso schema ripetuto nella sequenza del DNA. Bell et al. [1] determinano una formula per il numero di classi di equivalenza di schemi primitivi di sequenze di DNA di lunghezza n utilizzando la corrispondenza biunivoca tra le parole su due lettere di lunghezza 2n e le parole di lunghezza n in quattro lettere. Un’ulteriore derivazione della formula di classificazione delle sequenze di DNA di lunghezza n è presentata in [2] dove si utilizzano proprietà di strutture cicliche relative ai punti fissi dell’ipercubo Qn .
In questa tesi una stringa binaria ciclica di lunghezza n è interpretata come una particolare composizione ciclica di n e viene introdotta la nozione di grafo partizione Pn di un intero positivo n: i vertici di Pn sono collane binarie. Inoltre, viene studiato il rapporto tra cammini e cicli di Pn e Qn .
Nella seconda parte di questo lavoro vengono analizzate alcune tecniche che utilizzano le proprietà di complementarità dei filamenti di DNA per costruire nanostrutture, in particolare poliedri. Per tutti questi metodi, un passo essenziale è la descrizione accurata delle componenti molecolari che costituiranno i blocchi da utilizzare durante il processo di assemblaggio; vi è quindi una crescente necessità di approcci matematici a questi problemi di progettazione.
In questa tesi forniamo un modello matematico in grado di catturare i vincoli geometrici dei tasselli rigidi (“rigid tile”), i quali rappresentano “branched junction molecules”. Descriviamo anche un formalismo teorico per il metodo DNA-origami. Utilizzando queste tecniche mostriamo come costruire in modo efficiente i solidi platonici ed archimedei 3-regolari.
[1] G.I. Bell, R.L. Bivins, J.D. Louck , N. Metropolis, M.L. Stein, Properties of words on four letters from those on two letters with an application to DNA sequences. Advances in Applied Mathematics 14(3), 348–367 (1993)
[2] W. Y. C. Chen, J. D. Louck, Necklaces, MSS sequences, and DNA sequences. Advances in Applied Mathematics 18(1), 18–32 (1997)
It is known that some sequences of four elements, that are the nitrogenous bases A, C, G, T (namely adenine, cytosine, guanine and thymine) from which DNA is assembled, are repeated in the human genome many times. Because of the structure of DNA, different sequences that are equivalent up to cyclic rotation and reverse complementation, determine the same repeated pattern. Bell et al. [1] were able to derive a formula for the number of equivalence classes of primitive patterns of DNA sequences of length n using the bijective correspondence between words on two letters of length 2n and words of length n on four letters. A further derivation of the formula for the classification of DNA sequences of length n is provided in [2] by using properties of cycle structures related to fixed points of the hypercube Qn.
In this thesis a cyclic binary string of length n is interpreted as a particular cyclic composition of n and the notion of the partition graph Pn of a positive integer n is introduced: the vertices of Pn are binary necklaces. Moreover, the relation between paths and cycles of Pn and Qn is investigated.
The second part of this work deals with techniques that use the Watson-Crick complementarity properties of DNA strands to self-assembly nanostructures, particularly polyhedra. For all of these methods, an essential step is designing the component molecular building blocks; thus there is an increased necessity for a mathematical approach to these design strategy problems.
We provide a mathematical model that captures the geometric constraints of rigid tiles, which are the branched junction molecule building blocks for tile-based DNA self-assembly. We also describe graph theoretical formalism for the DNA origami method. Using the aforementioned techniques we provide DNA self-assembly strategies to efficiently construct Platonic and Archimedean 3-regular polyhedral skeletons.
[1] G. I. Bell, R. L. Bivins, J. D. Louck , N. Metropolis, M. L. Stein, Properties of words on four letters from those on two letters with an application to DNA sequences. Advances in Applied Mathematics 14(3), 348–367 (1993)
[2] W. Y. C. Chen, J. D. Louck, Necklaces, MSS sequences, and DNA sequences. Advances in Applied Mathematics 18(1), 18–32 (1997)