Search

Graphs are simple mathematical structures used to model a wide variety of real-life objects. With the rise of computers, the size of the graphs used for these models has grown enormously. The need to efficiently represent and study properties of extremely large graphs led to the development of the theory of graph limits., Snapshots of modern mathematics from Oberwolfach;2019,10

Graph immersions are a natural counterpart to the widely studied concepts of graph minors and topological graph minors, and yet their theory is much less developed. In the present work we search for sufficient conditions for the existence of the immersions and the properties of the graphs avoiding an immersion of a fixed graph. We prove that large tree-with of 4-edge-connected graph implies the existence of immersion of any 4-regular graph on small number of vertices and that large maximum degree of 3-edge-connected graph implies existence of immersion of any 3-regular graph on small number of vertices.

A vertex cover of a given graph is a vertex set including at least one endpoint from every edge. A vertex cover number τ is the size of a minimum vertex cover. If the vertices from a vertex cover are required to induce a connected subgraph, the resulting set is called a connected vertex cover. The corresponding parameter τc is called a connected vertex cover number. The decision versions of both problems are NP-complete. To better understand a relation between these two vertex cover numbers, Cardinal and Levy define the price of connectivity as a ratio between τc and τ. It is not surprising that determining whether the price of connectivity of a given graph is at most t is NP- hard. The notion of price of connectivity can be extended for more graph properties, such as for the dominating set. The price of connectivity has already been investigated in several papers, with some focusing on critical graphs whose price of connectivity is strictly greater than the price of connectivity of every induced subgraph. This thesis provides an overview of the current state of research into the price of connectivity. Moreover, we focus on the structural properties of critical graphs for the price of connectivity for vertex cover and discuss a possible characterization of graphs in which the price of connectivity for a...

Immersion is a notion of graph inclusion related to the notion of graph minors. While the structural theory of graph minors is extensive, there are still numerous open problems in the structural theory of graph immersions. Kuratowski's theorem claims that the class of graphs that do not contain a subdivision of the graphs K3,3 and K5 is exactly the class of planar graphs. The main goal of this thesis is to describe the structure of the graphs that do not contain an immersion of K3,3. Such graphs can be separated by small edge cuts into small graphs or planar 3-regular graphs. 1