Title of article
Almost diameter of a house-hole-free graph in linear time via LexBFS Original Research Article
Author/Authors
Feodor F. Dragan، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 1999
Pages
17
From page
223
To page
239
Abstract
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.
Keywords
House-hole-domino free graphs , AT-free graphs , LexBFS , Eccentricity , House-hole-free graphs , Linear-time algorithm , Diameter
Journal title
Discrete Applied Mathematics
Serial Year
1999
Journal title
Discrete Applied Mathematics
Record number
884949
Link To Document