/library/oar/handle/123456789/47738 2025-11-15T00:52:53Z 2025-11-15T00:52:53Z /library/oar/handle/123456789/50228 2020-04-29T12:50:39Z 2019-01-01T00:00:00Z

Title: Graph theory results of independence, domination, covering and Turán type Abstract: We obtain graph theory results of independence, domination, covering or Turán type, most of which are bounds on graph parameters. We first investigate the smallest number λ(G) of vertices and the smallest number λe(G) of edges that need to be deleted from a non-empty graph G so that the resulting graph has a smaller maximum degree. Generalising the classical Turán problem, we then investigate the smallest number λc(G,k) of edges that need to be deleted from a non-empty graph G so that the resulting graph contains no k-clique. Similarly, we address the recent problem of Caro and Hansberg of eliminating all k-cliques of G by deleting the smallest number ι(G,k) of closed neighbourhoods of vertices of G, establishing in particular a sharp bound on ι(G,k) that solves a problem they posed. Similarly to the problem of determining λ(G), the classical domination problem is to determine the size of a smallest set X of vertices of G such that the degree of each vertex v of the graph obtained by deleting X from G is smaller than the degree of v in G (that is, each vertex in V (G)\X is adjacent to some vertex in X). We add the condition that the vertices in V (G)\X have pairwise different numbers of neighbours in X, and we denote the size of X by γir(G). We also consider the further modification that V (G)\X is an independent set of G, and we denote the size of V (G)\X by αir(G). We obtain several sharp bounds on the graph parameters λ(G), λe(G), λc(G,k), ι(G,k), γir(G), and αir(G) in terms of basic graph parameters such as the order, the size, the minimum degree, and the maximum degree of G. We also characterise the extremal structures for some of the bounds. Description: PH.D.MATHS

2019-01-01T00:00:00Z /library/oar/handle/123456789/47891 2020-04-29T12:47:38Z 2019-01-01T00:00:00Z

Title: The algebraic connectivity of graphs Abstract: Algebraic graph theory is the study of how algebraic techniques can be used when working with graphs. The aim is to translate the properties of graphs into algebraic properties, and then use results and techniques in algebra to deduce and derive theorems about graphs. Of central importance in this topic are matrices that encode the structure of a graph. In particular, in this work we will be making extensive use of the adjacency matrix and the Laplacian matrix. Let G be a simple (with no loops or multiple edges) undirected graph having vertex set V (G) = {v1,v2,...,vn} and edge set E(G). The degree of a vertex v ∈ V (G), denoted by dG (v), is the number of edges of G incident to v. The 0−1 adjacency matrix A(G) = aij of G is the n×n matrix with aij =1 if vi is adjacent to vj and aij =0 otherwise. The n×n diagonal matrix D(G) is the matrix having the entries dG (v1),dG (v2),...,dG (vn) in this order on its leading diagonal and zero elsewhere. The matrix obtained by subtracting A(G) from D(G) is called the Laplacian matrix of G. It is known that L(G) is real and positive semidefinite, and thus its eigenvalues can be ordered as 0= λ1 ≤ λ2 ≤ ... ≤ λn Fiedler(1973)showed that the second smallest eigen value of L(G)is positive if and only if G is connected, and as a result α(G) = λ2 is called the algebraic connectivity of G. The investigation on this parameter is an important topic in algebraic graph theory and it has received much attention since it was introduced by Fiedler. A number of bounds for α(G) have been derived and the problem of determining those graphs that achieve the maximum or the minimum algebraic connectivity among given classes of graphs has been extensively studied. In the same seminal paper, Fiedler considered the relationship between the algebraic connectivity α(G), the vertex connectivity κ(G) of G, and the edge connectivity λ(G), where κ(G) and λ(G) are, respectively, the minimum number of vertices and edges that need to be deleted to disconnect G. This has motivated other researchers to examine in more depth the relationship between the algebraic, the vertex and the edge connectivities. Others investigated the relationship between the algebraic connectivity and various graph invariants, such as the independence number and the matching number, and characterised those graphs that achieve some set bounds. In this dissertation we survey the existing literature on the algebraic connectivity of graphs. We present and analyse the main results on this parameter, give an extensive look at the algebraic connectivity of trees, and investigate therelationshipbetweenalgebraicconnectivity,vertexandedgeconnectivity, independence number and matching number. We then consider a particular family of graphs, namely the Generalised Petersen graphs, and present a conjecture concerning the algebraic connectivity of a particular subfamily of these graphs. Description: M.SC.MATHS

2019-01-01T00:00:00Z /library/oar/handle/123456789/47889 2020-04-29T12:46:55Z 2019-01-01T00:00:00Z

Title: Approximate inverse for linear and non-linear inverse problems Abstract: Many applications in science, engineering, medical imaging and industry arise, where specific results need to be inferred from a given set of observations. Such a task is called an inverse problem, which can be expressed by an operator equation of the form Af = g, where f is the unknown quantity under investigation, g is the measurement data, while A is a bounded operator, illustrating the relation between f and g. An added difficulty when trying to solve such problems is the fact that in most cases, the operator A is ill-posed in the Hadamard sense, meaning that the solution of such problems either does not exist, or is not unique, or else does not depend continuously on the data. As a result, various regularization techniques such as the method of approximate inverse were developed to overcome such issues. The aim of this dissertation is to analyze how the approximate inverse method can be used to reconstruct the unknown quantity f in the case of both linear and non-linear inverse problems. The focus of this dissertation will then shift to an in-depth analysis of a practical realization of the inverse conductivity problem, namely Electrical Impedance Tomography (EIT), in which the unknown complex admittivity has to be reconstructed. It will also be shown how the approximate inverse method can be applied to this same problem in order to reconstruct the unknown admittivity. Description: M.SC.MATHS

2019-01-01T00:00:00Z