Cycles in Graphs and Properties of Graphs with Special Cycle Structures

The project considers three graph theoretical research topics, combined to a considerable extent with algorithmic approaches to various related questions and corresponding implementations. The research topics in question are: (a) Hamiltonian Cycles in Special Classes of Graphs, (b) Cycle (Double) Cover Problems, and (c) Independence Number for Special Classes of Graphs. Concerning Hamiltonian Cycles we intend to determine the most general block-cutpoint-structure of a graph G such that G^2 is hamiltonian. We also deal with aspects and certain generalizations of the Barnette Conjecture on the existence of hamiltonian cycles in planar, cubic, bipartite, 3-connected graphs; and we consider the problem of constructing uniquely hamiltonian planar graphs. As for cycle covers, we intend to find new classes of graphs satisfying the Cycle Double Cover Conjecture (CDCC). Sabidussi`s Compatibility Conjecture (SCC) is closely related to the CDCC, and we intend to prove the SCC for certain types of eulerian graphs. Another approach to solving the CDCC is to find two disjoint bipartizing matchings (BMs) w.r.t. a dominating cycle (DC); we are thus planning to test in snarks with stable DC the existence of disjoint BMs. To a minor extent we will also study the Minimum Cost Cycle Cover Problem in non-planar graphs and apply various computational methods there. Finally, we aim to determine the independence ratio in 4-regular graphs decomposable into a hamiltonian cycle H and a 2-factor consisting of cycles conformly inscribed in H. Besides fundamental theoretical research, computer algorithms and techniques of combinatorial optimization and problem solving will play an important role. In several instances the development of algorithms and their implementation will depend on the theoretical results achieved in this project.

Graph theory is a branch of discrete mathematics and plays an important role in different sciences such as operations research, social sciences, theoretical chemistry, and in other areas. Graphs are abstract objects consisting of vertices and edges which can be drawn in the plane as points and lines connecting pairs of points. Traversing graphs, decomposing and covering graphs, independent vertex sets in graphs, just to name a few, are central research themes in graph theory. In the case of hamiltonian cycles and paths every vertex is visited precisely once, and one ends the traversal in the vertex where it started, respectively in a different vertex. The project considered hamiltonian cycles/paths a) in the square G2 which one obtains from a given graph G by adding an edge joining any two non-adjacent vertices x and y if they share a common neighbor. Best possible results regarding hamiltonian cycles/paths in G2 were obtained, provided G is non-separable (i.e., deleting an arbitrary vertex leaves the rest connected). These results serve as a basis for describing the most general possible structure for a graph to guarantee its square to be hamiltonian; b) in polyhedral graphs in which every face contains an even number of vertices, and every vertex belongs to three faces. Barnette's Conjecture claims the existence of hamiltonian cycles in such graphs. Partial solutions of this conjecture were found which are so far the best. Eulerian graphs where every vertex is incident to an even number of edges, admit a cycle decomposition (every edge belongs to precisely one cycle of such decomposition). If one aims for a cycle decomposition which avoids certain forbidden transitions, then one speaks of a compatible cycle decomposition. A quite general theorem was achieved in this context which yields a direct application to the Cycle Double Cover Conjecture (CDCC) according to which every bridgeless graph (every edge is contained in some cycle) admits a family S of cycles such that every edge belongs to precisely 2 elements of S. Other partial solutions of the CDCC were achieved; they operate with certain subgraphs of a given bridgeless graph. A vertex set S in a graph G is called independent if no two vertices in S are joined by an edge. A graph is called smooth if it is 4-regular and can be decomposed into a hamiltonian cycle and non-selfintersecting cycles inscribed in it. It is conjectured that every sufficiently large smooth graph of order n contains an independent set of size >= 2n/7. Various partial solutions of this conjecture were obtained. In addition to theoretical results computer based methods were developed to find concrete graphs with corresponding structures, or to prove their nonexistence up to a certain input size.