Graph spectra

The k-spectrum s k ( G) of a graph G is the set of all positive integers that occur as the size of an induced k-vertex subgraph of G. In this paper we determine the minimum order and size of a graph G with s k ( G) = {0, 1, …,( 2 k )} and consider the more general question of describing those sets S...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 1996-04, Vol.150 (1), p.103-113
Main Authors: Faudree, R.J., Gould, R.J., Jacobson, M.S., Lehel, J., Lesniak, L.M.
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The k-spectrum s k ( G) of a graph G is the set of all positive integers that occur as the size of an induced k-vertex subgraph of G. In this paper we determine the minimum order and size of a graph G with s k ( G) = {0, 1, …,( 2 k )} and consider the more general question of describing those sets S ⊆ {0,1, … ,( 2 k )} such that S = s k ( G) for some graph G.
ISSN:0012-365X
1872-681X
DOI:10.1016/0012-365X(95)00179-Z