Resumen de Magic graphs

Francesc Antoni Muntaner Batlle

• Si un graf G admet un etiquetament super edge magic, aleshores G es diu que és un graf super edge màgic. La tesis està principalment enfocada a lestudi del conjunt de grafs que admeten etiquetaments super edge magic així com també a desenvolupar relacions entre aquest tipus detiquetaments i altres etiquetaments molt estudiats com ara els etiquetaments graciosos i armònics, entre daltres. De fet, els etiquetaments super edge magic serveixen com nexe dunió entre diferents tipus detiquetaments, i per tant moltes relacions entre etiquetaments poden ser obtingudes daquesta forma.

  A la tesis també es proposa una nova manera de pensar en la ja famosa conjectura que afirma que tots els arbres admeten un etiquetament super edge magic. Això és, per a cada arbre T trobam un arbre super edge magic T' que conté a T com a subgraf, i lordre de T'no és massa gran quan el comparam amb lordre de T .

  Un problema de naturalesa similar al problema anterior, en el sentit que intentam trobar un graf super edge magic lo més petit possible i que contengui a cert tipus de grafs, i que ha estat completament resolt a la tesis es pot enunciar com segueix.

  Problema: Quin és un graf conexe G super edge magic dordre més petit que conté al graf complet ? Kn com a subgraf?.

  La solució daquest problema és prou interessant ja que relaciona els etiquetaments super edge magic amb un concepte clàssic de la teoria aditiva de nombres com són els conjunts de Sidon dèbils, també coneguts com well spread sets.De fet, aquesta no és la única vegada que el concepte de conjunt de Sidon apareix a la tesis. També quan a la tesis es tracta el tema de la deficiència , els conjunts de Sidon són duna gran utilitat. La deficiencia super edge magic dun graf és una manera de mesurar quan daprop està un graf de ser super edge magic. Tècnicament parlant, la deficiència super edge magic dun graf ? G es defineix com el mínim número de vèrtexs aillats amb els que hem dunir G perque el graf resultant sigui super edge magic. Si daquesta manera no aconseguim mai que el graf resultant sigui super edge magic, aleshores deim que la deficiència del graf és infinita. A la tesis, calculam la deficiència super edge magic de moltes families importants de grafs, i a més donam alguns resultats generals, sobre aquest concepte.

  Per acabar aquest document, simplement diré que al llarg de la tesis molts dexemples que completen la tesis, i que fan la seva lectura més agradable i entenible han estat introduits.

  ------------------------------------------------------------------------------------------------------- SUMMARY OF THESIS If a graph G admits a super edge magic labeling, then G is called a super edge magic graph. The thesis is mainly devoted to study the set of graphs which admit super edge magic labelings as well as to stablish and study relations with other well known labelings.

  For instance, graceful and harmonic labelings, among others, since many relations among labelings can be obtained using super edge magic labelings as the link.

  In the thesis we also provide a new approach to the already famous conjecture that claims that every tree is super edge magic. We attack this problem by finding for any given tree T a super edge magic tree T' that contains T as a subgraph, and the order of T'is not too large if we compare it with the order of T .

  A similar problem to this one, in the sense of finding small host super edge magic graphs for certain type of graphs, which is completely solved in the thesis, is the following one.

  Problem: Find the smallest order of a connected super edge magic graph G that contains the complete graph Kn as a subgraph.

  The solution of this problem has particular interest since it relates super edge magic labelings with the additive number theoretical concept of weak Sidon set, also known as well spread set. In fact , this is not the only time that this concept appears in the thesis.

  Also when studying the super edge magic deficiency, additive number theory and in particular well spread sets have proven to be very useful. The super edge magic deficiency of graph is a way of measuring how close is graph to be super edge magic.

  Properly speaking, the super edge magic deficiency of a graph G is defined to be the minimum number of isolated vertices that we have to union G with, so that the resulting graph is super edge magic. If no matter how many isolated vertices we union G with, the resulting graph is never super edge magic, then the super edge magic deficiency is defined to be infinity. In the thesis, we compute the super edge magic deficiency of may important families of graphs and we also provide some general results, involving this concept.

  Finally, and in order to bring this document to its end, I will just mention that many examples that improve the clarity of the thesis and makes it easy to read, can be found along the hole work.