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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom