To see the other types of publications on this topic, follow the link: Graph labelings.
Dissertations / Theses on the topic 'Graph labelings'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Graph labelings.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Chan, Tsz-lung. "Graceful labelings of infinite graphs." Click to view the E-thesis via HKUTO, 2007. http://sunzi.lib.hku.hk/hkuto/record/B39332184.
Full text
2
Chan, Tsz-lung, and 陳子龍. "Graceful labelings of infinite graphs." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2007. http://hub.hku.hk/bib/B39332184.
Full text
3
Moragas, Vilarnau Jordi. "Graph labelings and decompositions by partitioning sets of integers." Doctoral thesis, Universitat Politècnica de Catalunya, 2010. http://hdl.handle.net/10803/5859.
Full textAbstract:
Aquest treball és una contribució a l'estudi de diferents problemes que sorgeixen de dues àrees fortament connexes de la Teoria de Grafs: etiquetaments i descomposicions. Molts etiquetaments de grafs deuen el seu origen als presentats l'any 1967 per Rosa. Un d'aquests etiquetaments, àmpliament conegut com a etiquetament graceful, va ser definit originalment com a eina per atacar la conjectura de Ringel, la qual diu que el graf complet d'ordre 2m+1 pot ser descompost en m copies d'un arbre donat de mida m. Aquí, estudiem etiquetaments relacionats que ens donen certes aproximacions a la conjectura de Ringel, així com també a una altra conjectura de Graham i Häggkvist que, en una forma dèbil, demana la descomposició d'un graf bipartit complet per un arbre donat de mida apropiada. Les principals contribucions que hem fet en aquest tema són la prova de la darrera conjectura per grafs bipartits complets del doble de mida essent descompostos per arbres de gran creixement i un nombre primer d'arestes, i la prova del fet que cada arbre és un subarbre gran de dos arbres pels quals les dues conjectures es compleixen respectivament. Aquests resultats estan principalment basats en una aplicació del mètode polinomial d'Alon.
Un altre tipus d'etiquetaments, els etiquetaments magic, també són tractats aquí. Motivats per la noció de quadrats màgics de Teoria de Nombres, en aquest tipus d'etiquetaments volem asignar nombres enters a parts del graf (vèrtexs, arestes, o vèrtexs i arestes) de manera que la suma de les etiquetes assignades a certes subestructures del graf sigui constant. Desenvolupem tècniques basades en particions de certs conjunts d'enters amb algunes condicions additives per construir etiquetaments cycle-magic, un nou tipus d'etiquetament introduït en aquest treball i que estén la noció clàssica d'etiquetament magic. Els etiquetaments magic no donen cap descomposició de grafs, però les tècniques usades per obtenir-los estan al nucli d'un altre problema de descomposició, l'ascending subgraph decomposition (ASD). Alavi, Boals, Chartrand, Erdös i Oellerman, van conjecturar l'any 1987 que tot graf té un ASD.
Aquí, estudiem l'ASD per grafs bipartits, una classe de grafs per la qual la conjectura encara no ha estat provada. Donem una condició necessària i una de suficient sobre la seqüència de graus d'un estable del graf bipartit de manera que admeti un ASD en que cada factor sigui un star forest. Les tècniques utilitzades estan basades en l'existència de branca-acoloriments en multigrafs bipartits.
També tractem amb el sumset partition problem, motivat per la conjectura ASD, que demana una partició de [n] de manera que la suma dels elements de cada part sigui igual a un valor prescrit. Aquí donem la millor condició possible per la versió modular del problema que ens permet provar els millors resultats ja coneguts en el cas enter per n primer. La prova està de nou basada en el mètode polinomial.
This work is a contribution to the study of various problems that arise from two strongly connected areas of the Graph Theory: graph labelings and graph decompositions. Most graph labelings trace their origins to the ones presented in 1967 by Rosa. One of these labelings, widely known as the graceful labeling, originated as a means of attacking the conjecture of Ringel, which states that the complete graph of order 2m+1 can be decomposed into m copies of a given tree of size m. Here, we study related labelings that give some approaches to Ringel's conjecture, as well as to another conjecture by Graham and Häggkvist that, in a weak form, asks for the decomposition of a complete bipartite graph by a given tree of appropriate size.
Our main contributions in this topic are the proof of the latter conjecture for double sized complete bipartite graphs being decomposed by trees with large growth and prime number of edges, and the proof of the fact that every tree is a large subtree of two trees for which both conjectures hold respectively. These results are mainly based on a novel application of the so-called polynomial method by Alon.
Another kind of labelings, the magic labelings, are also treated. Motivated by the notion of magic squares in Number Theory, in these type of labelings we want to assign integers to the parts of a graph (vertices, edges, or vertices and edges) in such a way that the sums of the labels assigned to certain substructures of the graph remain constant. We develop techniques based on partitions of certain sets of integers with some additive conditions to construct cycle-magic labelings, a new brand introduced in this work that extends the classical magic labelings. Magic labelings do not provide any graph decomposition, but the techniques that we use to obtain them are the core of another decomposition problem, the ascending subgraph decomposition (ASD).
In 1987, was conjectured by Alavi, Boals. Chartrand, Erdös and Oellerman that every graph has an ASD. Here, we study ASD of bipartite graphs, a class of graphs for which the conjecture has not been shown to hold. We give a necessary and a sufficient condition on the one sided degree sequence of a bipartite graph in order that it admits an ASD by star forests. Here the techniques are based on the existence of edge-colorings in bipartite multigraphs.
Motivated by the ASD conjecture we also deal with the sumset partition problem, which asks for a partition of [n] in such a way that the sum of the elements of each part is equal to a prescribed value. We give a best possible condition for the modular version of the sumset partition problem that allows us to prove the best known results in the integer case for n a prime. The proof is again based on the polynomial method.
4
Zhou, Haiying. "Distance-two constrained labeling and list-labeling of some graphs." HKBU Institutional Repository, 2013. https://repository.hkbu.edu.hk/etd_ra/1555.
Full textAbstract:
The distance-two constrained labeling of graphs arises in the context of frequency assignment problem (FAP) in mobile and wireless networks. The frequency assignment problem is the problem of assigning frequencies to the stations of a network, so that interference between nearby stations is avoided or minimized while the frequency reusability is exploited. It was first formulated as a graph coloring problem by Hale, who introduced the notion of the T-coloring of a graph, and that attracts a lot of interest in graph coloring. In 1988, Roberts proposed a variation of the channel assignment problem in which “close transmitters must receive different channels and “very close transmitters must receive channels at least two apart. Motivated by this variation, Griggs and Yeh first proposed and studied the L(2, 1)-labeling of a simple graph with a condition at distance two. Because of practical and theoretical applications, the interest for distance-two constrained labeling of graphs is increasing. Since then, many aspects of the problem and related problems remain to be further explored. In this thesis, we first give an upper bound of the L(2, 1)-labeling number, or simply λ number, for a special class of graphs, the n-cubes Qn, where n = 2k k 1. Chang et al. [3] considered a generalization of L(2, 1)-labeling, namely, L(d, 1)- labeling of graphs. We study the L(1, 1)-labeling number of Qn. A lower bound onλ1(Qn) is provided and λ1(Q2k1) is determined. As a related problem, the L(2, 1)-choosability of graphs is studied. Vizing [17] and Erdos et al. [18] generalized the graph coloring problem and introduced the list coloring problem independently more than three decades ago. We shall consider a new variation of the L(2, 1)-labeling problem, the list-L(2, 1)-labeling problem. We determine the L(2, 1)-choice numbers for paths and cycles. We also study the L(2, 1)- choosability for some special graphs such as the Cartesian product graphs and the generalized Petersen graphs. We provide upper bounds of the L(2, 1)-choice numbers for the Cartesian product of a path and a spider, also for the generalized Petersen graphs. Keywords: distance-two labeling, λ-number, L(2, 1)-labeling, L(d, 1)-labeling, list-L(2, 1)-labeling, choosability, L(2, 1)-choice number, path, cycle, n-cube, spider, Cartesian product graph, generalized Petersen graph.
5
Cheng, Hee Lin. "Supermagic labeling, edge-graceful labeling and edge-magic index of graphs." HKBU Institutional Repository, 2000. http://repository.hkbu.edu.hk/etd_ra/280.
Full text
6
Wu, Qiong. "Distance two labeling of some products of graphs." HKBU Institutional Repository, 2013. http://repository.hkbu.edu.hk/etd_ra/1487.
Full text
7
Ling, Man Ho. "Full friendly index sets of cartesian product of two cycles." HKBU Institutional Repository, 2008. http://repository.hkbu.edu.hk/etd_ra/918.
Full text
8
Wong, Fook Sun. "Full friendly index sets of Cartesian products of cycles and paths." HKBU Institutional Repository, 2010. http://repository.hkbu.edu.hk/etd_ra/1239.
Full text
9
Lin, Wensong. "Circular chromatic numbers and distance two labelling numbers of graphs." HKBU Institutional Repository, 2004. http://repository.hkbu.edu.hk/etd_ra/591.
Full text
10
Chavez, Dolores. "Investigation of 4-cutwidth critical graphs." CSUSB ScholarWorks, 2006. https://scholarworks.lib.csusb.edu/etd-project/3081.
Full textAbstract:
A 2004 article written by Yixun Lin and Aifeng Yang published in the journal Discrete Math characterized the set of a 3-cutwidth critical graphs by five specified elements. This project extends the idea to 4-cutwidth critical graphs.
11
Wang, Yi Ming. "Graph-based data selection for statistical machine translation." Thesis, University of Macau, 2017. http://umaclib3.umac.mo/record=b3691542.
Full text
12
Aftene, Florin. "Vertex-Relaxed Graceful Labelings of Graphs and Congruences." TopSCHOLAR®, 2018. https://digitalcommons.wku.edu/theses/2664.
Full textAbstract:
A labeling of a graph is an assignment of a natural number to each vertex
of a graph. Graceful labelings are very important types of labelings. The study of graceful labelings is very difficult and little has been shown about such labelings. Vertex-relaxed graceful labelings of graphs are a class of labelings that include graceful labelings, and their study gives an approach to the study of graceful labelings. In this thesis we generalize the congruence approach of Rosa to obtain new criteria for vertex-relaxed graceful labelings of graphs. To do this, we generalize Faulhaber’s Formula, which is a famous result about sums of powers of integers.
13
Gu, Guohua. "Distance-two constrained labellings of graphs and related problems." HKBU Institutional Repository, 2005. http://repository.hkbu.edu.hk/etd_ra/590.
Full text
14
Marr, Alison M. "Labelings of directed graphs /." Available to subscribers only, 2007. http://proquest.umi.com/pqdweb?did=1362527421&sid=22&Fmt=2&clientId=1509&RQT=309&VName=PQD.
Full text
15
Xiang, Yang. "Reachability, Routing and Distance Labeling Schemes in Graphs with Applications in Networks and Graph Databases." Kent State University / OhioLINK, 2009. http://rave.ohiolink.edu/etdc/view?acc_num=kent1258172703.
Full text
16
Sugeng, Kiki Ariyanti University of Ballarat. "Magic and antimagic labeling of graphs." University of Ballarat, 2005. http://archimedes.ballarat.edu.au:8080/vital/access/HandleResolver/1959.17/12758.
Full textAbstract:
"A bijection mapping that assigns natural numbers to vertices and/or edges of a graph is called a labeling. In this thesis, we consider graph labelings that have weights associated with each edge and/or vertex. If all the vertex weights (respectively, edge weights) have the same value then the labeling is called magic. If the weight is different for every vertex (respectively, every edge) then we called the labeling antimagic. In this thesis we introduce some variations of magic and antimagic labelings and discuss their properties and provide corresponding labeling schemes. There are two main parts in this thesis. One main part is on vertex labeling and the other main part is on edge labeling."Doctor of Philosophy
17
Sugeng, Kiki Ariyanti. "Magic and antimagic labeling of graphs." University of Ballarat, 2005. http://archimedes.ballarat.edu.au:8080/vital/access/HandleResolver/1959.17/15385.
Full textAbstract:
"A bijection mapping that assigns natural numbers to vertices and/or edges of a graph is called a labeling. In this thesis, we consider graph labelings that have weights associated with each edge and/or vertex. If all the vertex weights (respectively, edge weights) have the same value then the labeling is called magic. If the weight is different for every vertex (respectively, every edge) then we called the labeling antimagic. In this thesis we introduce some variations of magic and antimagic labelings and discuss their properties and provide corresponding labeling schemes. There are two main parts in this thesis. One main part is on vertex labeling and the other main part is on edge labeling."Doctor of Philosophy
18
Dafik, University of Ballarat. "Structural Properties and Labeling of Graphs." University of Ballarat, 2007. http://archimedes.ballarat.edu.au:8080/vital/access/HandleResolver/1959.17/12809.
Full textAbstract:
The complexity in building massive scale parallel processing systems has re- sulted in a growing interest in the study of interconnection networks design. Network design affects the performance, cost, scalability, and availability of parallel computers. Therefore, discovering a good structure of the network is one of the basic issues. From modeling point of view, the structure of networks can be naturally stud- ied in terms of graph theory. Several common desirable features of networks, such as large number of processing elements, good throughput, short data com- munication delay, modularity, good fault tolerance and diameter vulnerability correspond to properties of the underlying graphs of networks, including large number of vertices, small diameter, high connectivity and overall balance (or regularity) of the graph or digraph. The first part of this thesis deals with the issue of interconnection networks ad- dressing system. From graph theory point of view, this issue is mainly related to a graph labeling. We investigate a special family of graph labeling, namely antimagic labeling of a class of disconnected graphs. We present new results in super (a; d)-edge antimagic total labeling for disjoint union of multiple copies of special families of graphs. The second part of this thesis deals with the issue of regularity of digraphs with the number of vertices close to the upper bound, called the Moore bound, which is unobtainable for most values of out-degree and diameter. Regularity of the underlying graph of a network is often considered to be essential since the flow of messages and exchange of data between processing elements will be on average faster if there is a similar number of interconnections coming in and going out of each processing element. This means that the in-degree and out-degree of each processing element must be the same or almost the same. Our new results show that digraphs of order two less than Moore bound are either diregular or almost diregular.Doctor of Philosophy
19
Dafik. "Structural Properties and Labeling of Graphs." University of Ballarat, 2007. http://archimedes.ballarat.edu.au:8080/vital/access/HandleResolver/1959.17/13722.
Full textAbstract:
The complexity in building massive scale parallel processing systems has re- sulted in a growing interest in the study of interconnection networks design. Network design affects the performance, cost, scalability, and availability of parallel computers. Therefore, discovering a good structure of the network is one of the basic issues. From modeling point of view, the structure of networks can be naturally stud- ied in terms of graph theory. Several common desirable features of networks, such as large number of processing elements, good throughput, short data com- munication delay, modularity, good fault tolerance and diameter vulnerability correspond to properties of the underlying graphs of networks, including large number of vertices, small diameter, high connectivity and overall balance (or regularity) of the graph or digraph. The first part of this thesis deals with the issue of interconnection networks ad- dressing system. From graph theory point of view, this issue is mainly related to a graph labeling. We investigate a special family of graph labeling, namely antimagic labeling of a class of disconnected graphs. We present new results in super (a; d)-edge antimagic total labeling for disjoint union of multiple copies of special families of graphs. The second part of this thesis deals with the issue of regularity of digraphs with the number of vertices close to the upper bound, called the Moore bound, which is unobtainable for most values of out-degree and diameter. Regularity of the underlying graph of a network is often considered to be essential since the flow of messages and exchange of data between processing elements will be on average faster if there is a similar number of interconnections coming in and going out of each processing element. This means that the in-degree and out-degree of each processing element must be the same or almost the same. Our new results show that digraphs of order two less than Moore bound are either diregular or almost diregular.Doctor of Philosophy
20
Niedzialomski, Amanda Jean. "Consecutive radio labelings and the Cartesian product of graphs." Diss., University of Iowa, 2013. https://ir.uiowa.edu/etd/4886.
Full textAbstract:
For k∈{Z}+ and G a simple connected graph, a k-radio labeling f:VG→Z+ of G requires all pairs of distinct vertices u and v to satisfy |f(u)-f(v)|≥ k+1-d(u,v). When k=1, this requirement gives rise to the familiar labeling known as vertex coloring for which each vertex of a graph is labeled so that adjacent vertices have different "colors". We consider k-radio labelings of G when k=diam(G). In this setting, no two vertices can have the same label, so graphs that have radio labelings of consecutive integers are one extreme on the spectrum of possibilities; graphs that can be labeled with such a labeling are called radio graceful. In this thesis, we give four main results on the existence of radio graceful graphs, which focus on Hamming graphs (Cartesian products of complete graphs) and a generalization of the Petersen graph. In particular, we prove the existence of radio graceful graphs of arbitrary diameter, a result previously unknown. Two of these main results show that, under certain conditions, the tth Cartesian power Gt of a radio graceful graph G is also radio graceful. We will also speak to occasions when Gt is not radio graceful despite G being so, as well as some partial results about necessary and sufficient conditions for a graph G so that Gt is radio graceful.
21
Meadows, Adam M. "Decompositions of Mixed Graphs with Partial Orientations of the P4." Digital Commons @ East Tennessee State University, 2009. https://dc.etsu.edu/etd/1870.
Full textAbstract:
A decomposition D of a graph H by a graph G is a partition of the edge set of H such that the subgraph induced by the edges in each part of the partition is isomorphic to G. A mixed graph on V vertices is an ordered pair (V,C), where V is a set of vertices, |V| = v, and C is a set of ordered and unordered pairs, denoted (x, y) and [x, y] respectively, of elements of V [8]. An ordered pair (x, y) ∈ C is called an arc of (V,C) and an unordered pair [x, y] ∈ C is called an edge of graph (V,C). A path on n vertices is denoted as Pn. A partial orientation on G is obtained by replacing each edge [x, y] ∈ E(G) with either (x, y), (y, x), or [x, y] in such a way that there are twice as many arcs as edges. The complete mixed graph on v vertices, denoted Mv, is the mixed graph (V,C) where for every pair of distinct vertices v1, v2 ∈ V , we have {(v1, v2), (v2, v1), [v1, v2]} ⊂ C. The goal of this thesis is to establish necessary and sufficient conditions for decomposition of Mv by all possible partial orientations of P4.
22
Hillgren, Patrik. "Geometric Scene Labeling for Long-Range Obstacle Detection." Thesis, Linköpings universitet, Datorseende, 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-113126.
Full textAbstract:
Autonomous Driving or self driving vehicles are concepts of vehicles knowing their environment and making driving manoeuvres without instructions from a driver. The concepts have been around for decades but has improved significantly in the last years since research in this area has made significant progress. Benefits of autonomous driving include the possibility to decrease the number of accidents in traffic and thereby saving lives. A major challenge in autonomous driving is to acquire 3D information and relations between all objects in surrounding traffic. This is referred to as \textit{spatial perception}. Stereo camera systems have become a central sensor module for advanced driver assistance systems and autonomous driving. For object detection and measurements at large distances stereo vision encounter difficulties. This includes objects being small, having low contrast and the presence of image noise. Having an accurate perception of the environment at large distances is however of high interest for many applications, especially autonomous driving. This thesis proposes a method which tries to increase the range to where generic objects are first detected using a given stereo camera setup. Objects are represented by planes in 3D space. The input image is segmented into the various objects and the 3D plane parameters are estimated jointly. The 3D plane parameters are estimated directly from the stereo image pairs. In particular, this thesis investigates methods to introduce geometric constraints to the segmentation or labeling task, i.e assigning each considered pixel in the image to a plane. The methods provided in this thesis show that despite the difficulties at large distances it is possible to exploit planar primitives in 3D space for obstacle detection at distances where other methods fail.En autonom bil innebär att bilen har en uppfattning om sin omgivning och kan utifran det ta beslut angående hur bilen ska manövreras. Konceptet med självkörande bilar har existerat i årtionden men har utvecklats snabbt senaste åren sedan billigare datorkraft finns lättare tillgänglig. Fördelar med autonomiska bilar innebär bland annat att antalet olyckor i trafiken minskas och därmed liv räddas. En av de största utmaningarna med autonoma bilar är att få 3D information och relationer mellan objekt som finns i den omgivande trafikmiljön. Detta kallas för spatial perception och innebär att detektera alla objekt och tilldela en korrekt postition till dem. Stereo kamerasystem har fått en central roll för avancerade förarsystem och autonoma bilar. För detektion av objekt på stora avstånd träffar stereo system på svårigheter. Detta inkluderar väldigt små objekt, låg kontrast och närvaron av brus i bilden. Att ha en ackurativ perception på stora avstånd är dock vitalt för många applikationer, inte minst autonoma bilar. Den här rapporten föreslar en metod som försöker öka avståndet till där objekt först upptäcks. Objekt representeras av plan i 3D rymden. Bilder givna från stereo par segmenteras i olika object och plan parametrar estimeras samtidigt. Planens parametrar estimeras direkt från stereo bild paren. Den här rapporten utreder metoder att introducera gemoetriska begränsningar att använda vid segmenteringsuppgiften. Metoderna som presenteras i denna rapport visar att trots den höga närvaron av brus på stora avstånd är det möjligt att estimera geometriska objekt som är starka nog att möjliggöra detektion av objekt på ett avstand där andra metoder misslyckas.
23
Tener, Greg. "ATTACKS ON DIFFICULT INSTANCES OF GRAPH ISOMORPHISM: SEQUENTIAL AND PARALLEL ALGORITHMS." Doctoral diss., University of Central Florida, 2009. http://digital.library.ucf.edu/cdm/ref/collection/ETD/id/2631.
Full textAbstract:
The graph isomorphism problem has received a great deal of attention on both theoretical and practical fronts. However, a polynomial algorithm for the problem has yet to be found. Even so, the best of the existing algorithms perform well in practice; so well that it is challenging to find hard instances for them. The most efficient algorithms, for determining if a pair of graphs are isomorphic, are based on the individualization-refinement paradigm, pioneered by Brendan McKay in 1981 with his algorithm nauty. Nauty and various improved descendants of nauty, such as bliss and saucy, solve the graph isomorphism problem by determining a canonical representative for each of the graphs. The graphs are isomorphic if and only if their canonical representatives are identical. These algorithms also detect the symmetries in a graph which are used to speed up the search for the canonical representative--an approach that performs well in practice. Yet, several families of graphs have been shown to exist which are hard for nauty-like algorithms. This dissertation investigates why these graph families pose difficulty for individualization-refinement algorithms and proposes several techniques for circumventing these limitations. The first technique we propose addresses a fundamental problem pointed out by Miyazaki in 1993. He constructed a family of colored graphs which require exponential time for nauty (and nauty's improved descendants). We analyze Miyazaki's construction to determine the source of difficulty and identify a solution. We modify the base individualization-refinement algorithm by exploiting the symmetries discovered in a graph to guide the search for its canonical representative. This is accomplished with the help of a novel data structure called a guide tree. As a consequence, colored Miyazaki graphs are processed in polynomial time--thus obviating the only known exponential upper-bound on individualization-refinement algorithms (which has stood for the last 16 years). The preceding technique can only help if a graph has enough symmetry to exploit. It cannot be used for another family of hard graphs that have a high degree of regularity, but possess few actual symmetries. To handle these instances, we introduce an adaptive refinement method which utilizes the guide-tree data structure of the preceding technique to use a stronger vertex-invariant, but only when needed. We show that adaptive refinement is very effective, and it can result in dramatic speedups. We then present a third technique ideally suited for large graphs with a preponderance of sparse symmetries. A method was devised by Darga et al. for dealing with these large and highly symmetric graphs, which can reduce runtime by an order of magnitude. We explain the method and show how to incorporate it into our algorithm. Finally, we develop and implement a parallel algorithm for detecting the symmetries in, and finding a canonical representative of a graph. Our novel parallel algorithm divides the search for the symmetries and canonical representative among each processor, allowing for a high degree of scalability. The parallel algorithm is benchmarked on the hardest problem instances, and shown to be effective in subdividing the search space.Ph.D.
School of Electrical Engineering and Computer Science
Engineering and Computer Science
Computer Science PhD
24
Benson, Katherine Forcelle. "On Radio Labeling of Diameter N-2 and Caterpillar Graphs." Diss., University of Iowa, 2013. https://ir.uiowa.edu/etd/4822.
Full textAbstract:
Radio labeling of graphs is a specific type of graph labeling. Radio labeling evolved as a way to use graph theory to try to solve the channel assignment problem: how to assign radio channels so that two radio transmitters that are relatively close to one another do not have frequencies that cause interference between them. This problem of channel assignment was first put into a graph theoretic context by Hale. In terms of graph theory, the vertices of a graph represent the locations of the radio transmitters, or radio stations, with the labels of the vertices corresponding to channels or frequencies assigned to the stations.
Different restrictions on labelings of graphs have been studied to address the channel assignment problem. Radio labeling of a simple connected graph G is a labeling f from the vertex set of G to the positive integers such that for every pair of distinct vertices u and v of G, distance(u,v) + |f(u)-f(v)| is greater than or equal to diameter(G) +1. The largest number used to label a vertex of G is called the span of the labeling. The radio number of G is the smallest possible span for a radio labeling of G. The radio numbers of certain families of graphs have already been found. In particular, bounds and radio numbers of some tree graphs have been determined. Daphne Der-Fen Liu and Xuding Zhu determined the radio number of paths and Daphne Der-Fen Liu found a general lower bound for the radio number of trees.
This thesis builds off of work done on paths and trees in general to determine an improved lower bound or the actual radio number of certain graphs. This thesis includes joint work with Matthew Porter and Maggy Tomova on determining the radio numbers of graphs with n vertices and diameter n-2. This thesis also establishes the radio number of some specific caterpillar graphs as well as an improved lower bound for the radio number of more general caterpillar graphs.
25
Chen, Ying-Ren, and 陳盈任. "Two Edge Labelings in Graphs :Graph Decomposition and Antimagic Labeling." Thesis, 2013. http://ndltd.ncl.edu.tw/handle/33607894499191942857.
Full textAbstract:
博士國立中央大學
數學系
101
Graph decomposition is an important subject of graph theory. Many combinatorial, algebraic, and other mathematical structures are linked to decompositions of graphs, which gives their study a great theoretical importance. On the other hand, results on graph decompositions can be applied in coding theory, design of experiments, computer and communication networks, and other fields. Nowadays, graph decomposition ranks the most prominent area in graph theorey, even in combinatorics. A graph is called an antimagic graph, if there exists an edge labeling which is an assignment of integers to the vertices or edges, or both, subject to certain conditions. Graph labelings were first introduced in the late 1960s. In the intervening years dozens of graph labelings techniques have been studied in over 1500 papers. Graph labeling can be applied in computer and communication networks, applied statistics research, and some design science other fields.
26
Wijaya, Rachel Wulan Nirmalasari. "Advances in graph labelings." Thesis, 2018. http://hdl.handle.net/1959.13/1384118.
Full textAbstract:
Masters Research - Master of Philosophy (MPhil)A graph labeling is a mapping that assigns natural numbers to vertices and/or edges of a graph. In this thesis, we consider two types of labeling; magic and irregular labeling. In both labelings, we label both vertices and edges of the graph. This type of labeling is called total labeling. In irregular labeling we can repeat some numbers in the graph, but the weights of every graph element are pairwise distinct. A graph is called H-supermagic if the weight of every subgraph H of the graph is constant. In magic labeling, we prove that banana tree, firecracker, flower and grid graph are H-supermagic. Banana tree graph is an amalgamation of connected graphs. Therefore result for banana trees is an immediate consequence of a theorem about amalgamations of connected graphs from Maryati et al. The result for firecracker graph is obtained by a similar method. For flower graph, we provide results for odd order. In the grid graphs, we prove that it is H-supermagic by induction. In irregular labeling, we consider the weight of the corresponding edges. If the weight of every edge is different we called the labeling edge irregular total labeling. We prove that the grid graphs are edge irregular.
27
Barone, Chedomir Angelo. "Magic labelings of directed graphs." Thesis, 2008. http://hdl.handle.net/1828/898.
Full textAbstract:
Let G be a directed graph with a total labeling. The additive arc-weight of an arc xy is the sum of the label on xy and the label on y. The additive directed vertex-weight of a vertex x is the sum of the label on x and the labels on all arcs with head at x. The graph is additive arc magic if all additive arc-weights are equal, and is additive directed vertex magic if all vertex-weights are equal. We provide a complete characterization of all graphs which permit an additive arc magic labeling. A complete characterization of all regular graphs which may be oriented to permit an additive directed vertex magic labeling is provided. The definition of the subtractive arc-weight of an arc xy is proposed, and a correspondence between graceful labelings and subtractive arc magic labelings is shown.
28
"Graph labelings and decompositions by partitioning sets of integers." Universitat Politècnica de Catalunya, 2010. http://www.tesisenxarxa.net/TDX-0708110-134932/.
Full text
29
"Graph-based recommendation with label propagation." 2011. http://library.cuhk.edu.hk/record=b5894820.
Full textAbstract:
Wang, Dingyan.Thesis (M.Phil.)--Chinese University of Hong Kong, 2011.
Includes bibliographical references (p. 97-110).
Abstracts in English and Chinese.
Abstract --- p.ii
Acknowledgement --- p.vi
Chapter 1 --- Introduction --- p.1
Chapter 1.1 --- Overview --- p.1
Chapter 1.2 --- Motivations --- p.6
Chapter 1.3 --- Contributions --- p.9
Chapter 1.4 --- Organizations of This Thesis --- p.11
Chapter 2 --- Background --- p.14
Chapter 2.1 --- Label Propagation Learning Framework --- p.14
Chapter 2.1.1 --- Graph-based Semi-supervised Learning --- p.14
Chapter 2.1.2 --- Green's Function Learning Framework --- p.16
Chapter 2.2 --- Recommendation Methods --- p.19
Chapter 2.2.1 --- Traditional Memory-based Methods --- p.19
Chapter 2.2.2 --- Traditional Model-based Methods --- p.20
Chapter 2.2.3 --- Label Propagation Recommendation Models --- p.22
Chapter 2.2.4 --- Latent Feature Recommendation Models . --- p.24
Chapter 2.2.5 --- Social Recommendation Models --- p.25
Chapter 2.2.6 --- Tag-based Recommendation Models --- p.25
Chapter 3 --- Recommendation with Latent Features --- p.28
Chapter 3.1 --- Motivation and Contributions --- p.28
Chapter 3.2 --- Item Graph --- p.30
Chapter 3.2.1 --- Item Graph Definition --- p.30
Chapter 3.2.2 --- Item Graph Construction --- p.31
Chapter 3.3 --- Label Propagation Recommendation Model with Latent Features --- p.33
Chapter 3.3.1 --- Latent Feature Analysis --- p.33
Chapter 3.3.2 --- Probabilistic Matrix Factorization --- p.35
Chapter 3.3.3 --- Similarity Consistency Between Global and Local Views (SCGL) --- p.39
Chapter 3.3.4 --- Item-based Green's Function Recommendation Based on SCGL --- p.41
Chapter 3.4 --- Experiments --- p.41
Chapter 3.4.1 --- Dataset --- p.43
Chapter 3.4.2 --- Baseline Methods --- p.43
Chapter 3.4.3 --- Metrics --- p.45
Chapter 3.4.4 --- Experimental Procedure --- p.45
Chapter 3.4.5 --- Impact of Weight Parameter u --- p.46
Chapter 3.4.6 --- Performance Comparison --- p.48
Chapter 3.5 --- Summary --- p.50
Chapter 4 --- Recommendation with Social Network --- p.51
Chapter 4.1 --- Limitation and Contributions --- p.51
Chapter 4.2 --- A Social Recommendation Framework --- p.55
Chapter 4.2.1 --- Social Network --- p.55
Chapter 4.2.2 --- User Graph --- p.57
Chapter 4.2.3 --- Social-User Graph --- p.59
Chapter 4.3 --- Experimental Analysis --- p.60
Chapter 4.3.1 --- Dataset --- p.61
Chapter 4.3.2 --- Metrics --- p.63
Chapter 4.3.3 --- Experiment Setting --- p.64
Chapter 4.3.4 --- Impact of Control Parameter u --- p.65
Chapter 4.3.5 --- Performance Comparison --- p.67
Chapter 4.4 --- Summary --- p.69
Chapter 5 --- Recommendation with Tags --- p.71
Chapter 5.1 --- Limitation and Contributions --- p.71
Chapter 5.2 --- Tag-Based User Modeling --- p.75
Chapter 5.2.1 --- Tag Preference --- p.75
Chapter 5.2.2 --- Tag Relevance --- p.78
Chapter 5.2.3 --- User Interest Similarity --- p.80
Chapter 5.3 --- Tag-Based Label Propagation Recommendation --- p.83
Chapter 5.4 --- Experimental Analysis --- p.84
Chapter 5.4.1 --- Douban Dataset --- p.85
Chapter 5.4.2 --- Experiment Setting --- p.86
Chapter 5.4.3 --- Metrics --- p.87
Chapter 5.4.4 --- Impact of Tag and Rating --- p.88
Chapter 5.4.5 --- Performance Comparison --- p.90
Chapter 5.5 --- Summary --- p.92
Chapter 6 --- Conclusions and Future Work --- p.94
Chapter 6.0.1 --- Conclusions --- p.94
Chapter 6.0.2 --- Future Work --- p.96
Bibliography --- p.97
30
Gray, Ian. "Construction methods for vertex magic total labelings of graphs." Thesis, 2006. http://hdl.handle.net/1959.13/34369.
Full textAbstract:
Research Doctorate - Doctor of Philosophy (PhD)In this thesis, a number of new methods for constructing vertex-magic total-labelings of graphs are presented. These represent an advance on existing methods since they are general constructions rather than ad hoc constructions for specific families of graphs. Broadly, five new kinds of construction methods are presented. Firstly, we present a class of methods characterized by adding 2- or 4-factors to a labeled graph, reassigning vertex labels to the edges of these factors and then adding new vertex labels to create a VMTL of the new graph. The major result is a unified method for constructing VMTL of large families of regular graphs, providing strong evidence for MacDougall's conjecture that, apart from a few minor exceptions, all regular graphs possess vertex-magic total-labelings. Secondly, we present methods for obtaining a labeling of a union of two graphs, one of which possesses a strong labeling, and then building on this labeling to create a labeling of an irregular graph. These methods as well as results in the Appendices provide strong evidence against an early conjecture regarding labelings and vertex degrees. Thirdly, constructions are presented for a new kind of magic square, containing some zeroes, which can be used to build labelings of graphs from labeled spanning subgraphs. Next, constructions are presented for a new kind of anti-magic square, containing some zeroes, which is equivalent to a strong labeling of certain kinds of bipartite graphs which can in turn be built upon to produce labelings of graphs with more edges. Finally, we present a method of mutating a graph labeling by reassigning edges in a way that preserves the magic constant to obtain a labeling of a different graph. This method provides a prolific source of new labelings.
31
Gray, Ian. "Construction methods for vertex magic total labelings of graphs." 2006. http://hdl.handle.net/1959.13/34369.
Full textAbstract:
Research Doctorate - Doctor of Philosophy (PhD)In this thesis, a number of new methods for constructing vertex-magic total-labelings of graphs are presented. These represent an advance on existing methods since they are general constructions rather than ad hoc constructions for specific families of graphs. Broadly, five new kinds of construction methods are presented. Firstly, we present a class of methods characterized by adding 2- or 4-factors to a labeled graph, reassigning vertex labels to the edges of these factors and then adding new vertex labels to create a VMTL of the new graph. The major result is a unified method for constructing VMTL of large families of regular graphs, providing strong evidence for MacDougall's conjecture that, apart from a few minor exceptions, all regular graphs possess vertex-magic total-labelings. Secondly, we present methods for obtaining a labeling of a union of two graphs, one of which possesses a strong labeling, and then building on this labeling to create a labeling of an irregular graph. These methods as well as results in the Appendices provide strong evidence against an early conjecture regarding labelings and vertex degrees. Thirdly, constructions are presented for a new kind of magic square, containing some zeroes, which can be used to build labelings of graphs from labeled spanning subgraphs. Next, constructions are presented for a new kind of anti-magic square, containing some zeroes, which is equivalent to a strong labeling of certain kinds of bipartite graphs which can in turn be built upon to produce labelings of graphs with more edges. Finally, we present a method of mutating a graph labeling by reassigning edges in a way that preserves the magic constant to obtain a labeling of a different graph. This method provides a prolific source of new labelings.
32
Morgan, David. "Gracefully labelled trees from Skolem and related sequences /." 2001.
Find full text
33
Lin, Yuqing. "Topology and fault tolerance of interconnection networks." Thesis, 2003. http://hdl.handle.net/1959.13/1418188.
Full textAbstract:
Research Doctorate - Doctor of Philosophy (PhD)Interconnection networks is an enormous field which holds a very important position in both theory and practice. From a practical point of view, networks should be fast and reliable as much as possible. The performance of most network systems is limited by computational power as well as by interconnection capability. To improve the interconnection capability, we need to discover good network topology. Combining with more powerful hardware and more efficient algorithms, the performance of networks can be improved. The topology of networks is usually studied in ternis of graph theory. At the abstract level, interconnection networks are nothing but graphs, undirected or directed. Several comnion desirable features of networks such as high throughput, fast message exchange, fault tolerance and low complexity etc. correspond to properties of the underlying graphs of networks, including low degree, large number of nodes, high connectivity etc. Considering three parameters, namely, the number of vertices in a graph, degree and diameter, if we optimize each one of these three parameters in turn while holding the other two fixed, we obtain three optimization problems, namely, the degree/diameter problem, the order/degree problem and the order/diameter problem for both directed and undirected case. We shall discuss these three problems and show that certain monotonicity relationships hold among the parameters and among the problems. In this thesis we also deal with the issue of fault tolerance of networks. We investigate the connectivity of a particular type of network structure called (k;g)-cages. In 1997. Fu et al. conjectured that all (k;g)-cages are k-connected. This conjecture implies that all (k;g)-cages are k-edge-connected as well. We present new resuts with respect to edge-connectivity and combined with previous results from Balbuena et al. we completely solve the conjecture with respect to edge-connectivity. Additionally, we provide a positive contribution to the conjecture with respect to vertex-connectivity.
34
Kuo, David, and 郭大衛. "Graph Labeling Problems." Thesis, 1995. http://ndltd.ncl.edu.tw/handle/78481706283722764732.
Full textAbstract:
博士國立交通大學
應用數學研究所
83
A labeling problem in a graph $G$ is to assign numbers to vertices and/or edges of $G$ such that certain conditions hold. The most well-known problem probably is the map coloring problem. This problem was solved in 1976 by Appel and Haken. Many interesting results around this subject have been obtained. Besides the map coloring problem, there are many graph labeling problems, e.g., the $L(d,1)$-labeling problem, the cordial labeling problem, the integral sum number problem. This thesis studies the first three problems. In Chapter 2, we study the $L(d,1)$-labeling problem. The original idea of this problem was the channel assignment problem, Hale formulated this problem into the notion of the $T$-coloring of a graph. Roberts proposed a variation of the $T$-coloring problem, which is called the $L(2,1)$-labeling problem. Later, Yeh generalized this problem to the $L(d,1)$-labeling problem. In this thesis, we consider the problem for special graphs, such as paths, cycles, wheels, strongly chordal graphs, cographs, and trees. We also consider some basic properties of general graphs, such as the relations between the maximum degree $\Delta(G)$ and the $L(d,1)$-labeling number $\lambda_d(G)$; the relations between $\lambda_d(G), \lambda_d(H)$, $\lambda_d(G \cup H), \lambda_d(G+ H)$ for arbitrary graphs $G$ and $H$. In Chapter 3, we study the cordial labeling problem. This problem is a weaker version of the graceful labeling problem. In this thesis, we completely determine the cordiality of $mKn$, the union of $m$ copies of the complete graph of order $n$. In Chapter 4, we disscuess the integral sum number problem. The concepts of sum numbers and integral sum numbers were first introduced by Harary. In this thesis, we prove that the integral sum number $\zeta(G)=0$ when $G$ is a caterpilar, cycle, or wheel. We also find the integral sum number of complete bipartite graphs.
35
Tanna, Dushyant. "Graph labeling techniques." Thesis, 2017. http://hdl.handle.net/1959.13/1354312.
Full textAbstract:
Research Doctorate - Doctor of Philosophy (PhD)We give some background to the labeling schemes like graceful, harmonious, magic, antimagic and irregular total labelings. Followed by this we give some preliminary results and open problems in these schemes. We will introduce a new branch of irregular total labeling, irregular reflexive labeling. This new labeling technique has few variations on vertices labels from irregular total labeling. They are, 1) The vertices labels are non negative even integers. 2) The vertex label 0 is permissible, representing the vertex without loop. The vertex (edge) irregular reflexive labeling is a total irregular labeling with above conditions on vertices labeling such that the vertices (edges) weights are distinct. The idea is to use minimum possible labels for vertices (edges) and thus keeping the reflexive vertex (edge) strength as low as possible. We believe that this new technique is closer in concept to the original irregular labeling as proposed by Chartrand et al., since the vertex labels are also being used to represent edges(loops). Again the objective is to minimize the total strength by using the smallest vertices/edges labels. We will give edge and vertex irregular reflexive strengths for many graphs such as paths, cycles, stars, complete graphs, prisms, wheels, baskets, friendship graphs, join of graphs and generalised friendship graphs and present labeling techniques for these graphs. We also describe edge covering, H-edge covering, H-magic and H-antimagic graphs and prove some theorems based on these concepts. Many results have been established for construction of H-antimagic labelings of graphs. We will use the partitions of a set of integers with determined differences, the upper bound of the difference d if the graph GH is super (a,d)-H-antimagic, establishment of connection between H-antimagic labelings and edge-antimagic total labelings. We have also posed some open problems. Finally we address why study of graph labeling is important by explaining some applications of graph labeling and give some open problems and conjectures.
36
An-Chiang, Chu. "Distance Two Labelings on Graphs." 2005. http://www.cetd.com.tw/ec/thesisdetail.aspx?etdun=U0001-2806200516545000.
Full text
37
Chu, An-Chiang, and 朱安強. "Distance Two Labelings on Graphs." Thesis, 2005. http://ndltd.ncl.edu.tw/handle/05222790453510722050.
Full textAbstract:
碩士國立臺灣大學
數學研究所
93
An L(2,1)-labeling of a graph G is a function f : V (G) → N∪{0} such that for all u, v in V(G), we have |f(u) − f(v)| is not less than 2 if d(u,v) = 1, and |f(u) − f(v)| is not less than 1 if d(u,v) = 2. The L(2,1)-labeling number λ(G) of G is the smallest number k such that G has an L(2, 1)-labeling with max{f(v) : v in V (G)} = k. In this thesis, we review some proofs for the upper bounds of λ(G), and give an alternative proof for λ(G) is less than or equal to Δ^2+Δ−2.
38
Silalahi, Raphita Yanisari, and 施塔亞. "Antimagic Labelings on Disconnected Graphs." Thesis, 2019. http://ndltd.ncl.edu.tw/handle/pfqmq6.
Full textAbstract:
碩士國立中興大學
應用數學系所
107
Let G = (V (G), E(G)) with p vertices and q edges, and an edge labeling of G be a bijection f : E(G) → {1,2,...,q}. The (induced) vertex sum φ_f(u) : V(G) → ℕ of the edge labeling f is a function given by φ_f (u) := ∑_(uv∈E(G))f(uv) for all u ∈ V (G). A graph G is called antimagic if there exists an edge labeling of G such that vertex sums are all distinct for all vertices. We call the edge labeling of G is an antimagic labeling of G. Shang [4] conjectured that ”For m ∈ ℕ, the linear forest mP3 ∪ P4 is antimagic if and if m ≤ 2”. The conjecture is showed to be true for m ≤ 2 using a computer program but it is still widely open in general. In this thesis, we prove the conjecture is true and determine the value of m for which mP3 ∪ G is antimagic and non-antimagic for G being some paths or cycles.
39
Zhang, Huaming. "Graph orientation, labeling and their applications." 2005. http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&res_dat=xri:pqdiss&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&rft_dat=xri:pqdiss:3169111.
Full textAbstract:
Thesis (Ph.D.)--State University of New York at Buffalo, 2005.Title from PDF title page (viewed on Nov. 23, 2005) Available through UMI ProQuest Digital Dissertations. Thesis adviser: Xin He. Includes bibliographical references.
40
Panofsky, Ellen. "Graph labeling problems with distance conditions /." Diss., 2008. http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqdiss&rft_dat=xri:pqdiss:3314478.
Full text
41
Phanalasy, Oudone. "Antimagic labeling of graphs." Thesis, 2013. http://hdl.handle.net/1959.13/1036864.
Full textAbstract:
Research Doctorate - Doctor of Philosophy (PhD)The concept of labeling of graphs has attracted many researchers to this branch of research since the concept was introduced. It is becoming popular, partly because of mathematical challenges, and partly also because of the wide range of applications in other branches of science. A labeling of a graph is a map from one or more graphs elements to sets of numbers, for instance, labeling of edges, vertices, both edges and vertices, or edges, vertices and faces, if a labeling is applied to plane graph. Correspondingly, we distinguish edge labeling, vertex labeling, total labeling, or d-labeling. In this thesis we deal with edge labeling to contribute new results towards settling the Hartsfeld and Ringel conjecture that `Every graph different from K2 is antimagic'. We also prove that every graph has a vertex antimagic total labeling, and an edge antimagic total labeling if the graph contains no isolated vertex. We introduce the notion of totally antimagic total labeling and provide several initial results for such a labeling. Furthermore, we study super d-antimagic labeling and obtain several new results. Nevertheless, many open problems remain in antimagic labeling of graphs and we conclude the thesis by listing some of those that arose from our study.
42
Pei-Shan, Lee. "On Alpha-labelings of Prism Graphs and Gear Graphs." 2006. http://www.cetd.com.tw/ec/thesisdetail.aspx?etdun=U0017-1901200710274768.
Full text
43
Lee, Pei-Shan, and 李佩珊. "On Alpha-labelings of Prism Graphs and Gear Graphs." Thesis, 2006. http://ndltd.ncl.edu.tw/handle/93024595727329387774.
Full textAbstract:
碩士中原大學
應用數學研究所
94
Let G be a graph with q edges, we call a function f a β-labeling of G if f is an injective function from the vertices of G to{0,1,2, . . . , q} such that all values |f(u)−f(v)| for the q pairs of adjacent vertices u and v are distinct. A β-labeling is also known as a graceful labeling. An α-labeling is a graceful labeling with additional property that there is an integer λ such that for each edge uv either f(u)<=λ
44
Chen, Zhen-Chun, and 陳抮君. "Decompositions and Antimagic Labelings of Graphs." Thesis, 2015. http://ndltd.ncl.edu.tw/handle/43896930723186127150.
Full textAbstract:
博士國立中央大學
數學系
103
In this thesis, we investigate decompositions and antimagic labelings of graphs. In Chapter 1, we give some terminology and notation needed in the thesis. Chapter 2∼4 concern decompositions of graphs. Chapter 5 concerns antimagic labelings of graphs. In Chapter 2, we consider the problems about decompositions of the complete graphs Kn into two kinds of graphs, each with specific numbers of edges. In Chapter 3, the problems of the maximum (Pk; Sk)-packing, the minimum (Pk; Sk)- covering, the maximum (Ck; Sk)-packing and the minimum (Ck; Sk)-covering of Kn are investigated. In Chapter 4, we give necessary and sufficient conditions for the spiders to be t- decomposable. In Chapter 5, we obtain a necessary condition for the star forest to be antimagic and a sufficient condition for the star forest to be antimagic, and necessary and sufficient conditions for mS2 ∪ Sn to be antimagic.
45
Huang, Lian-Hwao, and 黃良豪. "Distance-two labelings of Hamming graphs." Thesis, 2003. http://ndltd.ncl.edu.tw/handle/79990950317378572849.
Full textAbstract:
碩士國立臺灣大學
數學研究所
91
An $L(2,1)$-labeling of a graph $G$ is a function $f$ from the vertex set $V(G)$ to the set of all nonnegative integers such that $|f(u)-f(v)|\geq 2$ if $d(u,v)=1$ and $|f(u)-f(v)|\geq 1$ if $d(u,v)=2$. For a nonnegative integer $k$, a $k$-$L(2,1)$-labeling is an $L(2,1)$-labeling such that no label is greater than $k$. The $L(2,1)$-labeling number of $G$, denoted by $\lambda(G)$, is the smallest number $k$ such that $G$ has a $k$-$L(2,1)$-labeling. In this thesis, we study $L(2,1)$-labeling numbers of cactuses and Hamming graphs.
46
Hsu, Yen-Wu, and 許炎午. "Graceful Labelings of Some Special Graphs." Thesis, 2015. http://ndltd.ncl.edu.tw/handle/15033129902556277565.
Full textAbstract:
碩士淡江大學
中等學校教師在職進修數學教學碩士學位班
103
Let G be a simple graph with q edges. If there exists a function f from V(G) to {0, 1, 2, ..., q} and f is one-to-one. If from f we can get a function g, g : E(G)→{1, 2, ..., q} defined by g(e) =│ f (u) − f (v)│for every edge e = {u, v}∈E(G), and g is a bijective function, then we call f is a graceful labeling of G and the graph G is a graceful graph. Let Cn⊙Pm be the graph obtained by attaching a path Pm to each vertex of an n-cycle Cn. Let Cn⊙[(n－1)Pm∪Pu] be the graph obtained by attaching a path Pu to a vertex of an n-cycle Cn and attaching a path Pm to the other vertices. In this thesis, we obtain the following results. (1) Let m be a positive integer. If n≡0, 3(mod 4), then Cn⊙Pm is a graceful graph. (2) Let m be a positive integer. If n≡1, 2(mod 4), then Cn⊙P2m is a graceful graph. (3) Let m and u be a positive integers. If n≡0, 3(mod 4), then Cn⊙[(n－1)Pm∪Pu] is a graceful graph.
47
Kao, Hsi-Chen, and 高惜珍. "On α-labelings of Prism Graphs." Thesis, 2008. http://ndltd.ncl.edu.tw/handle/45600700337438079142.
Full textAbstract:
碩士中原大學
應用數學研究所
96
Let G be a graph with q edges. A function f is called a β-labeling of G if f is a one-to-one from the set of vertices of G to the set {0, 1, 2, . . . , q}, when each edges uv is assigned the label |f(u) − f(v)|, the resulting edges labels are distinct. Let f be a β-labeling of G. If there exists an integer λ so that for each edge uv belong to E(G), either f(u)≦λ
48
Ke, Yan-syu, and 柯彥旭. "The Total L(2,1)-labeling of Graph." Thesis, 2009. http://ndltd.ncl.edu.tw/handle/02329279721274997094.
Full text
49
Hsiao, Cheng-Chih, and 蕭丞志. "on Graph Labeling Problems of Antimagic Type." Thesis, 2006. http://ndltd.ncl.edu.tw/handle/93438938170089870883.
Full textAbstract:
碩士東海大學
數學系
94
Assume G is a simple graph with p vertices and q edges. An edge labeling of a graph G is an assignment of integers to edges, which satisfies certain prescribed conditions. If the vertex sums are pairwise distinct in certain sense where the vertex sum is the sum of the labels of all edges incident with the vertex, we call them antimagic-type labeling. In this thesis, we study two kinds of antimagic-type labeling problems, antimagic labeling and k-edge-graceful labeling. An antimagic labeling is a bijection from the set of all edges to the set of 1,2,... ,q, such that the vertex sums are pairwise distinct. And a k-edge-graceful labeling of a graph G is a bijection from the set of all edges to the set of k,k+1,... ,k+q-1, such that the vertex sums modulo p are pairwise distinct. Our main results in this thesis are composed of two parts. The first part is about results for antimagic labeling of graphs. We study the Cartesian product of graphs, lexicographic product of graphs, and miscellaneous graphs using the methods of induction, graph decompositions, and results in magic square etc. The second part is results for k-edge-graceful labeling. We study recently the k-edge-graceful labeling of square of paths with Sin-Min Lee. While working on this topic, we found that there are close connections among graph labeling, graph decompositions, and integer sequences. This provides with more techniques to study graph labeling problems. This thesis is organized as follows : The first chapter gives the introduction to graph labeling. Main results are in the chapter two, three, and four. The second chapter deals with the antimagic labeling of Cartesian product of graphs, such as P_m ╳ P_n, C_m ╳P_n, and C_m ╳ C_n etc. The third chapter deals with the antimagic labeling of lexicographic product of graphs, join of graphs, corona of graphs. The fourth chapter deals with the edge-graceful spectrum of square of paths, and the last chapter is the conclusion.
50
Cho, Wen-Hsun, and 卓文勛. "Cordial labelings and 3-cordial labelings of union and join of graphs." Thesis, 2006. http://ndltd.ncl.edu.tw/handle/42911847041201420411.
Full textAbstract:
碩士國立東華大學
應用數學系
94
Let G be a graph with vertex set V (G) and edge set E (G), and let A be an abelian group. A vertex labeling f : V(G) →A induces an edge labeling f * : E(G) → A, defined by f *(uv) = f (u) + f (v) for all uv belongs to E (G). For i belongs to A, let v_f^i(G)=|{v belongs to V(G):f(v)=i}|, e_f^i(G)=|{e belongs to E(G):f * (e)=i}|。A labeling of a graph G is said to be A-friendly if |v_f^i(G)−v_f^j(G)|≦1 for all (i,j) belongs to A×A. An A-friendly labeling f of G is said to be an A-cordial labeling of G if |e_f^i(G)−e_f^j(G)|≦1 for all (i,j)belongs to A×A. A graph G is called A-cordial if there exists an A-cordial labeling f of G: When A = Z_n,we use the n-cordial labeling in stead of the Z_n-cordial labeling, and we say that G is n-cordial if G is Zn-cordial. And, for n = 2, we use cordial labeling and cordial in place of 2-cordial labeling and 2-cordial, respectively. In thesis, we study the cordiality and the 3-cordiality of graphs. We give a method to determine that whether the union or join of two graphs are cordial or 3-cordial or not, and use this to find the necessary and sufficient conditions for the cordiality and 3-cordiality of ∪_i=1^k=G_i and G_1+G2+...+G_k where G_i = K_m_i bar or C_m_i for all i,1≦i≦k, And we also prove that C_n is k-cordial for all odd integer k