Search

We describe how one department moved from skepticism to wide-spread embrace of coordinated Calculus I. Data played a crucial role in this process. Details of this journey, including successful strategies and missteps, may provide insight and perspective to other departments starting on, or immersed in, similar transformational adventures.

A graph G is H-saturated if H is not a subgraph of G but the addition of any edge from G̅ to G results in a copy of H. The minimum size of an H-saturated graph on n vertices is denoted sat(n,H), while the maximum size is the well studied extremal number, ex(n,H). The saturation spectrum for a graph H is the set of sizes of H saturated graphs between sat(n,H) and ex(n,H). In this paper we completely determine the saturation spectrum of stars and we show the saturation spectrum of paths is continuous from sat(n, Pk) to within a constant of ex(n, Pk) when n is sufficiently large.

We say that a graph G is maximal Kp-free if G does not contain Kp but if we add any new edge e ∈ E(G) to G, then the graph G + e contains Kp. We study the minimum and maximum size of non-(p − 1)-partite maximal Kp-free graphs with n vertices. We also answer the interpolation question: for which values of n and m are there any n-vertex maximal Kp-free graphs of size m?

A vertex dominating path in a graph is a path P such that every vertex outside P has a neighbor on P. In 1988 H. Broersma [5] stated a result implying that every n‐vertex k‐connected graph G such that σ(k+2)(G)≥n−2k−1 contains a vertex dominating path. We provide a short, self‐contained proof of this result and further show that every n‐vertex k‐connected graph such that σ2(G)≥2nk+2+f(k) contains a vertex dominating path of length at most (20k)|T|, where T is a minimum dominating set of vertices. An immediate corollary of this result is that every such graph contains a vertex dominating path with length bounded above by a logarithmic function of the order of the graph. To derive this result, we prove that every n‐vertex k‐connected graph with σ2(G)≥2nk+2+f(k) contains a path of length at most 20k|T|, through any set of T vertices where |T|≤n/900k4. [ABSTRACT FROM AUTHOR]

Let X, Y be connected graphs. A graph G is [ABSTRACT FROM AUTHOR]