Magic graphs

Author

Muntaner Batlle, Francesc Antoni

Director

Lladó Sánchez, Anna

Date of defense

2001-11-29

ISBN

8468931578

Legal Deposit

B.37098-2005



Department/Institute

Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV

Abstract

DE LA TESIS<br/>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 l'estudi del conjunt de grafs que admeten etiquetaments super edge magic així com també a desenvolupar relacions entre aquest tipus d'etiquetaments i altres etiquetaments molt estudiats com ara els etiquetaments graciosos i armònics, entre d'altres. De fet, els etiquetaments super edge magic serveixen com nexe d'unió entre diferents tipus d'etiquetaments, i per tant moltes relacions entre etiquetaments poden ser obtingudes d'aquesta forma. <br/>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 l'ordre de T'no és massa gran quan el comparam amb l'ordre de T . <br/>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.<br/>Problema: Quin és un graf conexe G super edge magic d'ordre més petit que conté al graf complet &#61486;<br/>Kn com a subgraf?.<br/>La solució d'aquest 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 d'una gran utilitat. La deficiencia super edge magic d'un graf és una manera de mesurar quan d'aprop està un graf de ser super edge magic. Tècnicament parlant, la deficiència super edge magic d'un graf &#61486;<br/>G es defineix com el mínim número de vèrtexs aillats amb els que hem d'unir<br/>G perque el graf resultant sigui super edge magic. Si d'aquesta 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.<br/>Per acabar aquest document, simplement diré que al llarg de la tesis molts d'exemples que completen la tesis, i que fan la seva lectura més agradable i entenible han estat introduits.


OF THESIS<br/>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.<br/>For instance, graceful and harmonic labelings, among others, since many relations among labelings can be obtained using super edge magic labelings as the link.<br/>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 .<br/>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.<br/>Problem: Find the smallest order of a connected super edge magic graph G that contains the complete graph Kn as a subgraph.<br/>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.<br/>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.<br/>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.<br/>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.

Keywords

magic graphs; graphs

Subjects

519.1 - Combinatorial analysis. Graph theory

Knowledge Area

1200. Matemàtiques

Documents

01Famb01de13.pdf

32.33Kb

02Famb02de13.pdf

44.15Kb

03Famb03de13.pdf

84.50Kb

04Famb04de13.pdf

5.970Mb

05Famb05de13.pdf

6.632Mb

06Famb06de13.pdf

2.805Mb

07Famb07de13.pdf

6.313Mb

08Famb08de13.pdf

3.153Mb

09Famb09de13.pdf

6.664Mb

10Famb10de13.pdf

3.836Mb

11Famb11de13.pdf

5.880Mb

12Famb12de13.pdf

5.005Mb

13Famb13de13.pdf

1.432Mb

 

Rights

ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs.

This item appears in the following Collection(s)