Loading…
Edge-Dominating Trails in AT-free Graphs
Köhler, Ekkehard; Kriesell, Matthias
Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
A triple of independent vertices of a graph G is called an asteroidal 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ÁČEK closure. In the last section we give a characterization of all AT-free graphs with maximum degree at most 3.
