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]

A geometric $$k$$-configuration is a collection of points and straight lines in the plane so that $$k$$ points lie on each line and $$k$$ lines pass through this point. We introduce a new construction method for constructing $$k$$-configurations with non-trivial dihedral or chiral (i.e., purely rotational) symmetry, for any $$k \ge 3$$; the configurations produced have $$2^{k-2}$$ symmetry classes of points and lines. The construction method produces the only known infinite class of symmetric geometric 7-configurations, the second known infinite class of symmetric geometric 6-configurations, and the only known 6-configurations with chiral symmetry. [ABSTRACT FROM AUTHOR]

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

The Chvátal-Erdös theorems imply that if G is a graph of order n ≥ 3 with κ(G) ≥ α(G), then G is hamiltonian, and if κ(G) > α(G), then G is hamiltonian-connected. We generalize these results by replacing the connectivity and independence number conditions with a weaker minimum degree and independence number condition in the presence of suffcient connectivity. More speciffcally, it is noted that if G is a graph of order n and k ≥ 2 is a positive integer such that κ(G) ≥ κ, δ(G) > (n + k² - k)/(k + 1), and δ(G) ≥ α(G) + k - 2, then G is hamiltonian. It is shown that if G is a graph of order n and k ≥ 3 is a positive integer such that κ(G) ≥ 4k²+1, δ(G) > (n+k²-k)/k, and δ(G) ≥ α(G) + k - 2, then G is hamiltonian-connected. This result supports the conjecture that if G is a graph of order n and k ≥ 3 is a positive integer such that κ(G) ≥ k, α(G) > (n + k² - 2k)/k, and δ(G)≥ α(G) + k - 2, then G is hamiltonian-connected, and the conjecture is verified for k = 3 and 4. [ABSTRACT FROM AUTHOR]