Premium
Non‐path spectrum sets
Author(s) -
Chen Guantao,
Faudree Ralph. J.,
Li Xuechao,
Schiermeyer Ingo
Publication year - 2008
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20315
Subject(s) - mathematics , combinatorics , path (computing) , discrete mathematics , graph , cardinality (data modeling) , spectrum (functional analysis) , integral graph , path graph , distance , shortest path problem , graph power , line graph , physics , computer science , quantum mechanics , data mining , programming language
A path of a graph is called maximal if it is not a proper subpath of any other path of the graph. The path spectrum of a graph G , denoted by ps ( G ), is the set of lengths of all maximal paths in the graph. A set S of positive integers is called a path spectrum if there is a connected graph G such that ps ( G ) = S . Jacobson et al. showed that all sets of positive integers with cardinality of 1 or 2 are path spectrum sets. Their results raised the question of whether all sets of positive integers are path spectra. We show that, for every positive integer k ≥ 3, there are infinitely many sets of k positive integers which are not path spectra. A set S of positive integers is called an absolute path spectrum if there are infinitely many connected graphs G such that ps ( G ) = S . We completely characterize absolute path spectra S for | S | ≤ 2. © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 329–350, 2008