Open AccessInduced Subgraphs of the Power of a Cycle
Author(s) -
J.-C. Bermond,
Claudine Peyrat
Publication year - 1989
Publication title -
siam journal on discrete mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.843
H-Index - 66
eISSN - 1095-7146
pISSN - 0895-4801
DOI - 10.1137/0402039
Subject(s) - mathematics , combinatorics , degree (music) , discrete mathematics , induced subgraph , graph , vertex (graph theory) , physics , acoustics
In this article, it is shown that if G is an induced subgraph of the dth power of a cycle of length n, and G has minimum degree $d + k$, then G has at least $[ (d + k)/2d ]n$ vertices. This answers a problem of Kezdy.
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