×

Graphs with small additive stretch number. (English) Zbl 1062.05053

Which undirected graphs contain a pair of vertices which may be linked by two induced paths (i.e. without other inner links than those of the path) differing by more than \(k\) edges? A complete answer is obtained for \(k=1\) and \(k=2\) in terms of containing some induced subgraph belonging to a structurally described set of graphs. From this a complete set of minimal induced subgraphs may be derived, but is not explicited.

MSC:

05C12 Distance in graphs
05C75 Structural characterization of families of graphs
PDFBibTeX XMLCite
Full Text: DOI Link