Hostname: page-component-745bb68f8f-hvd4g Total loading time: 0 Render date: 2025-02-11T23:01:57.575Z Has data issue: false hasContentIssue false
  • English
  • Français

Local Conditions for Exponentially Many Subdivisions

Part of: Graph theory

Published online by Cambridge University Press:  28 November 2016

HONG LIU ,
MARYAM SHARIFZADEH  and
KATHERINE STADEN
HONG LIU
Affiliation:
Mathematics Institute, University of Warwick, Coventry CV4 2AL, UK (e-mail: h.liu.9@warwick.ac.uk, k.l.staden@warwick.ac.uk, m.sharifzadeh@warwick.ac.uk)
MARYAM SHARIFZADEH
Affiliation:
Mathematics Institute, University of Warwick, Coventry CV4 2AL, UK (e-mail: h.liu.9@warwick.ac.uk, k.l.staden@warwick.ac.uk, m.sharifzadeh@warwick.ac.uk)
KATHERINE STADEN
Affiliation:
Mathematics Institute, University of Warwick, Coventry CV4 2AL, UK (e-mail: h.liu.9@warwick.ac.uk, k.l.staden@warwick.ac.uk, m.sharifzadeh@warwick.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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.

MSC classification

Primary: 05C10: Planar graphs; geometric and topological aspects of graph theory
Secondary: 05C35: Extremal problems 05C83: Graph minors
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 3 , May 2017 , pp. 423 - 430
Copyright
Copyright © Cambridge University Press 2016 

References

[1] Bollobás, B. and Thomason, A. (1996) Highly linked graphs. Combinatorica 16 313–320.CrossRefGoogle Scholar
[2] Erdős, P. and Hajnal, A. (1969) On topological complete subgraphs of certain graphs. Ann. Univ. Sci. Budapest 193–199.Google Scholar
[3] Jung, H. A. (1970) Eine Verallgemeinerung des n-fachen Zusammenhangs für Graphen. Math. Ann. 187 95–103.CrossRefGoogle Scholar
[4] Komlós, J. and Szemerédi, E. (1996) Topological cliques in graphs II. Combin. Probab. Comput. 5 79–90.CrossRefGoogle Scholar
[5] Kühn, D. and Osthus, D. (2006) Extremal connectivity for topological cliques in bipartite graphs. J. Combin. Theory Ser. B 96 73–99.CrossRefGoogle Scholar
[6] Mader, W. (1972) Hinreichende Bedingungen für die Existenz von Teilgraphen, die zu einem vollständingen Graphen homomorph sind. Math. Nachr. 53 145–150.CrossRefGoogle Scholar
[7] Tuza, Z. (1990) Exponentially many distinguishable cycles in graphs. J. Combin. Inform. Syst. Sci. 15 281–285.Google Scholar
[8] Tuza, Z. (2001) Unsolved Combinatorial Problems Part I BRICS Lecture Series LS-01-1.Google Scholar
[9] Tuza, Z. (2013) Problems on cycles and colorings. Discrete Math. 313 2007–2013.CrossRefGoogle Scholar