Large ‐ or ‐Minors in 3‐Connected Graphs
- 4 August 2015
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 82 (2) , 207-217
Abstract
There are numerous results bounding the circumference of certain 3‐connected graphs. There is no good bound on the size of the largest bond (cocircuit) of a 3‐connected graph, however. Oporowski, Oxley, and Thomas (J Combin Theory Ser B 57 (1993), 2, 239–257) proved the following result in 1993. For every positive integer k, there is an integer such that every 3‐connected graph with at least n vertices contains a ‐ or ‐minor. This result implies that the size of the largest bond in a 3‐connected graph grows with the order of the graph. Oporowski et al. obtained a huge function iteratively. In this article, we first improve the above authors' result and provide a significantly smaller and simpler function . We then use the result to obtain a lower bound for the largest bond of a 3‐connected graph by showing that any 3‐connected graph on n vertices has a bond of size at least . In addition, we show the following: Let G be a 3‐connected planar or cubic graph on n vertices. Then for any , G has a ‐minor with , and thus a bond of size at least .Keywords
Funding Information
- National Science Foundation (DMS-1500699)
- National Security Agency (H98230-14-1-0108)
This publication has 11 references indexed in Scilit:
- Capturing two elements in unavoidable minors of 3-connected binary matroidsAdvances in Applied Mathematics, 2013
- The circumference of a graph with no -minor, IIJournal of Combinatorial Theory, Series B, 2012
- Capturing matroid elements in unavoidable 3-connected minorsEuropean Journal of Combinatorics, 2012
- Long Cycles in 3-Connected GraphsJournal of Combinatorial Theory, Series B, 2002
- A sharp bound on the size of a connected matroidTransactions of the American Mathematical Society, 2001
- Unavoidable Minors of Large 3-Connected Binary MatroidsJournal of Combinatorial Theory, Series B, 1996
- Typical Subgraphs of 3- and 4-Connected GraphsJournal of Combinatorial Theory, Series B, 1993
- Longest cycles in 3-connected cubic graphsJournal of Combinatorial Theory, Series B, 1986
- Relative lengths of paths and cycles in 3-connected graphsDiscrete Mathematics, 1981
- A decomposition for combinatorial geometriesTransactions of the American Mathematical Society, 1972