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.

University of Macau / Faculty of Science and Technology / Department of Computer and Information Science

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.

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

Thesis (M.Sc.)--Memorial University of Newfoundland, 2001. / Includes index. Bibliography: leaf 41.