Edge-Dominating Trails in AT-free Graphs
| dc.contributor.author | Köhler, Ekkehard | |
| dc.contributor.author | Kriesell, Matthias | |
| dc.date.accessioned | 2021-12-17T10:09:38Z | |
| dc.date.available | 2021-12-17T10:09:38Z | |
| dc.date.issued | 1998 | |
| dc.description.abstract | 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. | en |
| dc.identifier.issn | 2197-8085 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/15716 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-14489 | |
| dc.language.iso | en | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 510 Mathematik | en |
| dc.subject.other | trails | en |
| dc.subject.other | graphs | en |
| dc.subject.other | asteroidal triple | en |
| dc.subject.other | AT-free graphs | en |
| dc.subject.other | traceability | en |
| dc.title | Edge-Dominating Trails in AT-free Graphs | en |
| dc.type | Research Paper | en |
| dc.type.version | submittedVersion | en |
| tub.accessrights.dnb | free | en |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
| tub.series.issuenumber | 1998, 615 | en |
| tub.series.name | Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin | en |