Subdivision thresholds for two classes of graphs

Autor:	A. J. Depew, R. C. Entringer, C. A. Barefoot, L. H. Clark, László A. Székely
Rok vydání:	1994
Předmět:	Combinatorics Factor-critical graph Discrete mathematics Graph power Symmetric graph Neighbourhood (graph theory) Wheel graph Discrete Mathematics and Combinatorics Graph homomorphism Complement graph Theoretical Computer Science Forbidden graph characterization Mathematics
Zdroj:	Discrete Mathematics. 125:15-30
ISSN:	0012-365X
DOI:	10.1016/0012-365x(94)90140-6
Popis:	The subdivision threshold for a graph F is the maximum number of edges, ex(n; FS), a graph of order n can have without containing a subdivision of F as a subgraph. We consider two instances: 1. (i) F is the graph formed by a cycle C one vertex of which is adjacent to k vertices not on C, and 2. (ii) F is the graph formed by a cycle C one vertex of which is adjacent to k vertices on C. In the first problem we determine the threshold and characterize the extremal graphs for all k ⩾ 1. In the second problem we do this for k = 2 only.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f6c8d1ebeca5537d630ae344f03f6ab1 https://doi.org/10.1016/0012-365x(94)90140-6 Zobrazit plný text záznamu