Graphs with small additive stretch number

Dieter Rautenbach

Discussiones Mathematicae Graph Theory (2004)

  • Volume: 24, Issue: 2, page 291-301
  • ISSN: 2083-5892

Abstract

top
The additive stretch number s a d d ( G ) of a graph G is the maximum difference of the lengths of a longest induced path and a shortest induced path between two vertices of G that lie in the same component of G.We prove some properties of minimal forbidden configurations for the induced-hereditary classes of graphs G with s a d d ( G ) ≤ k for some k ∈ N₀ = 0,1,2,.... Furthermore, we derive characterizations of these classes for k = 1 and k = 2.

How to cite

top

Dieter Rautenbach. "Graphs with small additive stretch number." Discussiones Mathematicae Graph Theory 24.2 (2004): 291-301. <http://eudml.org/doc/270368>.

@article{DieterRautenbach2004,
abstract = {The additive stretch number $s_\{add\}(G)$ of a graph G is the maximum difference of the lengths of a longest induced path and a shortest induced path between two vertices of G that lie in the same component of G.We prove some properties of minimal forbidden configurations for the induced-hereditary classes of graphs G with $s_\{add\}(G) ≤ k$ for some k ∈ N₀ = 0,1,2,.... Furthermore, we derive characterizations of these classes for k = 1 and k = 2.},
author = {Dieter Rautenbach},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {stretch number; distance hereditary graph; forbidden induced subgraph; forbidden subgraph},
language = {eng},
number = {2},
pages = {291-301},
title = {Graphs with small additive stretch number},
url = {http://eudml.org/doc/270368},
volume = {24},
year = {2004},
}

TY - JOUR
AU - Dieter Rautenbach
TI - Graphs with small additive stretch number
JO - Discussiones Mathematicae Graph Theory
PY - 2004
VL - 24
IS - 2
SP - 291
EP - 301
AB - The additive stretch number $s_{add}(G)$ of a graph G is the maximum difference of the lengths of a longest induced path and a shortest induced path between two vertices of G that lie in the same component of G.We prove some properties of minimal forbidden configurations for the induced-hereditary classes of graphs G with $s_{add}(G) ≤ k$ for some k ∈ N₀ = 0,1,2,.... Furthermore, we derive characterizations of these classes for k = 1 and k = 2.
LA - eng
KW - stretch number; distance hereditary graph; forbidden induced subgraph; forbidden subgraph
UR - http://eudml.org/doc/270368
ER -

References

top
  1. [1] H.J. Bandelt and M. Mulder, Distance-hereditary graphs, J. Combin. Theory (B) 41 (1986) 182-208, doi: 10.1016/0095-8956(86)90043-2. Zbl0605.05024
  2. [2] S. Cicerone and G. Di Stefano, Networks with small stretch number, in: 26th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'00), Lecture Notes in Computer Science 1928 (2000) 95-106, doi: 10.1007/3-540-40064-8₁0. 
  3. [3] S. Cicerone, G. D'Ermiliis and G. Di Stefano, (k,+)-Distance-Hereditary Graphs, in: 27th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'01), Lecture Notes in Computer Science 2204 (2001) 66-77, doi: 10.1007/3-540-45477-2₈. 
  4. [4] S. Cicerone and G. Di Stefano, Graphs with bounded induced distance, Discrete Appl. Math. 108 (2001) 3-21, doi: 10.1016/S0166-218X(00)00227-4. Zbl0965.05040
  5. [5] E. Howorka, Distance hereditary graphs, Quart. J. Math. Oxford 2 (1977) 417-420, doi: 10.1093/qmath/28.4.417. Zbl0376.05040
  6. [6] D. Rautenbach, A proof of a conjecture on graphs with bounded induced distance, manuscript (2002). 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.