Acyclic 5-Choosability of Planar Graphs Without Adjacent Short Cycles

The conjecture claiming that every planar graph is acyclic 5-choosable[Borodin et al., 2002] has been verified for several restricted classes of planargraphs. Recently, O. V. Borodin and A. O. Ivanova, [Journal of Graph Theory,68(2), October 2011, 169-176], have shown that a planar graph is acyclically 5-choosable if it does not contain an i-cycle adjacent to a j-cycle, where 3<=j<=5 if i=3 and 4<=j<=6 if i=4. We improve the above mentioned result and prove that every planar graph without an i-cycle adjacent to a j-cycle with3<=j<=5 if i=3 and 4<=j<=5 if i=4 is acyclically 5-choosable.

Edge-choosability of Planar Graphs

According to the List Colouring Conjecture, if G is a multigraph then χ' (G)=χl' (G) . In this thesis, we discuss a relaxed version of this conjecture that every simple graph G is edge-(∆ + 1)-choosable as by Vizing’s Theorem ∆(G) ≤χ' (G)≤∆(G) + 1. We prove that if G is a planar graph without 7-cycles with ∆(G)≠5,6 , or without adjacent 4-cycles with ∆(G)≠5, or with no 3-cycles adjacent to 5-cycles, then G is edge-(∆ + 1)-choosable.

Backbone Colouring of Graphs

Consider an undirected graph G and a subgraph of G, H. A q-backbone k-colouring of (G,H) is a mapping f: V(G) {1, 2, ..., k} such that G is properly coloured and for each edge of H, the colours of its endpoints differ by at least q. The minimum number k for which there is a backbone k-colouring of (G,H) is the backbone chromatic number, BBCq(G,H). It has been proved that backbone k-colouring of (G,T) is at most 4 if G is a connected C4-free planar graph or non-bipartite C5-free planar graph or Cj-free, j∈{6,7,8} planar graph without adjacent triangles. In this thesis we improve the results mentioned above and prove that 2-backbone k-colouring of any connected planar graphs without adjacent triangles is at most 4 by using a discharging method. In the second part of this thesis we further improve these results by proving that for any graph G with χ(G) ≥ 4, BBC(G,T) = χ(G). In fact, we prove the stronger result that a backbone tree T in G exists, such that ∀ uv ∈ T, |f(u)-f(v)|=2 or |f(u)-f(v)| ≥ k-2, k = χ(G). For the case that G is a planar graph, according to Four Colour Theorem, χ(G) = 4; so, BBC(G,T) = 4.

Properties and algorithms of the hyper-star graph and its related graphs

The hyper-star interconnection network was proposed in 2002 to overcome the drawbacks of the hypercube and its variations concerning the network cost, which is defined by the product of the degree and the diameter. Some properties of the graph such as connectivity, symmetry properties, embedding properties have been studied by other researchers, routing and broadcasting algorithms have also been designed. This thesis studies the hyper-star graph from both the topological and algorithmic point of view. For the topological properties, we try to establish relationships between hyper-star graphs with other known graphs. We also give a formal equation for the surface area of the graph. Another topological property we are interested in is the Hamiltonicity problem of this graph. For the algorithms, we design an all-port broadcasting algorithm and a single-port neighbourhood broadcasting algorithm for the regular form of the hyper-star graphs. These algorithms are both optimal time-wise. Furthermore, we prove that the folded hyper-star, a variation of the hyper-star, to be maixmally fault-tolerant.

Automatic Inference of Graph Models for Complex Networks with Genetic Programming

Complex networks can arise naturally and spontaneously from all things that act as a part of a larger system. From the patterns of socialization between people to the way biological systems organize themselves, complex networks are ubiquitous, but are currently poorly understood. A number of algorithms, designed by humans, have been proposed to describe the organizational behaviour of real-world networks. Consequently, breakthroughs in genetics, medicine, epidemiology, neuroscience, telecommunications and the social sciences have recently resulted. The algorithms, called graph models, represent significant human effort. Deriving accurate graph models is non-trivial, time-intensive, challenging and may only yield useful results for very specific phenomena. An automated approach can greatly reduce the human effort required and if effective, provide a valuable tool for understanding the large decentralized systems of interrelated things around us. To the best of the author's knowledge this thesis proposes the first method for the automatic inference of graph models for complex networks with varied properties, with and without community structure. Furthermore, to the best of the author's knowledge it is the first application of genetic programming for the automatic inference of graph models. The system and methodology was tested against benchmark data, and was shown to be capable of reproducing close approximations to well-known algorithms designed by humans. Furthermore, when used to infer a model for real biological data the resulting model was more representative than models currently used in the literature.

Planar Topological Defects in Unconventional Superconductors

