Saturation numbers for families of graph subdivisions |
| |
Authors: | Michael Ferrara Michael Jacobson Kevin G Milans Craig Tennenhouse Paul S Wenger |
| |
Institution: | 1. DEPARTMENT OF MATHEMATICAL AND STATISTICAL SCIENCES, UNIVERSITY OF COLORADO DENVER, , DENVER, CO, 80217;2. DEPARTMENT OF MATHEMATICS, UNIVERSITY OF SOUTH CAROLINA, , COLUMBIA, SC, 29208;3. DEPARTMENT OF MATHEMATICAL SCIENCES, UNIVERSITY OF NEW ENGLAND, , BIDDEFORD, ME, 04005;4. SCHOOL OF MATHEMATICAL SCIENCES, ROCHESTER INSTITUTE OF TECHNOLOGY, , ROCHESTER, NY, 14623 |
| |
Abstract: | For a family of graphs, a graph G is ‐saturated if G contains no member of as a subgraph, but for any edge in , contains some member of as a subgraph. The minimum number of edges in an ‐saturated graph of order n is denoted . A subdivision of a graph H, or an H‐subdivision, is a graph G obtained from H by replacing the edges of H with internally disjoint paths of arbitrary length. We let denote the family of H‐subdivisions, including H itself. In this paper, we study when H is one of or , obtaining several exact results and bounds. In particular, we determine exactly for and show for n sufficiently large that there exists a constant such that . For we show that will suffice, and that this can be improved slightly depending on the value of . We also give an upper bound on for all t and show that . This provides an interesting contrast to a 1937 result of Wagner (Math Ann, 114 (1937), 570–590), who showed that edge‐maximal graphs without a K5‐minor have at least edges. |
| |
Keywords: | saturation graph subdivision |
|
|