Almost diameter of a house-hole-free graph in linear time via LexBFS Original Research Article

We show that the vertex visited last by a LexBFS has eccentricity at least diam(G)−2 for house-hole-free graphs, at least diam(G)−1 for house-hole-domino-free graphs, and equal to diam(G) for house-hole-domino-free and AT-free graphs. To prove these results we use special metric properties of house-hole-free graphs with respect to LexBFS.