Given a simple and finite connected graph G, the distance d(u,v) is the length of the shortest (u,v)-path in G. Cicerone and Di Stefano [Graphs with bounded induced distance, Discrete Applied Mathematics 108 (2001), pp. 3–21] introduced and studied the class of k-distance-hereditary graphs, i.e., graphs where the distance in each connected induced subgraph is at most k times the distance in the whole graph. In this paper we make a step forward in the study of such graphs by providing characterizations for k-distance-hereditary graphs, k>2, in terms of both forbidden subgraphs and cycle-chord conditions. Such results lead to a polynomial-time recognition algorithm.

Characterizations of Graphs with Stretch Number less than 2

CICERONE, SERAFINO
2011

Abstract

Given a simple and finite connected graph G, the distance d(u,v) is the length of the shortest (u,v)-path in G. Cicerone and Di Stefano [Graphs with bounded induced distance, Discrete Applied Mathematics 108 (2001), pp. 3–21] introduced and studied the class of k-distance-hereditary graphs, i.e., graphs where the distance in each connected induced subgraph is at most k times the distance in the whole graph. In this paper we make a step forward in the study of such graphs by providing characterizations for k-distance-hereditary graphs, k>2, in terms of both forbidden subgraphs and cycle-chord conditions. Such results lead to a polynomial-time recognition algorithm.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11697/19768
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? ND
social impact