In this work, we consider the properties of planar topological defects in unconventional superconductors. Specifically, we calculate microscopically the interaction energy of domain walls separating degenerate ground states in a chiral p-wave fermionic superfluid. The interaction is mediated by the quasiparticles experiencing Andreev scattering at the domain walls. As a by-product, we derive a useful general expression for the free energy of an arbitrary nonuniform texture of the order parameter in terms of the quasiparticle scattering matrix. The thesis is structured as follows. We begin with a historical review of the theories of superconductivity (Sec. 1.1), which led the way to the celebrated Bardeen-Cooper- Schrieffer (BCS) theory (Sec. 1.3). Then we proceed to the treatment of superconductors with so-called "unconventional pairing" in Sec. 1.4, and in Sec. 1.5 we introduce the specific case of chiral p-wave superconductivity. After introducing in Sec. 2 the domain wall (DW) model that will be considered throughout the work, we derive the Bogoliubov-de Gennes (BdG) equations in Sec. 3.1, which determine the quasiparticle excitation spectrum for a nonuniform superconductor. In this work, we use the semiclassical (Andreev) approximation, and solve the Andreev equations (which are a particular case of the BdG equations) in Sec. 4 to determine the quasiparticle spectrum for both the single- and two-DW textures. The Andreev equations are derived in Sec. 3.2, and the formal properties of the Andreev scattering coefficients are discussed in the following subsection. In Sec. 5, we use the transfer matrix method to relate the interaction energy of the DWs to the scattering matrix of the Bogoliubov quasiparticles. This facilitates the derivation of an analytical expression for the interaction energy between the two DWs in Sec. 5.3. Finally, to illustrate the general applicability our method, we apply it in Sec. 6 to the interaction between phase solitons in a two-band s-wave superconductor.

Network Similarity Measures and Automatic Construction of Graph Models using Genetic Programming

A complex network is an abstract representation of an intricate system of interrelated elements where the patterns of connection hold significant meaning. One particular complex network is a social network whereby the vertices represent people and edges denote their daily interactions. Understanding social network dynamics can be vital to the mitigation of disease spread as these networks model the interactions, and thus avenues of spread, between individuals. To better understand complex networks, algorithms which generate graphs exhibiting observed properties of real-world networks, known as graph models, are often constructed. While various efforts to aid with the construction of graph models have been proposed using statistical and probabilistic methods, genetic programming (GP) has only recently been considered. However, determining that a graph model of a complex network accurately describes the target network(s) is not a trivial task as the graph models are often stochastic in nature and the notion of similarity is dependent upon the expected behavior of the network. This thesis examines a number of well-known network properties to determine which measures best allowed networks generated by different graph models, and thus the models themselves, to be distinguished. A proposed meta-analysis procedure was used to demonstrate how these network measures interact when used together as classifiers to determine network, and thus model, (dis)similarity. The analytical results form the basis of the fitness evaluation for a GP system used to automatically construct graph models for complex networks. The GP-based automatic inference system was used to reproduce existing, well-known graph models as well as a real-world network. Results indicated that the automatically inferred models exemplified functional similarity when compared to their respective target networks. This approach also showed promise when used to infer a model for a mammalian brain network.

Diastereoselective Synthesis of Planar Chiral N-Substituted Ferrocenes Derived from Epimeric Imidazolones and their Application to Asymmetric Hydrogenation of Quinolines

This thesis describes the synthesis and use of an N-substituted ferrocene bearing a proline-derived chiral directing group and diastereoselective lithiation-electrophile quench of the pro-Sp hydrogen of the ferrocene to give planar chiral products in >95:5 dr. The auxiliary group is found to be stable to lithium bases of types RLi and R2NLi giving the same diastereoselectivity. The anti- epimer of the previously mentioned syn auxiliary induces lithiation of pro Rp rather than pro Sp hydrogen in >95:5 dr. Upon electrophile quench and elimination, the enantiomer of the syn-derived planar chiral imidazolone is obtained. Hence, this method provides a practical way to prepare planar chiral enantiomers in this series without the use of a more expensive D-proline derived starting material. The syn and anti epimers have β, γ-stereogenic centers and the origin of stereoselectivity in lithiation appears to be driven by the conformational bias exerted by the β-silyloxy moiety in each chiral auxiliary. In the thesis, this conclusion is supported using insensitivity of lithiation selectivity to the bulkiness of the base, comparison of enantiomers, deuteration experiments, nOe difference studies and computational modeling of the ground states and lithiation transition states for both substrates. The products are then converted to ligand precursors to make iridium and rhodium complexes. Among them, one of the cationic iridium complex is found to be effective in the asymmetric hydrogenation of 2-substituted quinolines with enantioselectivities up to 80% at pressures as low as 5 atm.

Object-Oriented Genetic Programming for the Automatic Inference of Graph Models for Complex Networks

Complex networks are systems of entities that are interconnected through meaningful relationships. The result of the relations between entities forms a structure that has a statistical complexity that is not formed by random chance. In the study of complex networks, many graph models have been proposed to model the behaviours observed. However, constructing graph models manually is tedious and problematic. Many of the models proposed in the literature have been cited as having inaccuracies with respect to the complex networks they represent. However, recently, an approach that automates the inference of graph models was proposed by Bailey [10] The proposed methodology employs genetic programming (GP) to produce graph models that approximate various properties of an exemplary graph of a targeted complex network. However, there is a great deal already known about complex networks, in general, and often specific knowledge is held about the network being modelled. The knowledge, albeit incomplete, is important in constructing a graph model. However it is difficult to incorporate such knowledge using existing GP techniques. Thus, this thesis proposes a novel GP system which can incorporate incomplete expert knowledge that assists in the evolution of a graph model. Inspired by existing graph models, an abstract graph model was developed to serve as an embryo for inferring graph models of some complex networks. The GP system and abstract model were used to reproduce well-known graph models. The results indicated that the system was able to evolve models that produced networks that had structural similarities to the networks generated by the respective target models.