Minimum degree conditions for large subgraphs

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F09%3A00206508" target="_blank" >RIV/00216208:11320/09:00206508 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Minimum degree conditions for large subgraphs
Original language description
Much of extremal graph theory has concentrated either on finding very small subgraphs of a large graph (such as Turán's theorem [Turán, P., On an extremal problem in graph theory, Matematiko Fizicki Lapok 48 (1941), 436-452]) or on finding spanning subgraphs (such as Dirac's theorem [Dirac, G.A., Some theorems on abstract graphs, Proc. London Math. Soc. s3-2 (1952), 69-81] or more recently work of Komlós, Sárközy and Szemerédi towards a proof of the Pósa-Seymour conjecture). Only a few results give conditions to obtain some intermediate-sized subgraph. We contend that this neglect is unjustified. To support our contention we focus on the illustrative case of minimum degree conditions which guarantee squared-cycles of various lengths, but also offer results, conjectures and comments on other powers of paths and cycles, generalisations thereof, and hypergraph variants.
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Publication year
2009
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)