This thesis touches three different topics in graph theory, namely, rainbow colouring, product dimension and boxicity. Rainbow colouring An edge colouring of a graph is called a rainbow colouring, if every pair of vertices is connected by atleast one path in which no two edges are coloured the same. The rainbow connection number of a graph is the minimum number of colours required to rainbow colour it. In this thesis we give upper bounds on rainbow connection number based on graph invariants like minimum degree, vertex connectivity, and radius. We also give some computational complexity results for special graph classes. Product dimension The product dimension or Prague dimension of a graph G is the smallest natural number k such that G is an induced subgraph of a direct product of k complete graphs. In this thesis, we give upper bounds on the product dimension for forests, bounded tree width graphs and graphs of bounded degeneracy. Boxicity and cubicity The boxicity (cubicity of a graph G is the smallest natural number k such that G can be represented as an intersection graph of axis-parallel rectangular boxes(axis-parallel unit cubes) in Rk .In this thesis, we study the boxicity and the cubicity of Cartesian, strong and direct products of graphs and give estimates on the boxicity and the cubicity of a product graph based on invariants of the component graphs. Separation dimension The separation dimension of a hypergraph H is the smallest natural number k for which the vertices of H can be embedded in Rk such that any two disjoint edges of H can be separated by a hyper plane normal to one of the axes. While studying the boxicity of line graphs, we noticed that a box representation of the line graph of a hypergraph has a nice geometric interpretation. Hence we introduced this new parameter and did an extensive study of the same.

In view of the fact that a same complex phenomenon can be approached by different conceptual frameworks, it is natural to inquire on the possibility to find connections between different types of quantities, such as topological, dynamical, statistical or thermodynamical, characterizing the same system. The present work is built on the idea that this line of approach can provide interesting insights on possible universal principles governing complex phenomena. In Chapter I we introduce concepts and tools of dynamical systems and thermodynamics as applied in macroscopic scale description as well as, for a later use, a number of selected representative models. In Chapter II we briefly present the elements of the theory of Markov processes describing a large class of stochastic process and also introduce some important concepts on the probabilistic description of deterministic systems. This chapter ends with a thermodynamic formulation accounting for the evolution of the entropy under the effect of stochastic fluctuations. In Chapter III, after introducing the main concepts and recent advances in network theory, we provide a connection between dynamical systems and network theory, which shows how universal structural properties of evolving networks can arise from deterministic dynamics. More specifically, we show explicitly the relation between the connectivity patterns of these networks and the indicators of the underlying dynamics, such as the local Lyapunov exponents. Our analysis is applied to representative models of chaotic maps, chaotic flows and is finally extended to stochastic processes. In Chapter IV we address the inverse problem, namely, processes whose dynamics is determined, in part, by the structure of the network in which they are embedded. In particular, we focus on systems of particles diffusing on a lattice and reacting instantaneously upon encountering each other. We study the role of the topology, the degree of synchronicity of motion and the reaction mechanism on the efficiency of the process. This lead us to identify a common generic mechanism responsible for the behavior of the efficiency, as a function of the control parameters. Finally, in Chapter V we study the connection between the topology and the thermodynamic properties of reaction networks, with focus on the entropy production and the system’s efficiency at nonequilibrium steady states. We also explore the connection between dynamic and thermodynamic properties of nonlinear feedbacks, as well as the response properties of reaction networks against both deterministic and stochastic external perturbations. We address networks of varying topologies, from regular lattices to complex structures./Le présent travail s’inscrit dans le domaine de recherche sur les systèmes complexes. Différentes approches, basées des systèmes dynamiques, de la thermodynamique des systèmes hors d’équilibre, de la physique statistique et, plus récemment, de la théorie des réseaux, sont combinés afin d’explorer des liens entre différentes types de grandeurs qui caractérisent certaines classes de comportements complexes. Dans le Chapitre I nous introduisons les principaux concepts et outils de systèmes dynamiques et de thermodynamique. Dans le Chapitre II nous présentons premièrement des éléments de la théorie de processus de Markov, ainsi que les concepts à la base de la description probabiliste des systèmes déterministes. Nous finissons le chapitre en proposant une formulation thermodynamique qui décrit l’évolution de l’entropie hors d’équilibre, soumis à l’influence de fluctuations stochastiques. Dans le Chapitre III nous introduisons les concepts de base en théorie des réseaux, ainsi qu’un résumé générale des progrès récents dans le domaine. Nous établissons ensuite une connexion entre la théorie des systèmes dynamiques et la théorie de réseaux. Celle-ci permet d’approfondir la compréhension des mécanismes responsables de l’émergence des propriétés structurelles dans des réseaux crées par des lois dynamiques déterministes. En particulier, nous mettons en évidence la relation entre des motifs de connectivité de ce type de réseaux et des indicateurs de la dynamique sous-jacente, tel que des exposant de Lyapounov locaux. Notre analyse est illustrée par des applications et des flots chaotiques et étendue à des processus stochastiques. Dans le Chapitre IV nous étudions le problème complémentaire, à savoir, celui de processus dont la dynamique est déterminée, en partie, par la structure du réseau dans lequel elle se déroule. Plus précisément, nous nous concentrons sur le cas de systèmes de particules réactives, diffusent au travers d’un réseau et réagissant instantanément lorsqu’un rencontre se produit entre elles. Nous étudions le rôle de la topologie, du degré de synchronicité des mouvements et aussi celui du mécanisme de réaction sur l’efficacité du processus. Dans les différents modèles étudiés, nous identifions un mécanisme générique commun, responsable du comportement de l’efficacité comme fonction des paramètres de contrôle. Enfin, dans le Chapitre V nous abordons la connexion entre la topologie et les propriétés thermodynamiques des réseaux de réactions, en analysant le comportement local et global de la production d’entropie et l’efficacité du système dans des état stationnaires de non-équilibre. Nous explorons aussi la connexion entre la dynamique et les propriétés de boucles de rétroaction non linéaires, ainsi que les propriétés de réponse des réseaux de réaction à des perturbations stochastiques et déterministes externes. Nous considérons le cas de réseaux à caractère régulier aussi bien que celui de réseaux complexes.<p><p> / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

This project introduces history and basic notions of the graph theory. It describes graph theory problems, possible graph representations and practical graph management in databases. Aims to subgraph and graph isomorphism. It describes possible ways to find graph isomorphism and chosen algorithms for subgraph and graph isomorphism. The experimental part aims to comparing two implemented algorithms. These are Ullmann and VF2 algorithm. Also searches difference between graphs stored in memory and graphs stored in database.

In this work we use a graph-theoretic representation of secondary RNA structure found in the database RAG: RNA-As-Graphs. We model the bonding of two RNA secondary structures to form a larger structure with a graph operation called merge. The resulting data from each tree merge operation is summarized and represented by a vector. We use these vectors as input values for a neural network and train the network to recognize a tree as RNA-like or not based on the merge data vector. The network correctly assigned a high probability of RNA-likeness to trees identified as RNA-like in the RAG database, and a low probability of RNA-likeness to those classified as not RNA-like in the RAG database. We then used the neural network to predict the RNA-likeness of all the trees of order 9. The use of a graph operation to theoretically describe the bonding of secondary RNA is novel.

Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd W. Easton / Graph Theory is a widely studied topic. A graph is defined by two important features: nodes and edges. Nodes can represent people, cities, variables, resources, products, while the edges represent a relationship between two nodes. Using graphs to solve problems has played a major role in a diverse set of industries for many years. Integer Programs (IPs) are mathematical models used to optimize a problem. Often this involves maximizing the utilization of resources or minimizing waste. IPs are most notably used when resources must be of integer value, or cannot be split. IPs have been utilized by many companies for resource distribution, scheduling, and conflict management. The node packing or independent set problem is a common combinatorial optimization problem. The objective is to select the maximum nodes in a graph such that no two nodes are adjacent. Node packing has been used in a wide variety of problems, which include routing of vehicles and scheduling machines. This thesis introduces several new graph structures, cliqued hole, odd bipartite hole, and odd k-partite hole, and their corresponding valid inequalities for the node packing polyhedron. These valid inequalities are shown to be new valid inequalities and conditions are provided for when they are facet defining, which are known to be the strongest class of valid inequalities. These new valid inequalities can be used by practitioners to help solve node packing instances and integer programs.

This thesis introduces a new model to the field of social dynamics in which each node in a network moves to the mass center of the opinions in its neighborhood weighted by the changing certainty each node has in its own opinion. An upper bound of O(n) is proved for the number of timesteps until this model reaches a stable state. A second model is also analyzed in which nodes move to the mass center of the opinions of the nodes in their neighborhood unweighted by the certainty those nodes have in their opinions. This second model is shown to have a O(d) time complexity, where d is the diameter of the network, on a tree and is compared with a very similar model presented in 2013 by Frischknecht, Keller, and Wattenhofer who found a lower bound on some networks of Ω(3). 2 / Graduate

Thesis (PhD)--Stellenbosch University, 2013. / Please refer to full text to view abstract.

Thesis (MSc)--Stellenbosch University, 2014. / ENGLISH ABSTRACT: We study random walks on nite graphs. The reader is introduced to general Markov chains before we move on more specifically to random walks on graphs. A random walk on a graph is just a Markov chain that is time-reversible. The main parameters we study are the hitting time, commute time and cover time. We nd novel formulas for the cover time of the subdivided star graph and broom graph before looking at the trees with extremal cover times. Lastly we look at a connection between random walks on graphs and electrical networks, where the hitting time between two vertices of a graph is expressed in terms of a weighted sum of e ective resistances. This expression in turn proves useful when we study the cover cost, a parameter related to the cover time. / AFRIKAANSE OPSOMMING: Ons bestudeer toevallige wandelings op eindige gra eke in hierdie tesis. Eers word algemene Markov kettings beskou voordat ons meer spesi ek aanbeweeg na toevallige wandelings op gra eke. 'n Toevallige wandeling is net 'n Markov ketting wat tyd herleibaar is. Die hoof paramaters wat ons bestudeer is die treftyd, pendeltyd en dektyd. Ons vind oorspronklike formules vir die dektyd van die verdeelde stergra ek sowel as die besemgra ek en kyk daarna na die twee bome met uiterste dektye. Laastens kyk ons na 'n verband tussen toevallige wandelings op gra eke en elektriese netwerke, waar die treftyd tussen twee punte op 'n gra ek uitgedruk word in terme van 'n geweegde som van e ektiewe weerstande. Hierdie uitdrukking is op sy beurt weer nuttig wanneer ons die dekkoste bestudeer, waar die dekkoste 'n paramater is wat verwant is aan die dektyd.

The shortest path problem in graphs is both a classic combinatorial optimization problem and a practical problem that admits many applications. Techniques for preprocessing a graph are useful for reducing shortest path query times. This dissertation studies the foundations of a class of algorithms that use preprocessed landmark information and the triangle inequality to guide A* search in graphs. A new heuristic is presented for solving shortest path queries that enables the use of higher order polygon inequalities. We demonstrate this capability by leveraging distance information from two landmarks when visiting a vertex as opposed to the common single landmark paradigm. The new heuristic’s novel feature is that it computes and stores a reduced amount of preprocessed information (in comparison to previous landmark-based algorithms) while enabling more informed search decisions. We demonstrate that domination of this heuristic over its predecessor depends on landmark selection and that, in general, the denser the landmark set, the better heuristic performs. Due to the reduced memory requirement, this new heuristic admits much denser landmark sets. We conduct experiments to characterize the impact that landmark configurations have on this new heuristic, demonstrating that centrality-based landmark selection has the best tradeoff between preprocessing and runtime. Using a developed graph library and static information from benchmark road map datasets, the algorithm is compared experimentally with previous landmark-based shortest path techniques in a fixed-memory environment to demonstrate a reduction in overall computational time and memory requirements. Experimental results are evaluated to detail the significance of landmark selection and density, the tradeoffs of performing preprocessing, and the practical use cases of the algorithm.

In this thesis, we focus on the following topics: supereulerian graphs, hamiltonian line graphs, fault-tolerant Hamiltonian laceability of Cayley graphs generated by transposition trees, and several extremal problems on the (minimum and/or maximum) size of graphs under a given graph property. The thesis includes six chapters. The first one is to introduce definitions and summary the main results of the thesis, and in the last chapter we introduce the furture research of the thesis. The main studies in Chapters 2 - 5 are as follows. In Chapter 2, we explore conditions for a graph to be supereulerian.In Section 1 of Chapter 2, we characterize the graphs with minimum degree at least 2 and matching number at most 3. By using the characterization, we strengthen the result in [93] and we also address a conjecture in the paper.In Section 2 of Chapter 2, we prove that if $d(x)+d(y)\geq n-1-p(n)$ for any edge $xy\in E(G)$, then $G$ is collapsible except for several special graphs, where $p(n)=0$ for $n$ even and $p(n)=1$ for $n$ odd. As a corollary, a characterization for graphs satisfying $d(x)+d(y)\geq n-1-p(n)$ for any edge $xy\in E(G)$ to be supereulerian is obtained. This result extends the result in [21].In Section 3 of Chapter 2, we focus on a conjecture posed by Chen and Lai [Conjecture~8.6 of [33]] that every 3-edge connected and essentially 6-edge connected graph is collapsible. We find a kind of sufficient conditions for a 3-edge connected graph to be collapsible.In Chapter 3, we mainly consider the hamiltonicity of 3-connected line graphs.In the first section of Chapter 3, we give several conditions for a line graph to be hamiltonian, especially we show that every 3-connected, essentially 11-connected line graph is hamilton- connected which strengthens the result in [91].In the second section of Chapter 3, we show that every 3-connected, essentially 10-connected line graph is hamiltonian-connected.In the third section of Chapter 3, we show that 3-connected, essentially 4-connected line graph of a graph with at most 9 vertices of degree 3 is hamiltonian. Moreover, if $G$ has 10 vertices of degree 3 and its line graph is not hamiltonian, then $G$ can be contractible to the Petersen graph.In Chapter 4, we consider edge fault-tolerant hamiltonicity of Cayley graphs generated by transposition trees. We first show that for any $F\subseteq E(Cay(B:S_{n}))$, if $|F|\leq n-3$ and $n\geq4$, then there exists a hamiltonian path in $Cay(B:S_{n})-F$ between every pair of vertices which are in different partite sets. Furthermore, we strengthen the above result in the second section by showing that $Cay(S_n,B)-F$ is bipancyclic if $Cay(S_n,B)$ is not a star graph, $n\geq4$ and $|F|\leq n-3$.In Chapter 5, we consider several extremal problems on the size of graphs.In Section 1 of Chapter 5, we bounds the size of the subgraph induced by $m$ vertices of hypercubes. We show that a subgraph induced by $m$ (denote $m$ by $\sum\limits_{i=0}^ {s}2^{t_i}$, $t_0=[\log_2m]$ and $t_i= [\log_2({m-\sum\limits_{r=0}^{i-1}2 ^{t_r}})]$ for $i\geq1$) vertices of an $n$-cube (hypercube) has at most $\sum\limits_{i=0}^{s}t_i2^{t_i-1} +\sum\limits_{i=0}^{s} i\cdot2^{t_i}$ edges. As its applications, we determine the $m$-extra edge-connectivity of hypercubes for $m\leq2^{[\frac{n}2]}$ and $g$-extra edge-connectivity of the folded hypercube for $g\leq n$.In Section 2 of Chapter 5, we partially study the minimum size of graphs with a given minimum degree and a given edge degree. As an application, we characterize some kinds of minimumrestricted edge connected graphs.In Section 3 of Chapter 5, we consider the minimum size of graphs satisfying Ore-condition.