Name
Abstract | ||
|---|---|---|
Let x, y is an element of (0, 1], and let A, B, C be disjoint nonempty stable subsets of a graph G, where every vertex in A has at least x vertical bar B vertical bar neighbours in B, and every vertex in B has at least y vertical bar C vertical bar neighbours in C, and there are no edges between A, C. We denote by phi(x, y) the maximum z such that, in all such graphs G, there is a vertex v is an element of C that is joined to at least z vertical bar A vertical bar vertices in A by two-edge paths. This function has some interesting properties: we show, for instance, that phi(x, y) = phi(y, x) for all x, y, and there is a discontinuity in phi(x, x) when 1/x is an integer. For z = 1/2, 2/3, 1/3, 3/4, 2/5, 3/5, we try to find the (complicated) boundary between the set of pairs (x, y) with phi(x, y) >= z and the pairs with phi(x, y) < z. We also consider what happens if in addition every vertex in B has at least x vertical bar A vertical bar neighbours in A, and every vertex in C has at least y vertical bar B vertical bar neighbours in B. We raise several questions and conjectures; for instance, it is open whether phi(x, x) >= 1/2 for all x > 1/3. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.37236/8451 | ELECTRONIC JOURNAL OF COMBINATORICS |
DocType | Volume | Issue |
Journal | 29 | 2 |
ISSN | Citations | PageRank |
1077-8926 | 0 | 0.34 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maria Chudnovsky | 1 | 0 | 1.01 |
| Patrick Hompe | 2 | 0 | 0.34 |
| Alex Scott | 3 | 9 | 2.03 |
| Paul D. Seymour | 4 | 2786 | 314.49 |
| Sophie Spirkl | 5 | 0 | 0.68 |