Decomposizioni di grafi

Consideriamo solo grafi semplici (non orientati, privi di cappi e spigoli multipli). Nella sua accezione più generale una decomposizione di un asegnato grafo T non è altro che una famiglia di sottografi di T, a due a due privi di spigoli comuni, che ricoprono l insieme degli spigoli di T. In buona sostanza i sottografi della decomposizione danno luogo a una partizione dell insieme degli spigoli del grafo T. Un caso molto studiato è quello in cui i sottografi della decomposizione sono tutti isomorfi a un assegnato grafo G; in questo caso si parla di una G-decomposizione di T. Quando T è il grafo completo su v vertici una G-decomposizione di T viene anche indicata come G-disegno. La dicitura è giustificata dal fatto che, come per i disegni classici, per due punti continua a passare un unico blocco, solo che questo blocco ha la forma del grafo G. Nel presente seminario esporrò alcuni risultati vecchi e nuovi nel caso in cui T è il grafo completo K_v, assumendo l esistenza di un gruppo di automorfismi della G-decomposizione con proprietà assegnate. Gli ultimi contributi riguardano il caso in cui G è un grafo di Petersen (generalizzato) o un matching di cardinalità k.