Local conditions for exponentially many subdivisions
Given a graph F, let st (F) be the number of subdivisions of F, each with a different vertex set, which one can guarantee in a graph G in which every edge lies in at least t copies of F. In 1990, Tuza asked for which graphs F and large t, one has that st (F) is exponential in a power of t. We show t...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Published: |
Cambridge University Press
2016
|
| _version_ | 1826292245560557568 |
|---|---|
| author | Liu, H Sharifzadeh, M Staden, K |
| author_facet | Liu, H Sharifzadeh, M Staden, K |
| author_sort | Liu, H |
| collection | OXFORD |
| description | Given a graph F, let st (F) be the number of subdivisions of F, each with a different vertex set, which one can guarantee in a graph G in which every edge lies in at least t copies of F. In 1990, Tuza asked for which graphs F and large t, one has that st (F) is exponential in a power of t. We show that, somewhat surprisingly, the only such F are complete graphs, and for every F which is not complete, st (F) is polynomial in t. Further, for a natural strengthening of the local condition above, we also characterize those F for which st (F) is exponential in a power of t. |
| first_indexed | 2024-03-07T03:11:43Z |
| format | Journal article |
| id | oxford-uuid:b46b8316-91a6-4ad2-8bb7-79702457021c |
| institution | University of Oxford |
| last_indexed | 2024-03-07T03:11:43Z |
| publishDate | 2016 |
| publisher | Cambridge University Press |
| record_format | dspace |
| spelling | oxford-uuid:b46b8316-91a6-4ad2-8bb7-79702457021c2022-03-27T04:26:00ZLocal conditions for exponentially many subdivisionsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:b46b8316-91a6-4ad2-8bb7-79702457021cSymplectic Elements at OxfordCambridge University Press2016Liu, HSharifzadeh, MStaden, KGiven a graph F, let st (F) be the number of subdivisions of F, each with a different vertex set, which one can guarantee in a graph G in which every edge lies in at least t copies of F. In 1990, Tuza asked for which graphs F and large t, one has that st (F) is exponential in a power of t. We show that, somewhat surprisingly, the only such F are complete graphs, and for every F which is not complete, st (F) is polynomial in t. Further, for a natural strengthening of the local condition above, we also characterize those F for which st (F) is exponential in a power of t. |
| spellingShingle | Liu, H Sharifzadeh, M Staden, K Local conditions for exponentially many subdivisions |
| title | Local conditions for exponentially many subdivisions |
| title_full | Local conditions for exponentially many subdivisions |
| title_fullStr | Local conditions for exponentially many subdivisions |
| title_full_unstemmed | Local conditions for exponentially many subdivisions |
| title_short | Local conditions for exponentially many subdivisions |
| title_sort | local conditions for exponentially many subdivisions |
| work_keys_str_mv | AT liuh localconditionsforexponentiallymanysubdivisions AT sharifzadehm localconditionsforexponentiallymanysubdivisions AT stadenk localconditionsforexponentiallymanysubdivisions |