Abstract A linear forest is an acyclic graph of maximum degree at most two. Hence, a linear forest consists of isolated vertices and/or paths. The content of the present dissertation are sufficient conditions (Connectivity and Toughness) forcing the existence of a cycle through a specified linear forest of a graph. We consider the cases, that the specified linear forest consists of all vertices of the graph (Hamiltonian Cycles, especially in sep-chordal planar graphs), of some vertices of the graph, and of some vertices and some edges of the graph, respectively. Moreover we study a generalization of the k-ordered concept (especially in chordal graphs).
Ein linear forest ist ein kreisloser Graph mit einer Maximalvalenz von höchstens zwei. Damit besteht ein linear forest lediglich aus (isolierten) Knotenpunkten und/oder Wegen. Inhalt der vorliegenden Arbeit sind hinreichende Zusammenhangs- und Toughnessvoraussetzungen für die Existenz eines Kreises durch einen vorgeschriebenen linear forest eines Graphen. Es werden die Fälle betrachtet, daß der vorgeschriebene linear forest aus allen Knotenpunkten des Graphen (Hamiltonkreise, speziell in sep-chordalen planaren Graphen), aus einigen Knotenpunkten des Graphen bzw. aus einigen Knotenpunkten und einigen Kanten des Graphen besteht. Darauf aufbauend wird die Fragestellung nach der Existenz eines Kreises durch einige vorgeschriebene Knotenpunkte und einige vorgeschriebene Kanten mit einer zusätzlich vorgeschriebenen Durchlaufungsreihenfolge (speziell in chordalen Graphen) untersucht.