direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints 1998

Edge-Dominating Trails in AT-free Graphs
Zitatschlüssel Report-615-1998
Autor Ekkehard Köhler and Matthias Kriesell
Jahr 1998
Nummer 615
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung A triple of independent vertices of a graph $G$ is called an \emphasteroidal triple (AT) if between any two of them there exists a path in $G$ that does not intersect the neighborhood of the third. In this paper we consider different classes of graphs that are related to AT-free graphs. We start by examining AT-free line graphs, give a characterization of them, and apply this for showing that all connected AT-free line graphs are traceable. In the second part we consider line graphs of AT-free graphs. Here we prove that every AT-free graph contains an edge-dominating trail, and that, consequently, every line graph of an AT-free graph is traceable. Moreover, we give an algorithm to find such an edge-dominating trail. In the third part of the paper we consider claw-free AT-free graphs and show a couple of Hamiltonian properties for them, using the Ryjá\vcek closure. In the last section we give a characterization of all AT-free graphs with maximum degree at most 3.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag