z-logo
open-access-imgOpen Access
Graphs with small additive stretch number
Author(s) -
Dieter Rautenbach
Publication year - 2004
Publication title -
discussiones mathematicae graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.476
H-Index - 19
eISSN - 2083-5892
pISSN - 1234-3099
DOI - 10.7151/dmgt.1232
Subject(s) - mathematics , combinatorics
The additive stretch number sadd(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 sadd(G) ≤ k for some k ∈ N0 = {0, 1, 2, . . .}. Furthermore, we derive characterizations of these classes for k = 1 and k = 2.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom