Name
Abstract | ||
|---|---|---|
We study the problem of determining sat(n, k, r), the minimum number of edges in a k-partite graph G with n vertices in each part such that G is K-r-free but the addition of an edge joining any two nonadjacent vertices from different parts creates a K-r. Improving recent results of Ferrara, Jacobson, Pfender, and Wenger, and generalizing a recent result of Roberts, we show that sat(n, k, r) = alpha(k, r)n + O(1) as n -> infinity. Moreover, for every 3 <= r <= k we prove that k(2k 4) <= alpha(k, r) <= (k - 1)(4r -l - 6), where l = min{k, 2r - 3}, and show that the lower bound is tight for infinitely many values of r and every k >= 2r 1. This allows us to prove that, for these values, sat(n, k, r) = k(2r - 4)n + O(1) as n -> infinity. Along the way, we disprove a conjecture and answer a question of the first set of authors mentioned above. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1137/18M1166559 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | Field | DocType |
saturation,complete graphs,partite saturation | Graph,Discrete mathematics,Combinatorics,Saturation (chemistry),Mathematics | Journal |
Volume | Issue | ISSN |
33 | 4 | 0895-4801 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| António Girão | 1 | 1 | 3.07 |
| Teeradej Kittipassorn | 2 | 2 | 2.17 |
| Kamil Popielarz | 3 | 1 | 1.79 |