# A functional approach to the Van der Waals interaction

C. D. Fosco and G. Hansen
Centro Atómico Bariloche and Instituto Balseiro
Comisión Nacional de Energía Atómica
R8402AGP S. C. de Bariloche, Argentina.

###### Abstract

Based on a microscopic model, we use a functional integral approach to
evaluate the quantum interaction energy between two neutral atoms. Each atom
is coupled to the electromagnetic (EM) field via a dipole term, generated by
an electron bound to the nucleus via a harmonic potential. We show that the
resulting expression for the energy becomes the Van der Waals interaction
energy at the first non-trivial order in an expansion in powers of the fine
structure constant, encompassing both the long and short distance behaviours.
We also explore the opposite, strong-coupling limit, which yields a result for
the interaction energy as well as a threshold for the existence of a vacuum
decay probability, manifested here as an imaginary part for the effective
action.

In the weak-coupling limit, we also study the effect of using a general
central potential for the internal structure of the atoms.

##  1 Introduction

A celebrated manifestation of the existence of vacuum fluctuations are the
Casimir, Van der Waals, and related interactions [1, 2, 3]. The second is a
well-known example of an attractive force, between two neutral atoms, which
results from the correlation between their dipole-moment fluctuations. That
correlation, on the other hand, is mediated by the (vacuum) electromagnetic
(EM) field.

In this paper, we use a microscopic model to derive the interaction energy
between two neutral atoms, each one described by a static nucleus, to which an
electron is bound by a harmonic potential. The coupling of each atom to the EM
field is, on the other hand, implemented by a dipole term. In the approach
that we follow, we evaluate the interaction energy by calculating the
Euclidean (imaginary time) effective action resulting from the integration of
the quantum fluctuations of the electrons and the EM field. The vacuum energy
obtained thusly, may be thought of as the result of taking the zero-
temperature limit of the thermal free energy.

This paper is organized as follows: in Section 2 we introduce the model we use
to describe the system, and the tools used to evaluate the interaction energy,
in particular, its imaginary-time effective action. Then, in Sect. 3, we
evaluate the static interaction energy between the two atoms, discussing
different limits. We also derive an expression for the imaginary part of the
energy, and interpret it in terms of a vacuum decay probability. We conclude
the section by studying the case of a general central potential for the atoms,
in the weak-coupling regime.

Finally, in Sect. 4, we present our conclusions.

##  2 The system and its effective action

###  2.1 The model

The model that we consider in this work deals with two atoms, labeled by $1$
and $2$, having their centres of mass at ${\mathbf{r}}^{(1)}$ and
${\mathbf{r}}^{(2)}$, while the electrons are located at the positions
${\mathbf{x}}^{(1)}$ and ${\mathbf{x}}^{(2)}$, relative to
${\mathbf{r}}^{(1)}$ and ${\mathbf{r}}^{(2)}$, respectively. The action
${\mathcal{S}}$, a functional of the gauge field $A$ also, is given by:

$\displaystyle{\mathcal{S}}({\mathbf{x}}^{(1)},{\mathbf{x}}^{(2)},\,A\;;{\mathbf{r}}^{(1)},{\mathbf{r}}^{(2)})$
$\displaystyle=\;{\mathcal{S}}^{a}_{0}({\mathbf{x}}^{(1)})+{\mathcal{S}}^{a}_{0}({\mathbf{x}}^{(2)})\,+\,{\mathcal{S}}^{a}_{I}({\mathbf{x}}^{(1)},\,A\;;{\mathbf{r}}^{(1)})$
$\displaystyle+\,{\mathcal{S}}^{a}_{I}({\mathbf{x}}^{(2)},\,A\;;{\mathbf{r}}^{(2)})\,+\,{\mathcal{S}}^{\rm
EM}_{0}(A)\;,$ (1)

where ${\mathcal{S}}^{a}_{0}({\mathbf{x}})$ is the action for an electron in
the presence of the bounding potential, ${\mathcal{S}}^{\rm EM}_{0}(A)$ the
one for the free EM field, and ${\mathcal{S}}^{a}_{I}$ contains the coupling
of an electron to the EM field. The ${\mathbf{r}}^{(1)}$ and
${\mathbf{r}}^{(2)}$ vectors, which appear in the action, are to be regarded
as external parameters: the ones upon which the effective action will depend.

For the sake of simplicity, the action for each orbiting electron, having mass
$m$ and position $\mathbf{x}(t)$ relative to the nucleus, is taken to be of
the form:

${\mathcal{S}}^{a}_{0}({\mathbf{x}})\;=\;\frac{m}{2}\,\int
dt\,\big{(}\dot{\mathbf{x}}^{2}-\Omega^{2}{\mathbf{x}}^{2}\big{)}\;,$ (2)

since it will allow for the exact evaluation of the interaction energy. Note,
however, that it may be applied to some real physical systems, like heavy
muonic atoms [4, 5].

The interaction with the EM field is assumed to be given by the dipolar term:

$\mathcal{S}_{I}^{a}(A;\mathbf{r},\mathbf{x})=\int
dt\,q\,x_{i}\,E_{i}(\mathbf{r})\;,$ (3)

where $q$ is the charge of the “electron” 111We use this terminology, although
the actual value of $q$ will be assumed to be a variable which measures the
strength of the EM coupling. In the same vein, the binding potential is not
Coulombian but harmonic, and $E_{i}$ denotes the $i^{th}$ component of the
electric field. In our conventions, $E_{i}=F_{0i}$ with
$F_{\mu\nu}=\partial_{\mu}A_{\nu}-\partial_{\nu}A_{\mu}$. Indices from the
middle of the Latin alphabet: $i,\,j,\,k,\ldots$ run from $1$ to $3$, while
Greek ones are assumed to run from $0$ to $3$. Besides, we shall later on use
$\alpha,\beta,\ldots$, taking values $1$ and $2$, corresponding to the two
atoms.

We follow Einstein’s convention: throughout this paper, a sum over repeated
indices is assumed unless explicitly stated otherwise.

Here, $A_{\mu}$ denotes the 4-potential, which has the action:

$\mathcal{S}_{0}^{\text{EM}}(A)=\int
d^{4}x\,\left[-\frac{1}{4}F_{\mu\nu}F^{\mu\nu}-\frac{\lambda}{2}\,(\partial_{\mu}A^{\mu})^{2}\right]\;\;,$
(4)

consisting of the standard (vacuum) Maxwell term, plus a covariant gauge-
fixing term ($\lambda\neq 0$). We use natural units ($c=1$, $\hbar=1$) and the
metric signature $(+,-,-,-)$.

###  2.2 Effective action

A rather convenient way to obtain the quantum interaction energy for a system
composed of two or more objects is by means of its imaginary-time effective
action, $\Gamma_{\text{eff}}$. Indeed, by considering a static configuration,
one can extract the vacuum energy by taking the limit:

$E_{I}\;=\;\lim_{T\to\infty}\left(\frac{\Gamma_{\text{eff}}}{T}\right)\;,$ (5)

where $T$ denotes the extent of the (imaginary) time interval [6].
$\Gamma_{\text{eff}}$ results from the integration of the quantum
fluctuations, yielding as a result a function of the remaining, classical
degrees of freedom. Since we are interested in the interaction part of the
energy, we shall subtract the self-energy contributions, which are the ones
that survive when the objects are infinitely far apart.

We will use for $\Gamma_{\text{eff}}$ a convenient representation in terms of
a functional integral:

$\displaystyle
e^{-\Gamma_{\text{eff}}(\mathbf{r}^{(1)},\mathbf{r}^{(2)})}\,\equiv\,\frac{1}{\mathcal{N}}\;{\mathcal{Z}}(\mathbf{r}^{(1)},\mathbf{r}^{(2)})$
$\displaystyle{\mathcal{Z}}(\mathbf{r}^{(1)},\mathbf{r}^{(2)})=\,\int\mathcal{D}\mathbf{x}^{(1)}\,\mathcal{D}\mathbf{x}^{(2)}\,\mathcal{D}A\,\,e^{-\mathcal{S}_{E}(\mathbf{x}^{(1)},\,\mathbf{x}^{(2)},\,A\,;\,\mathbf{r}^{(1)},\,\mathbf{r}^{(2)})}\;,$
(6)

where ${\mathcal{N}}$ is a constant, and $\mathcal{S}_{E}$ is the Euclidean
(Wick rotated) version of the action:

$\displaystyle\mathcal{S}_{E}\,=\,\frac{m}{2}\,\int
d\tau\,\Big{[}(\dot{\mathbf{x}}^{(1)})^{2}+(\dot{\mathbf{x}}^{(2)})^{2}$
$\displaystyle+\,\Omega^{2}\big{(}({\mathbf{x}}^{(1)})^{2}+({\mathbf{x}}^{(2)})^{2}\big{)}\Big{]}$
$\displaystyle\,+\,q\,\int
d\tau\,\big{(}{\mathbf{x}}^{(1)}\cdot\,{\mathbf{E}}(\tau,\mathbf{r}^{(1)})\,+\,{\mathbf{x}}^{(2)}\cdot\,{\mathbf{E}}(\tau,\mathbf{r}^{(2)})\big{)}\,$
$\displaystyle+\,\int d^{4}x\,\frac{1}{2}A_{\mu}(-\partial^{2})A_{\mu}\;.$ (7)

Here, $\tau\equiv x_{0}$ is the imaginary time, the metric becomes
$(g_{\mu\nu})={\rm diag}(1,1,1,1)$,
${\mathbf{E}}\equiv\partial_{\tau}{\mathbf{A}}-\nabla A_{0}$, and we have
adopted the Feynman ($\lambda=1$) gauge. The normalization constant
${\mathcal{N}}$, is chosen in such a way that the energy vanishes when the
distance between atoms tends to infinity:

${\mathcal{N}}\,=\,\left[{\mathcal{Z}}(\mathbf{r}^{(1)},\mathbf{r}^{(2)})\right]\big{|}_{|\mathbf{r}^{(1)}-\mathbf{r}^{(2)}|\to\infty}\;.$
(8)

Note that this implies that any factor independent of $\mathbf{r}^{(1)}$ or
$\mathbf{r}^{(2)}$ in ${\mathcal{Z}}$, may be discarded.

As a first step towards obtaining $\Gamma_{\text{eff}}$, we introduce an
intermediate object, ${\mathcal{S}}_{\text{eff}}$: the result of performing
the functional integral just over $A_{\mu}$:

$\displaystyle
e^{-{\mathcal{S}}_{\text{eff}}(\mathbf{x}^{(1)},\,\mathbf{x}^{(2)}\,;\,\mathbf{r}^{(1)},\,\mathbf{r}^{(2)})}$
$\displaystyle=\,e^{-\frac{m}{2}\int_{\tau}\,\big{[}(\dot{\mathbf{x}}^{(1)})^{2}+(\dot{\mathbf{x}}^{(2)})^{2}\,+\,\Omega^{2}\big{(}({\mathbf{x}}^{(1)})^{2}+({\mathbf{x}}^{(2)})^{2}\big{)}\big{]}}$
$\displaystyle\times\,e^{-\frac{1}{2}\int_{x,y}J_{\mu}(x)\Delta_{\mu\nu}(x-y)J_{\nu}(y)}\;,$
(9)

where we used a shorthand notation for the integrations, and
$J_{\mu}=J_{\mu}^{(1)}+J_{\mu}^{(2)}$, $J_{\mu}^{(\alpha)}$ ($\alpha=1,\,2$)
being a dipole current concentrated on each atom, given explicitly by:

$\displaystyle J_{0}^{(\alpha)}(y)$
$\displaystyle=\,-q\,x^{(\alpha)}_{j}(\tau)\,\delta(y_{0}-\tau)\,\frac{\partial}{\partial
y_{j}}\,\delta^{3}({\mathbf{y}}-{\mathbf{r}}^{(\alpha)})$
$\displaystyle{\mathbf{J}}^{(\alpha)}(y)$
$\displaystyle=\,q\,\dot{\mathbf{x}}^{(\alpha)}(\tau)\,\delta(y_{0}-\tau)\,\delta^{3}({\mathbf{y}}-{\mathbf{r}}^{(\alpha)})\;\;,$
(10)

and

$\Delta_{\mu\nu}(x-y)=\delta_{\mu\nu}\,\Delta(x-y)\,$ (11)

where $\Delta(x-y)$ is the scalar propagator:

$\Delta(x-y)=\int\frac{d^{4}k}{(2\pi)^{4}}\,\frac{e^{-ik(x-y)}}{k^{2}}\;.$
(12)

Note that each current is conserved ($\partial_{\mu}J_{\mu}^{(\alpha)}=0$), so
the result (2.2) is independent of the value of the constant $\lambda$. Taking
into account the form of the gauge field propagator one sees that, due to the
coupling to the EM field, $\Omega$ in the harmonic term of each atom’s action
gets renormalized. Keeping the same notation, $\Omega$, now for the
renormalized frequency, we see that

${\mathcal{S}}_{\rm
eff}({\mathbf{x}}^{(1)},{\mathbf{x}}^{(2)},A\,;{\mathbf{r}}^{(1)},{\mathbf{r}}^{(2)})\;=\;\frac{1}{2}\,\int_{-\infty}^{+\infty}\frac{d\nu}{2\pi}\,[\tilde{x}^{(\alpha)}_{i}(\nu)]^{*}\,K_{ij}^{(\alpha\beta)}(\nu)\,\tilde{x}^{(\beta)}_{j}(\nu)\;,$
(13)

where we have introduced:

$\tilde{x}^{(\alpha)}_{j}(\nu)\equiv\int_{-\infty}^{+\infty}dt\,e^{i\nu
t}\,x^{(\alpha)}_{j}(t)\;\;,$ (14)

and ∗ denotes complex conjugation.

On the other hand,

$K_{ij}^{(ab)}(\nu)\;\equiv\;m(\nu^{2}\,+\,\Omega^{2})\delta^{(ab)}\delta_{ij}\;+\;\sigma^{(ab)}\,M_{ij}(\nu)$
(15)

where
$\sigma^{(ab)}\,\equiv\,\delta^{(a1)}\delta^{(b2)}+\delta^{(a2)}\delta^{(b1)}$,
while the matrix elements $M_{ij}(\nu)$ are given by:

$M_{ij}(\nu)\equiv
q^{2}\int\frac{d^{3}\mathbf{k}}{(2\pi)^{3}}\,e^{i\mathbf{k}\cdot\mathbf{r}}\,\frac{\nu^{2}\delta_{ij}+k_{i}k_{j}}{\nu^{2}+\mathbf{k}^{2}}\;\;,\;\;\;\;\mathbf{r}\equiv\mathbf{r}^{(1)}-\mathbf{r}^{(2)}\;.$
(16)

With the appropriate choice of the system of coordinates
($\hat{e}_{k_{3}}\,||\,\mathbf{r}$), we cast this Hermitian matrix in diagonal
form: ${\rm diag}(M_{1}(\nu),M_{2}(\nu),M_{3}(\nu))$, with:

$\displaystyle M_{1}(\nu)$ $\displaystyle=M_{2}(\nu)=-\frac{q^{2}}{4\pi
r^{3}}\,(1+r|\nu|+r^{2}|\nu|^{2})\,e^{-r|\nu|},$ $\displaystyle M_{3}(\nu)$
$\displaystyle=-\frac{q^{2}}{2\pi r^{3}}\,(1+r|\nu|)\,e^{-r|\nu|}\;,$ (17)

where, as expected, the dependence on the relative positions of the atoms is
only through their distance: $r\equiv|{\mathbf{r}}|$.

Finally, we integrate out the electrons’ coordinates relative to each atom.
This is still a Gaussian functional integral which, by converting to Fourier
space also the integration measure, becomes an infinite product of decoupled
ordinary integrals. This means that the integral

$e^{-\Gamma_{\text{eff}}(r)}\,=\,\frac{1}{\mathcal{N}}\int\mathcal{D}\mathbf{x}^{(1)}\,\mathcal{D}\mathbf{x}^{(2)}\,e^{-{\mathcal{S}}_{\text{eff}}({\mathbf{x}}^{(1)},{\mathbf{x}}^{(2)},A\,;r)}\;,$
(18)

yields an expression for $\Gamma_{\text{eff}}$ which is proportional to the
total evolution time, $T$, as it should be for a static configuration. The
interaction energy, however, is given by the ratio
$\frac{\Gamma_{\text{eff}}}{T}$ in the $T\to\infty$ limit, which is well-
defined:

$E_{I}(r)\;=\;\Big{[}\frac{{\Gamma}_{\text{eff}}({\mathbf{r}})}{T}\Big{]}_{T\to\infty}\,=\,\frac{1}{2}\,\int_{-\infty}^{\infty}\frac{d\nu}{2\pi}\,\log\det(\mathds{1}-\mathds{T}(\nu)),$
(19)

where $\mathds{T}(\nu)$ is the $3\times 3$ matrix:

$\mathds{T}(\nu)\,=\,e^{-2|\nu|r}\,\begin{bmatrix}[\xi_{\shortparallel}(\nu,r)]^{2}&0&0\\\
0&[\xi_{\shortparallel}(\nu,r)]^{2}&0\\\
0&0&[\xi_{\perp}(\nu,r)]^{2}\end{bmatrix}\;,$ (20)

where

$\xi_{\shortparallel}(\nu,r)\,=\,\frac{q^{2}(1+r|\nu|+r^{2}|\nu|^{2})}{4\pi
r^{3}m(\nu^{2}+\Omega^{2})}\;\;,\;\;\;\xi_{\perp}(\nu,r)\,=\,\frac{q^{2}(1+r|\nu|)}{2\pi
r^{3}m(\nu^{2}+\Omega^{2})}\;.$ (21)

##  3 Interaction energy

Computing the determinant, we have the resulting expression for the
interaction energy

$E_{I}(r)=\frac{1}{2}\int_{-\infty}^{\infty}\frac{d\nu}{2\pi}\,\big{[}2\log\left(1-\xi_{\shortparallel}^{2}e^{-2|\nu|r}\right)+\,\log\left(1-\xi_{\perp}^{2}e^{-2|\nu|r}\right)\big{]}\;$
(22)

which is a realization, in a particular context, of the $TGTG$ formula [7].

By a redefinition of the integration variable: $\nu=\frac{u}{r}$, we see that:

$\displaystyle
E_{I}(r)=\frac{1}{2r}\int_{-\infty}^{\infty}\frac{du}{2\pi}\,\Big{\\{}2$
$\displaystyle\log\big{[}1-\big{(}\frac{q^{2}}{4\pi
m\,r}\frac{1+|u|+u^{2}}{u^{2}+(\Omega r)^{2}}\big{)}^{2}e^{-2|u|}\big{]}$
$\displaystyle+\,$ $\displaystyle\log\big{[}1-\big{(}\frac{q^{2}}{2\pi
m\,r}\frac{1+|u|}{u^{2}+(\Omega
r)^{2}}\big{)}^{2}e^{-2|u|}\big{]}\Big{\\}}\;.$ (23)

Introducing the dimensionless variable $x\equiv\Omega r$, which measures the
distance between atoms in terms of a length scale $\sim\Omega^{-1}$, and using
$\Omega$ to measure energies: $E_{I}(r)\equiv\Omega{\mathcal{E}}_{I}(\Omega
r)$, where:

$\displaystyle{\mathcal{E}}_{I}(x)=\frac{1}{x}\int_{0}^{\infty}\frac{du}{2\pi}\,\Big{\\{}2$
$\displaystyle\log\big{[}1-\big{(}\frac{q^{2}}{4\pi}\frac{\Omega}{m}\big{)}^{2}\,\frac{(1+u+u^{2})^{2}}{x^{2}(u^{2}+x^{2})^{2}}\,e^{-2u}\big{]}$
$\displaystyle+\,$
$\displaystyle\log\big{[}1-\big{(}\frac{q^{2}}{2\pi}\frac{\Omega}{m}\big{)}^{2}\,\frac{(1+u)^{2}}{x^{2}(u^{2}+x^{2})^{2}}\,e^{-2u}\big{]}\Big{\\}}\;,$
(24)

a result that we shall analyze below under different assumptions regarding the
parameters of the system.

###  3.1 Weak coupling and Van der Waals interaction

This corresponds to situations where, keeping a few terms in the power series
expansion: ${\rm log}(1-x)=-\sum_{n=1}\frac{x^{n}}{n+1}$ for each one of the
logs above, is a reliable approximation.

Moreover, we also assume here that that is achieved by means of the two
(independent) conditions: $\frac{q^{2}}{2\pi}\ll m/\Omega$, and $r\gg
1/\Omega$. The first one is essentially a constraint on the maximum value of
the coupling constant or, equivalently, on the size of the electric dipole
fluctuations on each atom.

Under those two assumptions, the leading term in the expansion is:

$\displaystyle{\mathcal{E}}_{I}(x)$ $\displaystyle\sim{\mathcal{E}}_{w}(x)$
$\displaystyle{\mathcal{E}}_{w}(x)$
$\displaystyle\equiv\,-\frac{1}{16\pi^{3}}\big{(}\frac{q^{2}\Omega}{m}\big{)}^{2}\,\frac{1}{x^{3}}\,\int_{0}^{\infty}du\,e^{-2u}\,\frac{u^{4}+2u^{3}+5u^{2}+6u+3}{(u^{2}+x^{2})^{2}}\;.$
(25)

The integral from (3.1) can be computed exactly, for that we introduce the two
auxiliary functions:

$\displaystyle f(x)$
$\displaystyle\equiv\text{Ci}(x)\sin(x)-\text{si}(x)\cos(x),$ (26)
$\displaystyle g(x)$
$\displaystyle\equiv-(\text{Ci}(x)\cos(x)+\text{si}(x)\sin(x)),$ (27)

where $\text{si}(x)\equiv\text{Si}(x)-\frac{\pi}{2}$, being $\text{Ci}(x)$ and
$\text{Si}(x)$ the cosine and sine integrals, respectively [8]. In terms of
those functions, we have:

$\displaystyle\mathcal{E}_{w}(x)=-\frac{1}{32\pi^{3}}\left(\frac{q^{2}\Omega}{m}\right)^{2}\frac{1}{x^{6}}\,$
$\displaystyle\big{(}x\,(6-x^{2})+(3-7x^{2}+x^{4})\,f(2x)$
$\displaystyle+2x\,(3-3x^{2}+x^{4})\,g(2x)\big{)}.$ (28)

We plot $\mathcal{E}_{w}(x)$ in Fig. 1. For $x\gg 1$, result (3.1) reproduces
the asymptotic behaviour of Van der Waals forces at long distances:

$E_{I}(r)\sim-\frac{23}{(4\pi)^{3}}\,\big{(}\frac{q^{2}}{m\Omega^{2}}\big{)}^{2}\,\frac{1}{r^{7}}\;,$
(29)

in agreement with [9] (see also [10]). From (29), we identify the static
electric susceptibility of the microscopic model:
$\alpha_{E}=\frac{q^{2}}{m\Omega^{2}}$, which has volume dimensions.

Figure 1: Weak coupling interaction energy ($\mathcal{E}_{w}$) as function of
$x=\Omega r$. $A$ is the global factor
$A=\big{(}\frac{q^{2}\Omega}{m}\big{)}^{2}$.

In terms of the original variables, and written in a way that makes the
comparison with the next-to-leading term more straightforward,

$E_{I}(r)\sim-\frac{23}{4\pi}\,\big{(}\frac{q^{2}}{4\pi
m\Omega}\big{)}^{2}\,\frac{1}{\Omega r}\;\frac{1}{\Omega r^{6}}\;.$ (30)

The next-to-leading term at long distances corresponds to the London limit
[11, 1]. This can be picked up by extracting the next negative power of the
distance or, equivalently, by evaluating the frequency integral in (22) using
the approximation $|\nu|r\simeq 0$. In this situation,

$\displaystyle E_{I}(r)$
$\displaystyle\simeq\,-\frac{1}{2}\,\int_{-\infty}^{+\infty}\frac{d\nu}{2\pi}\,\frac{1}{(\nu^{2}+\Omega^{2})^{2}}\,\Big{[}2\,\big{(}\frac{q^{2}}{4\pi
r^{3}m}\big{)}^{2}+\big{(}\frac{q^{2}}{2\pi r^{3}m}\big{)}^{2}\Big{]}$
$\displaystyle=\;-\frac{3}{4}\,\big{(}\frac{q^{2}}{4\pi
m\Omega}\big{)}^{2}\,\frac{1}{\Omega\,r^{6}}$ (31)

The ratio between this term and the asymptotic one at long distances is
${\mathcal{O}}(\Omega r)$, as it should be.

###  3.2 Strong coupling: short distances and imaginary part of the energy

One should expect the interaction energy to be real. Note, however, that due
to the presence of the logarithms, the interaction will have both real and
imaginary parts. The existence of imaginary parts for the logarithms may be
seen to depend on the value of the dimensionless ratio:

$g\;\equiv\;\frac{q^{2}}{2\pi}\frac{1}{m\Omega^{2}r^{3}}\;.$ (32)

The existence of an instability at short distances, and therefore of an
imaginary part in the effective action, may be understood by an argument based
on the form of the intermediate effective action ${\mathcal{S}}_{\text{eff}}$,
and its short distance behaviour: the London limit. We recall that it is a
quadratic form in the electrons’ coordinates, with a frequency-dependent
kernel $K_{ij}^{(ab)}(\nu)$. At sufficiently small distances $r$, we may use
the instantaneous approximation for the gauge field propagator, namely, assume
that $r\ll\lambda$, and therefore use $r\nu\simeq 0$ (see [1] & references
there in).

This is in fact equivalent to replacing the gauge-field propagator by its
Coulomb form. Therefore,

$K_{ij}^{(ab)}(\nu)\;\simeq\;m(\nu^{2}\,+\,\Omega^{2})\delta^{(ab)}\delta_{ij}\;+\;\sigma^{(ab)}\,M_{ij}(0)$
(33)

where $M_{ij}(0)$ is diagonal if the orthogonal coordinate system is chosen so
that $x_{3}$ points along the direction of the line connecting the two atoms.
With this choice,

$\big{[}M_{ij}(0)\big{]}\,\equiv\,-\frac{q^{2}}{4\pi
r^{3}}\,\left(\begin{array}[]{ccc}1&0&0\\\ 0&1&0\\\
0&0&2\end{array}\right)\;.$ (34)

In this limit, transforming back the electrons fluctuations from frequency to
time, ${\mathcal{S}}_{\text{eff}}$ becomes local in time, and may thus be
interpreted as an action.

That action involves the original six harmonic modes (one for each
$x^{(\alpha)}_{i}$) with identical oscillation frequency $\Omega$, plus an
$r$-dependent term which couples them. Altogether, they produce a potential
which we denote by $V_{\text{eff}}$, and is still quadratic:

$\displaystyle\mathcal{S}_{\text{eff}}$ $\displaystyle\simeq\,\int
d\tau\,\big{[}\frac{m}{2}\dot{x}^{(\alpha)}_{i}\dot{x}^{(\alpha)}_{i}\,+\,V_{\text{eff}}(\\{x^{(\alpha)}_{i}\\})\big{]}$
$\displaystyle V_{\text{eff}}(\\{x^{(\alpha)}_{i}\\})$
$\displaystyle=\,\frac{m}{2}\Omega^{2}x^{(\alpha)}_{i}x^{(\alpha)}_{i}-\frac{q^{2}}{4\pi
r^{3}}\big{(}x^{(1)}_{1}x^{(2)}_{1}+x^{(1)}_{2}x^{(2)}_{2}+2x^{(1)}_{3}x^{(2)}_{3}\big{)}\;.$
(35)

The diagonalization of this potential is straightforward; the normal
coordinates

$\displaystyle x_{i}^{(\pm)}\;\equiv\;\frac{x^{(1)}_{i}\pm
x^{(2)}_{i}}{\sqrt{2}}\;\;,\;\;\;i=1,\,2,\,3\;,$ (36)

lead to the potential:

$\displaystyle V_{\text{eff}}(\\{x^{(\pm)}_{i}\\})$
$\displaystyle=\,\frac{m}{2}\sum_{i=1}^{3}\,\big{(}(\Omega^{+}_{i})^{2}\,x^{(+)}_{i}x^{(+)}_{i}+(\Omega^{-}_{i})^{2}\,x^{(-)}_{i}x^{(-)}_{i}\big{)}$
$\displaystyle(\Omega^{\pm}_{1})^{2}$
$\displaystyle=\;(\Omega^{\pm}_{2})^{2}\,=\,\Omega^{2}\,\mp\,\frac{q^{2}}{4\pi
mr^{3}}\;\;,\;\;\;(\Omega^{\pm}_{3})^{2}\,=\,\Omega^{2}\,\mp\,\frac{q^{2}}{2\pi
mr^{3}}\;.$ (37)

By diagonalizing the action (3.2), the system becomes a set of three uncoupled
harmonic oscillators, which partition function factorices as the product of
the partition functions of each individual oscillator, with frequencies
$\sqrt{(\Omega_{i}^{\pm})^{2}}$, $i=1,2,3$ [6, 12]. The energy of the system
is:

$E_{0}=\frac{1}{2}\,\sum_{i=1}^{3}\big{(}\sqrt{{(\Omega_{i}^{+})}^{2}}+\sqrt{{(\Omega_{i}^{-})}^{2}}\,\big{)}.$
(38)

From the expressions of (3.2), we see that there will appear complex
frequencies, depending on the value of $r$. Defining the two distances:

$r_{1}\,\equiv\,\big{(}\frac{q^{2}}{2\pi
m\Omega^{2}}\big{)}^{1/3}\;\;,\;\;\;r_{2}\,\equiv\,\big{(}\frac{q^{2}}{4\pi
m\Omega^{2}}\big{)}^{1/3}\;\;,$ (39)

we note that there is a first threshold at $r=r_{1}$ for the existence of an
complex frequency, and then another one at $r=r_{2}<r_{1}$. Note that this
explains the behaviour observed in the plot of the imaginary part of the
energy as a function of $r$. Indeed, besides the clear existence of the first
threshold at $r=r_{1}$, we also see the emergence of the second one at
$r=r_{2}$. Note also that the existence of two modes for the latter is
reflected in the steepest rise for $r<r_{2}$. The real and imaginary parts of
the interaction energy are shown in Fig. 2.

Figure 2: Real and imaginary parts of the interaction energy
($\mathcal{E}_{I}$), as a function of $x=\Omega r$, with
$\frac{q^{2}}{2\pi}\,\frac{\Omega}{m}=0.5$. $x_{1}=\Omega r_{1}$ and
$x_{2}=\Omega r_{2}$ are the first and second thresholds for which
$\mathcal{E}_{I}$ develops an imaginary part.

The physical interpretation of the imaginary part of the energy is that of a
non-vanishing probability of vacuum decay, understanding as vacuum the one
used in the calculation of the effective action. Regarding the atoms, that
vacuum is the tensor product of the two respective ground states. On the other
hand, when the two atoms are sufficiently close to each other, it is clear the
true vacuum should be closer to the one of two electrons in a molecule. That
is not a tensor product of the two: rather, it should be closer to a linear
combination of two atomic orbitals. That is indeed what may be seen from the
form of the normal coordinates obtained in (36): the modes that destabilize
the vacuum correspond to
${\mathbf{x}}^{(+)}=\frac{x^{(1)}+x^{(2)}}{\sqrt{2}}$.

###  3.3 General central potential

Let us consider here the case of a more general central potential $V$, in such
a way that the action for each atom, rather than having the specific form (2)
is now assumed to fall under the more general form:

${\mathcal{S}}^{a}_{0}({\mathbf{x}})\;=\;\,\int
dt\,\big{[}\frac{m}{2}\,\dot{\mathbf{x}}^{2}-V(|{\mathbf{x}}|)\big{]}\;.$ (40)

The most immediate way to compute the effect of using this potential rather
than the original, harmonic one, is to evaluate the Euclidean the effective
action for the redefined action in the weak-coupling regime. The lowest non-
trivial contribution to $\Gamma_{\text{eff}}(r)$ is again of order $q^{4}$,

$\Gamma_{\text{eff}}(r)\;\simeq\;\Gamma^{(4)}_{\text{eff}}(r)\;,$ (41)

and it may be obtained by using the properly redefined
${\mathcal{S}}_{\text{eff}}$ in (18), after integrating out the EM field
fluctuations, and discarding self-energy terms, the result being

$\displaystyle\Gamma^{(4)}_{\text{eff}}(r)\;=\;-\frac{1}{2}\,\int d^{4}x\int
d^{4}y$ $\displaystyle\int d^{4}z\int d^{4}w\,\Big{[}\Delta(x-y)\Delta(z-w)$
$\displaystyle\times\,\langle J_{\mu}^{(1)}(x)J_{\nu}^{(1)}(z)\rangle\,\langle
J_{\mu}^{(2)}(y)J_{\nu}^{(2)}(w)\rangle\Big{]}\;.$ (42)

Here, the functional averaging is understood with the (40) action determining
the respective weight; namely:

$\langle
J_{\mu}^{(\alpha)}(x)J_{\nu}^{(\alpha)}(y)\rangle\,\equiv\,\frac{\int{\mathcal{D}}{\mathbf{x}}^{(\alpha)}\;J_{\mu}^{(\alpha)}(x)J_{\nu}^{(\alpha)}(y)\,e^{-{\mathcal{S}}_{0}^{a}({\mathbf{x}}^{(\alpha)})}}{\int{\mathcal{D}}{\mathbf{x}}^{(\alpha)}e^{-{\mathcal{S}}_{0}^{a}({\mathbf{x}}^{(\alpha)})}}$
(43)

(no sum over $\alpha$). The model we are using is such that each electron is
concentrated on one of the atoms, and as a consequence $\langle
J_{\mu}^{(1)}J_{\nu}^{(2)}\rangle=0$.

Recalling the definition of the currents in (2.2), it is clear that the above
averages are going to depend on the correlators involving the coordinates and
velocities of the electrons:

$\displaystyle\langle
x_{i}^{(\alpha)}(\tau)x_{j}^{(\alpha)}(\tau^{\prime})\rangle\;,\;\;$
$\displaystyle\langle\dot{x}_{i}^{(\alpha)}(\tau)x_{j}^{(\alpha)}(\tau^{\prime})\rangle\;\;,$
$\displaystyle\langle\dot{x}_{i}^{(\alpha)}(\tau)\dot{x}_{j}^{(\alpha)}(\tau^{\prime})\rangle\;,\;\;$
$\displaystyle\langle\dot{x}_{i}^{(\alpha)}(\tau)x_{j}^{(\alpha)}(\tau^{\prime})\rangle$
(44)

(no sum over $\alpha$).

Using all the ingredients above, a lengthy but otherwise straightforward
calculation allows us to evaluate (3.3). We find that it is proportional to
the total time and, besides, it may be written as a single integral over a
frequency:

$\displaystyle\Big{[}\frac{\Gamma^{(4)}_{\text{eff}}(r)}{T}\Big{]}_{T\to\infty}\;=\;-\frac{q^{4}}{2}\,\int\frac{d\nu}{2\pi}\,\widetilde{G}_{ij}(\nu)\,\widetilde{G}_{kl}(-\nu)\Big{[}\partial_{i}\partial_{k}\widetilde{\Delta}(\nu,r)\,\partial_{j}\partial_{l}\widetilde{\Delta}(\nu,r)$
$\displaystyle-\nu^{2}\,\delta_{jl}\,\partial_{i}\partial_{k}\widetilde{\Delta}(\nu,r)\widetilde{\Delta}(\nu,r)-\nu^{2}\,\delta_{ik}\,\widetilde{\Delta}(\nu,r)\,\partial_{j}\partial_{l}\widetilde{\Delta}(\nu,r)$
$\displaystyle+\nu^{4}\,\delta_{ik}\delta_{jl}\,\widetilde{\Delta}(\nu,r)\widetilde{\Delta}(\nu,r)\Big{]}\;,$
(45)

where $\widetilde{G}_{ij}(\nu)$ is the Fourier transform of $\langle
x_{i}^{(\alpha)}(\tau)x_{j}^{(\alpha)}(\tau^{\prime})\rangle$:

$\langle
x_{i}^{(\alpha)}(\tau)x_{j}^{(\alpha)}(\tau^{\prime})\rangle\,=\,\int\frac{d\nu}{2\pi}\,e^{i\nu(\tau-\tau^{\prime})}\,\widetilde{G}_{ij}(\nu)\;,$
(46)

and

$\widetilde{\Delta}(\nu,r)\;=\;\frac{e^{-|\nu|r}}{4\pi r}\;.$ (47)

Under the assumption that the potential is central, we may, for each $\alpha$,
write:

$\displaystyle\langle
x_{i}^{(\alpha)}(\tau)x_{j}^{(\alpha)}(\tau^{\prime})\rangle\,=\,\delta_{ij}G(\tau-\tau^{\prime})\;,\;\;\langle\dot{x}_{i}^{(\alpha)}(\tau)x_{j}^{(\alpha)}(\tau^{\prime})\rangle\,=\,\delta_{ij}\partial_{\tau}G(\tau-\tau^{\prime})$
$\displaystyle\langle
x_{i}^{(\alpha)}(\tau)\dot{x}_{j}^{(\alpha)}(\tau^{\prime})\rangle\,=\,-\delta_{ij}\partial_{\tau}G(\tau-\tau^{\prime})\;,\;\langle\dot{x}_{i}^{(\alpha)}(\tau)\dot{x}_{j}^{(\alpha)}(\tau^{\prime})\rangle\,=\,-\delta_{ij}\partial^{2}_{\tau}G(\tau-\tau^{\prime})\;,$
(48)

in terms of a single scalar function $G$ (we recall that the atoms are assumed
to be identical).

Therefore, the energy of interaction becomes:

$\displaystyle
E_{I}\;=\;-\frac{q^{4}}{16\pi^{3}r^{2}}\,\int_{0}^{\infty}\,d\nu\,\big{|}\widetilde{G}(\nu)\big{|}^{2}\,e^{-2\nu
r}\,\Big{(}\nu^{4}+\frac{2\nu^{3}}{r}+\frac{5\nu^{2}}{r^{2}}+\frac{6\nu}{r^{3}}+\frac{3}{r^{4}}\Big{)}\;.$
(49)

Introducing yet again the variable $u\equiv\nu r$,

$\displaystyle
E_{I}\;=\;-\frac{q^{4}}{16\pi^{3}r^{7}}\,\int_{0}^{\infty}du\,e^{-2u}\,\big{|}\widetilde{G}(\frac{u}{r})\big{|}^{2}\,\big{(}u^{4}+2u^{3}+5u^{2}+6u+3\big{)}\;.$
(50)

When $\widetilde{G}(\nu)$ has a finite zero-frequency limit, we can extract
the long-distance behaviour of the interaction energy in terms of that limit.
Besides,

$\widetilde{G}(0)\,=\,\frac{1}{3}\,\int_{-\infty}^{+\infty}\frac{d\nu}{2\pi}\,\langle\big{|}\tilde{x}_{i}(\nu)\big{|}^{2}\rangle\;.$
(51)

Thus, the asymptotic form of the energy is:

$\displaystyle
E_{I}\;=\;-\frac{q^{4}}{16\pi^{3}r^{7}}\,\big{|}\widetilde{G}(0)\big{|}^{2}\,\int_{0}^{\infty}du\,e^{-2u}\,\big{(}u^{4}+2u^{3}+5u^{2}+6u+3\big{)}\;.$
(52)

By evaluating the integral, we get:

$E_{I}\;=\;-\frac{23}{(4\pi)^{3}}\,\frac{q^{4}}{r^{7}}\,\big{|}\widetilde{G}(0)\big{|}^{2}.$
(53)

In the special case of the three-dimensional harmonic potential we just
considered before, we have, $\widetilde{G}(0)=\frac{1}{m\Omega^{2}}$, which
reproduces our previous result.

Finally, note that we can also find the result for the London limit in the
case of a general central potential, since in that approximation we get:

$\displaystyle
E_{I}\;=\;-\frac{3}{4}\,\big{(}\frac{q^{2}}{4\pi}\big{)}^{2}\frac{\pi}{r^{6}}\,\int_{0}^{\infty}d\nu\,\big{|}\widetilde{G}(\nu)\big{|}^{2}\;,$
(54)

which again produces the right result for the harmonic potential case.

##  4 Conclusions

We have presented a derivation of some known expressions for the Van der Waals
interaction energy between two atoms, based on a microscopic description of
the system, and applying functional methods: the energy is obtained by
functional integration of the degrees of freedom in the Euclidean formalism,
in order to obtain the vacuum energy from the resulting effective action.

We have analyzed the region where the description begins to fail, namely, when
the atoms are too close, and the dipole interaction may overcome the binding
energy of the electrons to their respective nuclei. This phenomenon shows up
as the emergence of an imaginary part in the energy, and the consequent vacuum
decay probability per unit time.

We suggest that beyond such a limit a molecular description should be the
proper framework to describe the physics of the system.

Our results may be interpreted as providing a lower bound for the distances to
which one can apply the usual Van der Waals description, in terms of
parameters related to the structure of the atoms (in our case, $m$ and
$\Omega$), and the electromagnetic coupling ($q$). For distances larger that
what we denoted by $r_{1}$, an effective description for the interaction
energy like the one we have used should be reliable.

## Acknowledgements

The authors thank ANPCyT, CONICET and UNCuyo for financial support.

## References

  * [1] P. W. Milonni, “The Quantum vacuum: An Introduction to quantum electrodynamics,” Academic Press: San Diego, CA, USA, (1994).
  * [2] K. A. Milton,“The Casimir effect: Physical manifestations of zero-point energy,” World Scientific: River Edge, NJ, USA (2001).
  * [3] M. Bordag, G. L. Klimchitskaya, U. Mohideen and V. M. Mostepanenko, “Advances in the Casimir effect’, Oxford University Press: Oxford, UK, (2009).
  * [4] V. W. Hughes, The Muonium Atom, Scientific American, 214, 93, (April 1966).
  * [5] V. W. Hughes, Muonium, Physics Today, 20, 29 (Dec. 1967).
  * [6] J. Zinn-Justin, Quantum Field Theory and Critical Phenomena; Oxford University Press, Oxford (2021).
  * [7] I. Klich and O. Kenneth, Journal of Physics: Conference Series 161, 012020 (2009).
  * [8] Abramowitz, Stegun, Handbook of Mathematical Functions: with Formulas, Graphs, and Mathematical Tables; Dover Publications, Washington D.C (1972).
  * [9] G. Feinberg, J. Sucher, Phys. Rev. A, vol 2, p. 2395 (1970).
  * [10] C. Itzykson, J. B. Zuber, Quantum Field Theory; McGraw-Hill, New York (1986).
  * [11] F. London, Z. Phys. 63, 245 (1930).
  * [12] L. Schulman, Techniques and Applications of Path Integration; Dover Publications, Inc., New York (2005).


# Generalized saturation problems for cliques, paths, and stars

Jamie Radcliffe1 Adam Volk1

(1University of Nebraska-Lincoln
)

###### Abstract

A graph $G$ is $F$-saturated if it does not contain any copy of $F$, but the
addition of any missing edge in $G$ creates at least one copy of $F$. Inspired
by work of Alon and Shikhelman regarding a similar question for $F$-free
graphs, Kritschgau, Methuku, Tait, and Timmons introduced the parameter of
$\operatorname{sat}_{H}(n,F)$ to denote the minimum number of copies of some
subgraph $H$ in an $F$-saturated graph on $n$ vertices. In this paper, we
address this generalized saturation problem with special focus on
$\operatorname{sat}_{K_{r}}(n,S_{t})$ and
$\operatorname{sat}_{S_{r}}(n,S_{t})$. This relates to recent work by
Chakraborti and Loh regarding $\operatorname{sat}_{K_{r}}(n,K_{t})$ and by
Ergemlidze, Methuku, Tait, and Timmons regarding
$\operatorname{sat}_{S_{r}}(n,K_{t})$. We also provide some results regarding
paths and arbitrary trees.

Keywords— Cliques, Extremal graph theory, Graph saturation, Stars

##  1 Introduction

A major object of focus in extremal graph theory is the extremal number
$\operatorname{ex}(n,F)$, which denotes the maximum number of edges in an
$F$-free graph on $n$ vertices. The study of such values dates back to Turán
in 1941 [18]. See [17] for a survey by Sidorenko with some results in the
field. More recently, Alon and Shikhelman [2] introduced the generalized
extremal number $\operatorname{ex}_{H}(n,F)$ which gives the maximum number of
copies of $H$ among $F$-free graphs on $n$ vertices. If we take $H$ to be a
single edge, we recover the original extremal number.

In addition to maximizing the number of copies of a given subgraph among
$F$-free graphs, it is also natural to try to understand the minimum. To avoid
trivialities, we say that a graph $G$ is $F$-saturated if $G$ does not contain
any copy of $F$ as a subgraph, but the addition of any missing edge creates at
least one copy of $F$. We do not consider induced subgraphs in this setting
although it is possible to do so. (For instance, see [15] for a consideration
of induced saturation.) The minimum number of edges in an $F$-saturated graph
on $n$ vertices is denoted $\operatorname{sat}(n,F)$. The case where $F$ is
the complete graph was solved by Erdős, Hajnal, and Moon [6] and is stated
here.

######  Theorem 1.1 (Erdős, Hajnal, and Moon, 1964).

For every $n\geq t\geq 2$,

$\operatorname{sat}(n,K_{t})=(n-t+2)(t-2)+\binom{t-2}{2}.$

The graph $K_{t-2}+\overline{K}_{n-t+2}$ is the unique extremal example.

Saturation numbers have been well-studied and a collection of some of these
results can be found in [9]. Inspired by the generalization of Alon and
Shikhelman in the $F$-free setting, Kritschgau, Methuku, Tait, and Timmons
[12] introduced the generalized saturation number
$\operatorname{sat}_{H}(n,F)$ to denote the minimum number of copies of $H$ in
an $F$-saturated graph on $n$ vertices. In addition to proving general
results, they focused on the cases where at least one of $H$ and $F$ was a
clique or cycle. Extending a result of Kritschgau et al. and proving a
conjecture from that paper, Chakraborti and Loh [4] showed the following.

######  Theorem 1.2 (Chakraborti and Loh, 2019).

For every $t>r\geq 2$, there exists a constant $n_{r,t}$ such that, for all
$n\geq n_{r,t}$, we have

$\operatorname{sat}_{K_{r}}(n,K_{t})=(n-t+2){{t-2}\choose{r-1}}+{{t-2}\choose{r}}.$

Furthermore, for $n$ sufficiently large, the (complete) split graph
$K_{t-2}+\overline{K}_{n-t+2}$ is the unique extremal example.

Chakraborti and Loh asked if the split graph minimizes the number of copies of
any $F$ among $K_{t}$-saturated graphs. Using stars as their choice of $F$,
Ergemlidze, Methuku, Tait, and Timmons [7] proved that this is not the case.
Furthermore, the split graph was far from optimal.

In this paper, we look at the other variations involving stars and cliques,
namely $\operatorname{sat}_{K_{r}}(n,S_{t})$ and
$\operatorname{sat}_{S_{r}}(n,S_{t})$. We also consider
$\operatorname{sat}_{S_{r}}(n,K_{t})$ in a more restricted setting as well as
generalized saturation numbers involving paths.

###  1.1 Notation and organization

In general our notation follows that of Bollobás [3]. In particular, we write
$G_{1}+G_{2}$ to denote the join of two graphs $G_{1}$ and $G_{2}$. That is,
we take the disjoint union of the two graphs and add the edge $uv$ for every
vertex $u$ in $G_{1}$ and $v$ in $G_{2}$. We similarly write $G_{1}\cup G_{2}$
for the disjoint union of $G_{1}$ and $G_{2}$ with no added edges. For a given
vertex $v$, we write $N(v)$ to denote the neighborhood of $v$ and $N[v]$ to
denote the closed neighborhood of $v$. That is, $N[v]=N(v)\cup\\{v\\}$. We
write $(n)_{k}$ to denote the falling factorial $n(n-1)\cdots(n-k+1)$ and will
make use of the generalized binomial coefficient which is defined to be
${{x}\choose{k}}=\frac{1}{k!}x(x-1)\cdots(x-k+1)$ for an arbitrary real number
$x$ and integer $k$.

Given a graph $G$, we let $k_{r}(G)$ and $s_{r}(G)$ denote the number of
copies of cliques $K_{r}$ and stars $S_{r}$ in $G$ respectively. Using the
notation of Gallian [10], we let $S_{r}$ denote a star on $r+1$ vertices and
$r$ edges.

The paper is organized as follows. In Section 2 and Section 3 we count cliques
and stars respectively in star-saturated graphs. In Section 4, we briefly
discuss the problem of counting stars in clique-saturated graphs. In
particular, we comment on a recent result of Ergemlidze, Methuku, Tait, and
Timmons [7] and state a result regarding clique-saturated graphs with linear
maximum degree. In Section 5, we provide an asymptotic result regarding the
minimum number of paths in clique-saturated graphs. We also use a result of
Kaszonyi and Tuza [13] to show that for $n$ sufficiently large, the minimum
number of copies of $K_{r}$ in path-saturated graphs is in fact $0$ for all
$r\geq 3$. We finish in Section 6 with a brief discussion of some more general
results regarding cliques and trees.

###  1.2 Graph constructions

In the sections that follow, we will make use of certain graphs that are
regular or almost regular. The first construction concerns regular
multipartite graphs. Before presenting the construction, we state a theorem of
Hoffman and Rodger [11].

######  Theorem 1.3 (Hoffman and Rodger, 1992).

Given a complete multipartite graph $K$, $\chi^{\prime}(K)=\Delta(K)$ if and
only if it is not overfull. Here $\chi^{\prime}$ denotes the chromatic index
of $K$, and we say that a graph $G$ is overfull if
$|E(G)|>\Delta(G)\left\lfloor\frac{|V(G)|}{2}\right\rfloor$. In particular,
the complete $r$-partite graph $K_{a,\dots,a}$ is overfull if and only if $ar$
is odd.

######  Proposition 1.4.

Let $a,r$ be positive integers. If $ar$ is even, there exists a $k$-regular
spanning subgraph of the $r$-partite graph $K_{a,\dots,a}$ for all $k\leq
a(r-1)$.

###### Proof.

Consider the complete $r$-partite graph $K_{a,\dots,a}$. If $ar$ is even, then
$K_{a,\dots,a}$ is not overfull. By Theorem 1.3, the chromatic index of this
graph is equal to the maximum degree. That is, we can give a proper edge
coloring using $a(r-1)$ colors. In particular, the color classes form a
$1$-factorization of $K_{a,\dots,a}$. We delete perfect matchings until we are
left with a $k$-regular subgraph for any $k\leq a(r-1)$. ∎

For our next construction, given $a<b$, we let $R_{a,b}$ denote a graph on $b$
vertices that is as close to $a$-regular as possible. More specifically, when
$ab$ is even, $R_{a,b}$ is $a$-regular. When $ab$ is odd, $R_{a,b}$ has one
vertex of degree $a-1$ and $b-1$ vertices of degree $a$.

######  Lemma 1.5.

An $R_{a,b}$ exists if and only if $b\geq a+1$.

###### Proof.

It is well known that $a$-regular graphs exist on $b$ vertices if and only if
$b\geq a+1$ and $ab$ is even. When $b\geq a+1$ and $ab$ is odd, we can obtain
a graph on $b$ vertices that is $a$-regular with the exception of one vertex
of degree $a-1$ in the following manner. Label the vertices $0,1,\dots,b-1$.
Add edges between vertices with labels $i$ and $j$ if and only if

$|i-j|\leq\frac{a-1}{2}\mod{b}.$

Finally for $1\leq i\leq\frac{b-1}{2}$, add an edge between the vertices
labeled $i$ and $i+\frac{b-1}{2}\mod{b}$. We aren’t reusing any edges since
$b\geq a+1$, and the degree of every vertex increases by $1$, except for the
vertex labeled $0$. Thus every vertex has degree $a$ with the exception of one
vertex of degree $a-1$, and $R_{a,b}$ exists. Necessity is clear because a
graph can’t have any vertex of degree $a$ if there are fewer than $a+1$
vertices. ∎

Utilizing the regularity of $R_{a,b}$, we define some candidate extremal
graphs for $\operatorname{sat}_{S_{r}}(n,S_{t})$ that will be studied in
Section 3. They are essentially the disjoint union of a clique and a regular
graph. To be precise, for $m\leq t-1$ we let

$\operatorname{KR}_{t,n}(m)=\begin{cases}K_{m}\cup R_{t-1,n-m}&\text{if
$(t-1)(n-m)$ is even}\\\ K_{m}\cup R_{t-1,n-m}+e&\text{if $(t-1)(n-m)$ is
odd},\end{cases}$

where in the second case $e$ is an edge between the vertex of degree $t-2$ in
$R_{t-1,n-m}$ and an arbitrary vertex of the clique $K_{m}$.

##  2 Cliques in star-saturated graphs

We begin this section with a structural lemma regarding star-saturated graphs,
which was observed by Kaszonyi and Tuza [13]. We include the proof for
completeness.

######  Lemma 2.1.

Let $G$ be an $S_{t}$-saturated graph on $n$ vertices. Then the maximum degree
of $G$ is $t-1$, and all vertices of degree less than $t-1$ form a clique.

###### Proof.

Since $G$ is $S_{t}$-saturated, it must be $S_{t}$-free. Thus the maximum
degree of $G$ is at most $t-1$. Adding any missing edge can increase the
maximum degree by at most $1$. Since $G$ is $S_{t}$-saturated, the new edge
must force the maximum degree to become $t$. Thus $G$ has maximum degree
exactly $t-1$.

To prove the second part of the statement, suppose that $u$ and $v$ are
vertices in $G$ with degrees $d(u)<t-1$ and $d(v)<t-1$. If $u$ is not adjacent
to $v$, then the addition of the edge $uv$ will only increase their degrees,
and the resulting graph will still have maximum degree less than $t$, a
contradiction to $G$ being $S_{t}$-saturated. Therefore all vertices of degree
less than $t-1$ must form a clique in $G$. ∎

The following result allows us to completely determine the minimum number of
copies of $K_{r}$ in an $S_{t}$ saturated graph for all $r\geq 3$ and $t\geq
3$ when $n$ is sufficiently large. Note that for $t=1$ we need $n\geq 2$, and
for $t=2$ we need $n\geq 3$ for $S_{t}$-saturated graphs to exist. In
particular, there is a unique $S_{2}$-saturated graph on $n$ vertices for all
$n\geq 3$. When $n$ is even, the graph is a collection of disjoint edges. When
$n$ is odd, it is a collection of disjoint edges and an isolated vertex.
$S_{1}$-saturated graphs are simply independent sets on at least $2$ vertices.

######  Proposition 2.2.

Let $t\geq 3$. There exists an $S_{t}$-saturated graph on $n$ vertices that is
$K_{3}$-free if and only $n\geq 2t-2$.

###### Proof.

If $n$ is even and $n\geq 2t-2$, there exists an $(t-1)$-regular bipartite
graph on $n$ vertices. This is certainly $S_{t}$-saturated. When $n$ is odd,
consider $G\cup K_{1}$ where $G$ is a $(t-1)$-regular bipartite graph on $n-1$
vertices. The resulting graph is still $S_{t}$-saturated and bipartite, hence
$K_{3}$-free.

For the other direction, let $G$ be $S_{t}$-saturated and $K_{3}$-free. If $G$
has no vertices of degree $t-1$, then by Lemma 2.1 $G$ is complete and
contains triangles. This means there is a vertex $v\in G$ with degree $t-1$.
For any two vertices $x,y\in N(v)$, at least one of them must have degree
$t-1$. Otherwise $x$ is adjacent to $y$ and $v,x,y$ form a copy of $K_{3}$.
Without loss of generality, the degree of $x$ is $t-1$. Since $G$ is
$K_{3}$-free, $N(v)\cap N(x)=\varnothing$, and $N(x)$ contains $t-2$ vertices
outside of $N[v]$. Therefore $n\geq 2t-2$. ∎

The following is immediate.

######  Corollary 2.3.

For all $r\geq 3$ and all $t\geq 3$,

$\operatorname{sat}_{K_{r}}(n,S_{t})=0$

for $n\geq 2t-2$. When $t=1,2$,

$sat_{K_{r}}(n,S_{t})=0$

when $n\geq 2,3$ respectively.

Proposition 2.2 gives us a cutoff for the values of $n$ which require
$S_{t}$-saturated graphs to contain at least one copy of $K_{3}$. It tells us,
for instance, that any $S_{5}$-saturated graph that is $K_{3}$-free must have
at least $8$ vertices. Although there does not exist such a graph on $6$
vertices, the graph in Figure 1 is an example of an $S_{5}$-saturated graph on
$6$ vertices that, although not $K_{3}$-free, is $K_{4}$-free.

123456 Figure 1: An example of a $K_{4}$-free, $S_{5}$-saturated graph on
fewer than $8$ vertices

These results, together with this observation, lead us to the following
question.

######  Question 2.4.

Given a fixed $r\geq 3$ and $t\geq 3$, for which values of $n$ do there exist
$S_{t}$-saturated graphs that are $K_{r+1}$-free? Furthermore, what are the
possible values of the number of copies of $K_{r}$ in $S_{t}$-saturated graphs
on $n$ vertices?

We provide a partial answer to the first question, focusing especially on the
existence of $S_{t}$-saturated graphs that are $r$-partite. Due to the
triviality of the cases where $t=1,2$, our general results consider $t\geq 3$.

######  Theorem 2.5.

Let $r\geq 3$ and $t\geq 3$ be fixed. There exists an $n$-vertex, $r$-partite,
$S_{t}$-saturated graph if

$n\geq\max\left(t+1,\min_{0\leq c\leq
r-2}\left\\{(r-c)\left\lceil\frac{t-1}{r-c-1}\right\rceil+r-c\right\\}\right).$
(1)

###### Proof.

Suppose (1) holds for some $0\leq c\leq r-2$. Let $a,b$ be non-negative
integers such that $n=a(r-c)+b$ with $b<r-c$. That is,
$a=\lfloor\frac{n}{r-c}\rfloor$. In addition, let $k,d$ be non-negative
integers such that $b=kt+d$ with $d<t$. We will consider two cases and exhibit
an $r$-partite, $S_{t}$-saturated graph on $n$ vertices in each case.

Begin by supposing $a(r-c)$ is even. By rewriting (1), we see that $t-1\leq
a(r-c-1).$ By Proposition 1.4, there exists a $(t-1)$-regular, $(r-c)$-partite
graph $G$ on $a(r-c)$ vertices. Taking the disjoint union $G\cup kK_{t}\cup
K_{d}$ yields an $r$-partite, $S_{t}$-saturated graph on $n$ vertices.

Similarly, when $a(r-c)$ is odd, there exists a $(t-1)$-regular,
$(r-c)$-partite graph $G$ on $(a-1)(r-c)$ vertices. Thus $G\cup\ell K_{t}\cup
K_{m}$ where $b+r-c=\ell t+m$ with $m<t$ provides an $r$-partite,
$S_{t}$-saturated graph on $n$ vertices. ∎

With regards to the lower bounds on $n$, we note that if $n<t+1$, then there
is no $S_{t}$-saturated graph on $n$ vertices, and hence none that is
$r$-partite. We now provide a necessary condition for the existence of
$S_{t}$-saturated, $r$-partite graphs that is related to the other bound in
Theorem 2.5.

######  Proposition 2.6.

For all $r\geq 3$ and $t\geq 3$, if there exists a graph $G$ on $n$ vertices
that is an $S_{t}$-saturated graph and $r$-partite, then
$n\geq\frac{r(t-1)}{r-1}$.

###### Proof.

Suppose such a graph $G$ exists with $n<\frac{r(t-1)}{r-1}$. Let $a,b$ be non-
negative integers such that $n=ar+b$ with $b<r$. Since $G$ is $r$-partite,
there exists a partition $P_{1},\dots,P_{r}$ of the vertices of $G$ with
$|P_{i}|\leq|P_{i+1}|$ for all $1\leq i\leq r-1$ such that no two vertices in
a given $P_{i}$ are adjacent. We have two cases to consider.

Begin by supposing that $|P_{1}|<|P_{r}|$. If $a=0$, then $G$ has $b$ vertices
with $b<r$. Since $G$ is $S_{t}$-saturated, we have $b\geq t+1$, and, by
assumption, $b<\frac{r(t-1)}{r-1}$. It follows that $t+1<\frac{r(t-1)}{r-1}$.
Rearranging, we have $2r<t+1$, a contradiction since $b<r$ and $b\geq t+1$.
Thus it must be the case that $a\geq 1$.

Now, since $|P_{1}|<|P_{r}|$, it follows that

$|P_{r}|\geq\left\lceil\frac{n}{r}\right\rceil=a+1.$

For any vertex $u\in P_{r}$, we have $d(u)\leq n-a-1$. Since each $P_{i}$ is
an independent set, it can contain at most one vertex of degree less than
$t-1$. In particular, since $a\geq 1$, $P_{r}$ must contain at least one
vertex of degree exactly $t-1$. Thus $n-a-1\geq t-1$. Since
$n<\frac{r(t-1)}{r-1}$ by assumption, we have

$\displaystyle\frac{r(t-1)}{r-1}$ $\displaystyle>t+a.$ After rearranging the
previous inequality and noting that $t-1\leq n-a-1=a(r-1+b-1)$, we have
$\displaystyle a(r-1)+b-1$ $\displaystyle>a(r-1)+r-1,$

contradicting the assumption that $b<r$.

Finally, we consider the case where each of the $r$ parts have equal size. It
follows that $b=0$ and $n=ar$. Every vertex in $G$ has degree at most
$a(r-1)$. Since $n<\frac{r(t-1)}{r-1}$, we have that $a(r-1)<t-1$. This means
that if we add an edge to $G$, the maximum degree is at most $t-1$, a
contradiction to the assumption that $G$ is $S_{t}$-saturated. ∎

In addition to bridging the gap between these bounds, we would like to know
which value of $c$ for given $r$ and $t$ minimizes the lower bound on $n$ in
Theorem 2.5. If our bound did not include ceilings, this would be a
straightforward computation as demonstrated in the lemma below. However,
finding a general solution using the bound in the theorem is more complicated.
Although we do not have a general solution, we determine which value of $c$
provides the smallest bound on $n$ in Theorem 2.5 for the existence of
$r$-partite, $S_{t}$-saturated graphs in two special cases.

######  Lemma 2.7.

Let $r\geq 3$ and $t\geq 3$ be fixed. Then

$n_{2}(c)=(r-c)\left(\frac{t-1}{r-c-1}\right)+r-c$

is minimized on the interval $[0,r-2]$ when $c=r-1-\sqrt{t-1}$.

###### Proof.

Taking the derivative with respect to $c$, we obtain

$n_{2}^{\prime}(c)=\frac{t-1}{(r-c-1)^{2}}-1.$

Setting this equal to $0$, we have $c=r-1\pm\sqrt{t-1}$. Since $c\leq r-2$ and
$n_{2}^{\prime\prime}(r-1-\sqrt{t-1})<0$, our function is minimized at
$c=r-1-\sqrt{t-1}$. ∎

######  Proposition 2.8.

For all $r\geq 3$, if $t\leq(r-1)^{2}+1$ and $t=k^{2}+1$ for some integer $k$,
then $r-1-\sqrt{t-1}$ is the minimizing $c$-value in Theorem 2.5. The
corresponding lower bound on $n$ is $n\geq(k+1)^{2}=t+2\sqrt{t-1}$.

###### Proof.

Let

$n_{1}(c)=(r-c)\left\lceil\frac{t-1}{r-c-1}\right\rceil+r-c$

and

$n_{2}(c)=(r-c)\left(\frac{t-1}{r-c-1}\right)+r-c.$

That is, $n_{1}(c)$ provides the lower bounds on $n$ for the $(r-c)$-partite
construction in Theorem 2.5. By Lemma 2.7, $n_{2}(c)$ is minimized when
$c=r-1\pm\sqrt{t-1}$ on the interval $[0,r-2]$. Since $n_{1}(c)\geq n_{2}(c)$
for all $c$, it follows that $n_{1}(c)$ is minimized at $c=r-1-\sqrt{t-1}$ if
$n_{1}(r-1-\sqrt{t-1})=n_{2}(r-1-\sqrt{t-1})$. This is true precisely when
$t=k^{2}+1$ for some integer $k$. We finally note that in this setting
$n_{1}(r-1-\sqrt{t-1})=t+2\sqrt{t-1}$. ∎

######  Proposition 2.9.

For all $r\geq 3$, if $t\geq(r-1)^{2}+1$ and $r-1$ divides $t-1$, then $0$ is
the minimizing $c$-value in Theorem 2.5. The corresponding lower bound on $n$
is $n\geq r\left(\frac{t-1}{r-1}\right)+r$.

###### Proof.

Define $n_{1}(c)$ and $n_{2}(c)$ as in the previous proof. Since
$t\geq(r-1)^{2}+1$, we have that $r-1-\sqrt{t-1}\leq 0$. Thus $n_{2}(c)$ is
increasing on the interval $[0,r-2]$. It follows that $n_{1}(c)$ is minimized
at $c=0$, if $n_{1}(0)=n_{2}(0).$ This is true precisely when
$\frac{t-1}{r-1}$ is an integer. That is, when $r-1$ divides $t-1$. We finally
note that in this setting $n_{1}(0)=r\bigl{(}\frac{t-1}{r-1}\bigr{)}+r$. ∎

Note that when $t>(r-1)^{2}+1$, Proposition 2.8 shows that the minimizing
$c$-value for Theorem 2.5 is not $0$. That is, starting with fewer parts than
what we’re permitted leads to a smaller lower bound on $n$.

We conclude this section by providing necessary conditions for the existence
of $S_{t}$-saturated graphs on $n$ vertices that are $K_{r+1}$-free.

######  Lemma 2.10.

Let $G$ be an $S_{t}$-saturated graph on $n$ vertices with $m$ vertices of
degree less than $t-1$ and no copy of $K_{r+1}$. Then

$n\geq\frac{r}{r-1}\left(\frac{t-1}{2}+\sqrt{\left(\frac{t-1}{2}\right)^{2}-\frac{m(r-1)(t-m)}{r}}\right).$

###### Proof.

Since $G$ is $K_{r+1}$-free, we have by Turán’s Theorem that

$e(G)\leq\frac{r-1}{r}\cdot\frac{n^{2}}{2}.$

Using the structure of $S_{t}$-saturated graphs described in Lemma 2.1 at the
beginning of this section, we also have that

$e(G)\geq\frac{1}{2}(n-m)(t-1)+{{m}\choose{2}}$

for some value of $m$. These two bounds together provide the desired
inequality. ∎

Considering the case where $t\geq 2r$, we provide a general bound independent
of the existence of $S_{t}$-saturated, $K_{r}$-free graphs with specific $m$.
We also demonstrate when these bounds are at least $t+1$, the trivial
necessary condition for the existence of an $S_{t}$-saturated graph.

######  Proposition 2.11.

Let $G$ be an $S_{t}$-saturated graph on $n$ vertices with no copy of
$K_{r+1}$ where $t\geq 2r$ and $r\geq 2$. Then

$n\geq\frac{r}{r-1}\left(\frac{t-1}{2}+\sqrt{\left(\frac{t-1}{2}\right)^{2}-(r-1)(t-r)}\right).$

Furthermore, this bound is at least $t+1$ whenever $t\geq r(r+1)-1$.

###### Proof.

We begin by noting that the bound in Lemma 2.10 is minimized at $m=r$. This is
because $m\leq r$ by Lemma 2.1 and because the bound in Lemma 2.10 is
decreasing in $m$ for $m<t/2$. Plugging this value in for $m$ yields the
desired bound. Letting $n(t)$ denote this bound, we observe that
$n(r(r+1)-1)=r(r+1)=t+1$. In addition, $n^{\prime}(t)\geq\frac{r}{r-1}$ for
all $t$. By the racetrack principle, $n(t)\geq t+1$ whenever $t\geq r(r+1)-1$
as desired. ∎

Finally, we observe that the bound in Lemma 2.10 is asymptotically equivalent
to the bound in Proposition 2.6.

######  Proposition 2.12.

Let $r$ be fixed. If there exists an $S_{t}$-saturated graph on $n$ vertices
with no copy of $K_{r+1}$ where $t\geq 2r$ and $r\geq 3$, then

$n\geq\frac{r(t-1)}{r-1}-O_{t}(1).$

###### Proof.

Note that the number of vertices, that is $m$, of degree less than $t-1$, in a
$K_{r+1}$-free graph is at most $r$ since these vertices form in a clique in
$S_{t}$-saturated graphs. Thus the following holds as $t\geq 2r$.

$\displaystyle\frac{r}{r-1}\left(\frac{t-1}{2}+\sqrt{\left(\frac{t-1}{2}\right)^{2}-\frac{m(r-1)(t-m)}{r}}\right)$
$\displaystyle\geq\frac{r}{r-1}\left(\frac{t-1}{2}+\frac{t-1}{2}-\frac{m(r-1)t}{r(t-1)}\right)$
$\displaystyle=\frac{r}{r-1}\left(t-1-O_{t}(1)\right)$
$\displaystyle=\frac{r(t-1)}{r-1}-O_{t}(1).\qed$

##  3 Stars in star-saturated graphs

###  3.1 General results for stars in star-saturated graphs

We now turn to counting copies of stars $S_{r}$ in $S_{t}$-saturated graphs.
As stated in the introduction, we write $s_{r}(G)$ to denote the number of
copies of $S_{r}$ in a given graph $G$ where $S_{r}$ is the complete bipartite
graph $K_{1,r}$. Note that if $t\leq r$, then
$\operatorname{sat}_{S_{r}}(n,S_{t})=0$ trivially as an $S_{t}$-saturated
graph must be $S_{t}$-free. That is, any $S_{t}$-saturated graph has no vertex
of degree at least $t$, and hence none of degree at least $r$. Our focus is
therefore on the situation where $t>r$, and we will consider the cases where
$t$ is odd and even separately. We also ignore the case where $t=1$ as the
only $S_{1}$-saturated graph on $n$ vertices is an independent set.

We stated in Section 1.2 that $\operatorname{KR}_{t,n}(m)$ would be a
candidate for achieving $\operatorname{sat}_{S_{r}}(n,S_{t})$. Our next
theorem shows that this graph does exactly that.

######  Theorem 3.1.

For all $n\geq 2t-1$ with $t\geq 2$ and $r<t$,

$\operatorname{sat}_{S_{r}}(n,S_{t})=\min_{0\leq m\leq
t-1}s_{r}(\operatorname{KR}_{t,n}(m)).$

Note also that

$s_{r}(\operatorname{KR}_{t,n}(m))=\begin{cases}m{{m-1}\choose{r}}+(n-m){{t-1}\choose{r}}&\text{if
$(t-1)(n-m)$ is even}\\\
m{{m-1}\choose{r}}+(n-m){{t-1}\choose{r}}+{{m-1}\choose{r-1}}&\text{if
$(t-1)(n-m)$ is odd.}\end{cases}$

###### Proof.

We begin by considering the case where $t$ is odd. By Lemma 2.1, if $G$ is
$S_{t}$-saturated, then $G$ contains a clique $A$ containing all of the
vertices with degree smaller than $t-1$. Let $A$ have size $m$, and let
$B=V(G)\setminus A$. We have two cases to consider. If $G$ has no edges
between $A$ and $B$, then $G$ contains exactly
$m{{m-1}\choose{r}}+(n-m){{t-1}\choose{r}}$ copies of $S_{r}$. The first term
counts stars centered in $A$, and the second term counts stars centered in
$B$. Since $t-1$ is even, there exists a $(t-1)$-regular graph $R_{t-1,n-m}$
on $n-m$ vertices for all $n-m\geq t$. This inequality holds since we assume
$n\geq 2t-1$ and $m\leq t-1$. Thus an $S_{t}$-saturated graph with precisely
the above count is given by $\operatorname{KR}_{t,n}(m)$.

Now, if there exist vertices $u\in A$ and $v\in B$ such that $u$ is adjacent
to $v$, then our graph contains all of the previously counted stars, along
with at least ${{m-1}\choose{r-1}}$ stars centered at $u$ containing the edge
$uv$. This means than an $S_{t}$-saturated graph $G$ with $|A|=m$ and any such
edge must have at least as many copies of $S_{r}$ as
$\operatorname{KR}_{t,n}(m)$. Thus an $S_{t}$-saturated graph with minimum
number of copies of $S_{r}$ is given by some $\operatorname{KR}_{t,n}(m)$ for
some $m\leq t-1$.

We now consider the case where $t$ is even. For a given $m\leq t-1$, if $n-m$
is even, we can find a $(t-1)$-regular graph on $n-m$ vertices, and the
argument is the same as before. That is, among $S_{t}$-saturated graphs with
$m$ vertices of degree less than $t-1$, $\operatorname{KR}_{t,n}(m)$ is a
minimal example with respect to copies of $S_{r}$. When $n-m$ is odd, we can
construct a graph $R_{t-1,n-m}$ on $n-m$ vertices that is $(t-1)$-regular with
the exception of one vertex $v$ of degree $t-2$. Thus we can construct an
$S_{t}$-saturated graph $\operatorname{KR}_{t,n}(m)$ by taking the disjoint
union of $K_{m}$ with $R_{t-1,n-m}$ and adding an edge from $v$ to an
arbitrary vertex in the clique $K_{m}$. Since every $S_{t}$-saturated graph
with $m$ vertices of degree less than $t-1$ has at least
$m{{m-1}\choose{r}}+(n-m){{t-1}\choose{r}}$ many copies of $S_{r}$ and there
is no $(t-1)$-regular graph on $n-m$ vertices, this adds the fewest possible
copies of $S_{r}$. That is, we must have at least one edge between $A$ and
$B$, introducing ${{m-1}\choose{r-1}}$ copies of $S_{r}$. Therefore the
generalized saturation number is obtained by minimizing
$s_{r}(\operatorname{KR}_{t,n}(m))$ over all values of $m$ between the two
scenarios. ∎

We note that the above theorem does not hold when $n<2t-1$. This is because it
is possible for an $S_{t}$-saturated graph to have fewer than $t$ vertices of
degree $t-1$. This means we can’t consider the disjoint union of a small
clique and a $(t-1)$-regular graph. In this setting, it turns out than an
optimal graph does not need to have that structure. For example, a quick check
shows that the graph in Figure 2 minimizes the number of copies of $S_{3}$
among $S_{5}$-saturated graphs on $6$ vertices and has only $4$ vertices of
degree $4$.

Figure 2: An example of an $S_{5}$-saturated graph that does not satisfy the
criteria in Theorem 3.1

We now introduce additional notation to aid in our discussion of this topic.
Given $n,r,$ and $t$ with $n\geq\max\\{2t-1,t+1\\}$, we define

$m_{0}(n,r,t):=\underset{m}{\operatorname{argmin}}\
s_{r}(\operatorname{KR}_{t,n}(m)).$

That is, $m_{0}(n,r,t)$ is the value of $m$ for which
$\operatorname{KR}_{t,n}(m)$ attains the generalized saturation number
$\operatorname{sat}_{S_{r}}(n,S_{t})$. If the generalized saturation number is
achieved for multiple values of $m$, we take the smallest one for
definiteness. In light of Theorem 3.1, our goal is to identify the value of
$m_{0}(n,r,t)$ for given values of $n,r,$ and $t$. Kaszonyi and Tuza [13]
showed that the number of edges in an $S_{t}$-saturated graph is minimized
when $m=\lfloor\frac{t}{2}\rfloor$ or $\lfloor\frac{t+1}{2}\rfloor$, answering
our question for $r=1$. This solution does not hold for all $r\geq 1$ though.
Rather $m_{0}(n,r,t)$ depends on both $r$ and $t$. The value of $n$ does not
matter for $n\geq 2t-1$ since we are simply getting more vertices of degree
$t-1$ as we increase $n$. The particular value of $n$ does matter when
$t+1\leq n<2t-1$ though. This is because there may not exist a $(t-1)$-regular
graph on $n-m$ as demonstrated by the example in Figure 2.

Although we are unable to provide a closed form for $m_{0}(n,r,t)$ for
arbitrary pairs of $r$ and $t$, there is more we can say about the optimal
choice, or in some cases, choices. We begin with the observation that

$\mathcal{D}(m):=s_{r}(\operatorname{KR}_{t,n}(m+1))-s_{r}(\operatorname{KR}_{t,n}(m))=(r+1){{m}\choose{r}}-{{t-1}\choose{r}}.$
(2)

That is, $\mathcal{D}(m)$ denotes the change in the number of copies of
$S_{r}$ as we increase $m$, the number of vertices of degree less than $t-1$,
by $1$. The following is an immediate consequence of this observation.

######  Lemma 3.2.

If $t$ is odd, then for all $n\geq 2t-1$ with $t>r$, we have $m_{0}(n,r,t)\geq
r$. In particular, $m_{0}(n,t-1,t)=t-1$.

###### Proof.

If $m<r$, then ${{m}\choose{r}}=0$ and so $\mathcal{D}(m)<0$. That is,
$s_{r}(\operatorname{KR}_{t,n}(m+1))<s_{r}(\operatorname{KR}_{t,n}(m))$
whenever $m<r$. Therefore the minimum must be attained when $m\geq r$. To
prove the second statement, we observe that when $r=t-1$,
$\mathcal{D}(t-1)=t-1>0$. Since $\mathcal{D}$ is an increasing function, it
follows that $m_{0}(n,t-1,t)=t-1$. ∎

For fixed $t$ and $r$, we extend the definition of $\mathcal{D}$ in (2) to all
real numbers:

$\mathcal{D}(x):=(r+1){{x}\choose{r}}-{{t-1}\choose{r}}.$

Now, ${{x}\choose{r}}$ is convex and increasing in $x$ for all $x\geq r-1$. It
follows that those properties hold for $\mathcal{D}(x)$ as well. Thus
$\mathcal{D}(x)$ has a unique root on the interval $(r-1,\infty)$ as
$\mathcal{D}(r-1)=-{{t-1}\choose{r}}$. Our next theorem takes advantage of
this structure.

######  Theorem 3.3.

For fixed $n,r,$ and $t$ with $n\geq 2t-1$ and $t>r$, let $\overline{x}$
denote the unique root of $\mathcal{D}(x)$ in the interval $(r-1,\infty)$.
Then

$m_{0}(n,r,t)=\lceil\overline{x}\rceil.$

Furthermore, when $\overline{x}\not\in\mathbb{Z}$, this is the unique
minimizing value of $m$ in Theorem 3.1. When $\overline{x}\in\mathbb{Z}$, both
$\overline{x}$ and $\overline{x}+1$ simultaneously minimize the number of
copies of $S_{r}$ among $S_{t}$-saturated graphs on $n$ vertices.

###### Proof.

As stated previously, $\mathcal{D}(x)$ has a unique root $\overline{x}$ and is
increasing on the interval $[r-1,\infty)$. Let $m\geq r$ be an integer. If
$m<\overline{x}$, then $\mathcal{D}(m)<0$ and
$s_{r}(\operatorname{KR}_{t,n}(m+1))<s_{r}(\operatorname{KR}_{t,n}(m))$. If
$m>\overline{x}$, then $\mathcal{D}(m)>0$ and
$s_{r}(\operatorname{KR}_{t,n}(m+1))>s_{r}(\operatorname{KR}_{t,n}(m))$. If
$\overline{x}\not\in\mathbb{Z}$, then it follows that
$s_{r}(\operatorname{KR}_{t,n}(m))$ is minimized when $m$ is the first integer
larger than $\overline{x}$, namely $\lceil\overline{x}\rceil$, and this choice
of $m$ is unique.

On the other hand, if $\overline{x}\in\mathbb{Z}$, then
$\mathcal{D}(\overline{x})=0$ and
$s_{r}(\operatorname{KR}_{t,n}(\overline{x}+1))=s_{r}(\operatorname{KR}_{t,n}(\overline{x}))$.
Therefore $s_{r}(\operatorname{KR}_{t,n}(m))$ is minimized by $\overline{x}$
and $\overline{x}+1$ simultaneously. These are the only optimal choices for
$m$ as $\mathcal{D}(\overline{x}-1)<0$ and $\mathcal{D}(\overline{x}+1)>0$. ∎

We conclude the discussion on general results by providing two lower bounds on
the value of $m_{0}(n,r,t)$ and giving a more precise answer for $t=2$. The
second lower bound will be of additional interest in the following section on
asymptotic results. Before stating these results, we prove a simple lemma
regarding binomial coefficients.

######  Lemma 3.4.

If $a\geq c\geq 2$ and $b>1$ where $a,b\in\mathbb{R}$ and $c\in\mathbb{Z}$,
then

$b^{c}{{\lfloor a/b\rfloor}\choose{c}}<{{a}\choose{c}}.$

###### Proof.

Note that if $\lfloor a/b\rfloor<c$, then the inequality holds trivially as
the left hand side of our inequality is equal to $0$, and the right hand side
is positive. Suppose then that $\lfloor a/b\rfloor\geq c$. Then we have the
following

$\displaystyle b^{c}(\lfloor a/b\rfloor)_{c}$ $\displaystyle=b^{c}(\lfloor
a/b\rfloor)(\lfloor a/b\rfloor-1)\cdots(\lfloor a/b\rfloor-(c-1))\leq
a(a-b)(a-2b)\cdots(a-b(c-1))$ and $\displaystyle(a)_{c}$
$\displaystyle=a(a-1)(a-2)\cdots(a-(c-1)).$

Since $0<a-bk<a-k$ for all $1\leq k\leq c-1$ and $b>1$, the desired inequality
holds. ∎

We now proceed to state and prove our lower bounds on the optimal choice for
$m$.

######  Corollary 3.5.

If $t\geq 3$ is odd and $r\geq 2$ with $t>r$, then for all $n\geq 2t-1$, we
have

$m_{0}(n,r,t)\geq\frac{t+1}{2}.$

###### Proof.

Since $r\geq 2$, we know that $2^{r}>r+1$. Let $m\leq\frac{t-1}{2}$ be an
integer. Applying Lemma 3.4 with $a=t-1,b=2$, and $c=r$, we obtain the
following

$(r+1){{m}\choose{r}}<2^{r}{{m}\choose{r}}\leq
2^{r}{{\frac{t-1}{2}}\choose{r}}<{{t-1}\choose{r}}.$

Thus

$\mathcal{D}(m)=(r+1){{m}\choose{r}}-{{t-1}\choose{r}}<0.$

This means that $\operatorname{sat}_{S_{r}}(n,S_{t})$ is not attained by
$\operatorname{KR}_{t,n}(m)$, and $m_{0}(n,r,t)>\frac{t-1}{2}$. ∎

######  Corollary 3.6.

If $t\geq 3$ is odd and $r\geq 2$ with $t>r$, then for all $n\geq 2t-1$, we
have

$m_{0}(n,r,t)>\frac{t-1}{(r+1)^{1/r}}.$

###### Proof.

Note that

$\mathcal{D}\left(\left\lfloor\frac{t-1}{(r+1)^{1/r}}\right\rfloor\right)=(r+1){{\left\lfloor\frac{t-1}{(r+1)^{1/r}}\right\rfloor}\choose{r}}-{{t-1}\choose{r}}.$

Applying Lemma 3.4 with $a=t-1$, $b=(r+1)^{1/r}$, and $c=r$, we see that this
quantity is strictly less than $0$. Since $\frac{t-1}{(r+1)^{1/r}}$ is not an
integer for all $r\geq 2$, it must be the case that
$m_{0}(n,r,t)>\frac{t-1}{(r+1)^{1/r}}$. ∎

When $r=2$, finding $m_{0}(n,r,t)$ amounts to solving a quadratic equation and
applying Theorem 3.3. The following is thus immediate.

######  Proposition 3.7.

For all $t\geq 3$ and $n\geq 2t-1$, the value of $\overline{x}$ as in Theorem
3.3 for $r=2$ is given by

$\overline{x}=\frac{1}{2}+\frac{1}{6}\sqrt{12t^{2}-36t+33}.$

We can say a little more when $r=2$.

######  Proposition 3.8.

There are two optimal choices for $m$ that simultaneously minimize the number
of copies of $S_{2}$ among $S_{t}$-saturated graphs if and only if $t$ is
given by the following where $i\geq 0$ is some non-negative integer

$t(i)=\frac{1}{4}\left((1+\sqrt{3})(2+\sqrt{3})^{i}-(\sqrt{3}-1)(2-\sqrt{3})^{i}-2\right)+2.$

###### Proof.

By Theorem 3.3 and Proposition 3.7, there are two optimal choices for $m$
precisely when $m=\frac{1}{2}+\frac{1}{6}\sqrt{12t^{2}-36t+33}$ is an integer.
This is the case when we can write $\sqrt{12t^{2}-36t+33}$ in the form $6k+3$
where $k$ is an integer. Equivalently, we need $(t-1)(t-2)=3(k+1)k$. Now, the
second member of the Diophantine pair $(x,y)$ that satisfies
$3(x^{2}+x)=y^{2}+y$ is given by $y=a(i)$ where $a(i)$ satisfies the
recurrence (see OEIS sequence A001571 [16])

$a(i)=4a(i-1)-a(i-2)+1\text{ with }a(0)=0\text{ and }a(1)=2.$

Solving the linear recurrence, we find that

$a(i)=\frac{1}{4}\left((1+\sqrt{3})(2+\sqrt{3})^{i}-(\sqrt{3}-1)(2-\sqrt{3})^{i}-2\right).$

Thus the values of $t$ for which there are two optimal choices of $m$ are
given by $t(i)=a(i)+2$. ∎

###  3.2 Asymptotic results for stars in star-saturated graphs

In addition to general questions regarding the number of stars in star-
saturated graphs, we can address asymptotic questions. Here we focus on the
case where $t$ is odd and $n\geq 2t-1$ for convenience. Utilizing our general
results from the previous section, we immediately proceed to our asymptotic
results.

######  Theorem 3.9.

Let $r=o(\sqrt{t})$ with $t$ odd and $r\geq 2$. Then for all $n\geq 2t-1$, we
have

$m_{0}(n,r,t)=(1+o_{t}(1))\frac{t-1}{(r+1)^{1/r}}.$

###### Proof.

As in Theorem 3.3, we need to solve for the value of $x$ such that

$(r+1){{x}\choose{r}}={{t-1}\choose{r}}.$ (3)

Let $\overline{x}$ be the unique solution. By Corollary 3.5, we know that
$\overline{x}\geq\lfloor t/2\rfloor$ and so $\overline{x}=\Theta(t)$. It is
well known that when $k=o(\sqrt{n})$,

${{n}\choose{k}}=(1+o_{n}(1))\frac{n^{k}}{k!}.$

Since $r=o(\sqrt{t})$, $\overline{x}=\Theta(t)$, and $n\geq 2t-1$, we can
apply this to our equality and obtain the following.

$\displaystyle(r+1)(1+o_{\overline{x}}(1))\overline{x}^{r}$
$\displaystyle=(1+o_{t}(1))(t-1)^{r}.$ Thus, since $\overline{x}=\Theta(t)$,
$\displaystyle\overline{x}$
$\displaystyle=(1+o_{t}(1))\frac{t-1}{(r+1)^{1/r}}.$

Applying Theorem 3.3 gives us the desired result. ∎

With slightly less precision than our previous theorem, we consider the more
general case where $r=o(t)$. Before stating our theorem, we note the following
useful result. A short proof can be found in [5]. See also [14].

######  Lemma 3.10.

If $k=o(n)$, then $\log{{n}\choose{k}}=(1+o_{n}(1))k\log\frac{n}{k}$.

######  Theorem 3.11.

Let $r=o(t)$ with $t$ odd and $r\geq 2$. Then for all $n\geq 2t-1$, we have
that

$m_{0}(n,r,t)=\left(\frac{t-1}{(r+1)^{1/r}}\right)^{1+o_{t}(1)}.$

###### Proof.

Let $\overline{x}$ be the unique solution to (3). By Corollary 3.5,
$\overline{x}\geq\lfloor t/2\rfloor$ and so $\overline{x}=\Theta(t)$. We now
take the logarithm of both sides in our equality, and we observe the
following.

$\displaystyle\log\left((r+1){{\overline{x}}\choose{r}}\right)$
$\displaystyle=\log{{t-1}\choose{r}},\text{ so}$
$\displaystyle\log(r+1)+\log{{\overline{x}}\choose{r}}$
$\displaystyle=\log{{t-1}\choose{r}}$ By Lemma 3.10,
$\displaystyle\log(r+1)+(1+o_{\overline{x}}(1))r\log\left(\frac{\overline{x}}{r}\right)$
$\displaystyle=(1+o_{t}(1))r\log\left(\frac{t-1}{r}\right)$

Solving for $\overline{x}$ in this equation and using the fact that
$\overline{x}=\Theta(t)$, we get

$\overline{x}=\left(\frac{t-1}{(r+1)^{1/r}}\right)^{1+o_{t}(1)}.$

By Theorem 3.3, $m_{0}(n,r,t)=\lceil\overline{x}\rceil$, and the result
follows. ∎

##  4 Stars in clique-saturated graphs

Having considered the minimum number of cliques of a given size in star-
saturated graphs and counting stars in star-saturated graphs, we move to
counting stars in clique-saturated graphs. Clique-saturated graphs have been
of interest since the proof of Turán’s Theorem, which established the maximum
number of edges among clique-saturated graphs. Theorem 1.1 gives the minimum
number of edges among clique-saturated graphs. This gives us the exact value
of $\operatorname{sat}_{S_{1}}(n,K_{t})$ since $S_{1}$ is simply an edge. The
split graph $K_{t-2}+\overline{K}_{n-t+2}$ satisfies the edge count for
Theorem 1.1. For $n$ sufficiently large, Chakraborti and Loh [4] showed that
this graph is the unique $K_{t}$-saturated graph minimizing the number of
copies of $K_{r}$ for all $r<t$, as well as the number of copies of $C_{r}$.

However, it turns out that the split graph is far from optimal when we want to
minimize stars $S_{r}$ for $r\geq 3$. Using a construction of Alon, Erdős,
Holzman, and Krivelevich [1] involving a truncated projective plane for their
upper bound, Ergemlidze, Methuku, Tait, and Timmons [7] proved the following.

######  Theorem 4.1 (Ergemlidze et al., 2021).

For integers $n\geq t\geq 3$ and $r\geq 3$,

$\operatorname{sat}_{S_{r}}(n,K_{t})=\Theta(n^{r/2+1})$

An important detail about the construction from Alon, Erdős, Holzman, and
Krivelevich is that the resulting graph has maximum degree
$\Delta=\Theta(\sqrt{n})$. Since vertices of large degree contain many stars,
it makes sense that the optimal choice is for the graph to have as small of
degree as possible. Furthermore, Alon et al. showed that the maximum degree of
a $K_{t}$-saturated graph on $n$ vertices is $\Omega(\sqrt{n})$ [1].

In addition to the split graph not minimizing stars among all
$K_{t}$-saturated graphs, it is still not optimal for minimizing stars when
considering families of $K_{t}$-saturated graphs with linear maximum degree.
The following graph will be the starting point for our construction.

ABCDEFGHI Figure 3: $K_{4}$-saturated graph $G_{4,9}$ on $9$ vertices

######  Proposition 4.2.

Let $t\geq 4$ and $r\geq 3$. There exists a sequence $(G_{t,n})$ of
$K_{t}$-saturated graphs on $n$ vertices with $\Delta(G_{t,n})=\Theta(n)$ and
a constant $n_{r,t}$ such that
$s_{r}(G_{t,n})<s_{r}(K_{t-2}+\overline{K}_{n-t+2})$ for all $n\geq n_{r,t}$.

###### Proof.

Consider the graph $G_{4,9}$ in Figure 3. We obtain $G_{4,n}$ for $n>9$ by
blowing up vertices $A,C,E$ into independent sets of size as equal as
possible. For $t>4$, we define $G_{t,n}$ to be $G_{4,n-t+4}+K_{t-4}$. Since
$G_{4,n-t+4}$ is $K_{4}$-saturated, joining $t-4$ universal vertices results
in a $K_{t}$-saturated graph. Given $r$ and $t$, we can find a constant
$n_{r,t}$ such that $s_{r}(G_{t,n})<s_{r}(K_{t-2}+\overline{K}_{n-t+2})$ for
all $n\geq n_{r,t}$. ∎

Although we omit the computations from the previous proof, we note that the
key to the construction is that $\Delta(G_{t,n})$ is roughly $\frac{2}{3}n$
for large $n$, and $\Delta(K_{t-2}+\overline{K}_{n-t+2})=n-1$.

##  5 Paths and cliques

In addition to stars and cliques, we are interested in the broader topic of
saturation involving trees and cliques. In the next section we will say a few
things about arbitrary trees, but here we will turn to another basic class of
trees, namely paths. Let $P_{r+1}$ denote a path on $r+1$ vertices. We begin
this discussion by stating the following result of Kritschgau, Methuku, Tait,
and Timmons [12] concerning cycles.

######  Proposition 5.1 (Kritschgau et al., 2020).

For $t\geq 5$ and $r\leq 2t-4$,

$\operatorname{sat}_{C_{r}}(n,K_{t})=\Theta(n^{\lfloor r/2\rfloor}).$

The case where $t=4$ was accounted for in their result on cliques in clique-
saturated graphs. By refining their proof slightly and with a similar argument
used by Chakraborti and Loh [4], we prove the following regarding the order of
$n$ when counting paths in clique-saturated graphs.

######  Theorem 5.2.

For $t\geq 4$ and $r\leq 2t-3$,

$\operatorname{sat}_{P_{r+1}}(n,K_{t})=\Theta(n^{\left\lceil\frac{r+1}{2}\right\rceil}).$

If $r\geq 2t-2$, the split graph is $P_{r+1}$-free.

###### Proof.

By considering the split graph $K_{t-2}+\overline{K}_{n-t+2}$, we can
construct a path on $r+1$ vertices by using at most
$k=\lceil\frac{r+1}{2}\rceil$ vertices from the independent set. The remaining
vertices must come from the clique of order $t-2$. Thus the number of copies
of $P_{r+1}$ in $G$ is

$\frac{1}{2}{{n-t+2}\choose{k}}(t-2)_{k}k!+o(n^{k}).$

The $o(n^{k})$ term accounts for any paths using fewer than $k$ elements in
the independent set. This gives us the appropriate upper bound.

For the lower bound, let $G$ be $K_{t}$-saturated, and let $I$ be an
independent set of order $k=\lceil\frac{r+1}{2}\rceil$ in $G$. There are $k!$
ways to order the elements of $I$. Enumerate the elements
$v_{1},v_{2},\dots,v_{k}$. For each ordering we will give a lower bound on the
number of copies of $P_{r+1}$ containing it. For all $1\leq i\leq k-1$, let
$V_{i}$ be a set of vertices such that $V_{i}\subseteq N(v_{i})\cap
N(v_{i+1})$ and the subgraph induced by $V_{i}$ is a copy of $K_{t-2}$. Such
copies exist since $v_{i},v_{i+1}\in I$ which is an independent set, and $G$
is $K_{t}$-saturated. Since each $V_{i}$ has $t-2$ elements, we can pick
distinct $u_{i}\in V_{i}$ such that $v_{1}u_{1}v_{2}\cdots
v_{k-1}u_{k-1}v_{k}$ is a path in $G$. This gives us at least
$\frac{1}{2}k!(t-2)_{k}$ copies of $P_{r+1}$ involving every element of $I$.
The factor of $\frac{1}{2}$ accounts for the double-counting of paths being
read from left-to-right and right-to-left. Chakraborti and Loh showed in [4]
that any $K_{t}$-saturated graph contains $\Theta(n^{k})$ independent sets of
order $k$ for any given $k$. This gives us the corresponding lower bound, and
we have that $\operatorname{sat}_{P_{r+1}}(n,K_{t})=\Theta(n^{k})$ as desired.

For the second statement in the theorem, we note that when $r\geq 2t-2$, a
copy of $P_{r+1}$ in $K_{t-2}+\overline{K}_{n-t+2}$ must use at least
$\lfloor\frac{r+1}{2}\rfloor$ vertices from the clique $K_{t-2}$. Thus

$2t-2=2(t-2)+2\geq 2\left\lfloor\frac{r+1}{2}\right\rfloor+2>r,$

a contradiction. Therefore $K_{t-2}+\overline{K}_{n-t+2}$ is $P_{r+1}$-free. ∎

Chakraborti and Loh [4] showed that for $n$ sufficiently large in terms of $r$
and $t$, the split graph minimizes the number of copies of $C_{r}$ in
$K_{t}$-saturated graphs. This leads us to the following question.

######  Question 5.3.

For $n$ sufficiently large, is the number of copies of $P_{r+1}$ in
$K_{t}$-saturated graphs is minimized by $K_{t-2}+\overline{K}_{n-t+2}$?

Shifting perspectives, we now briefly consider path-saturated graphs. Kaszonyi
and Tuza provided a construction in [13] for trees which are
$P_{t+1}$-saturated for all $t\geq 3$. Furthermore, they characterized all
trees which are $P_{t+1}$-saturated for $t\geq 4$. The existence of such
graphs, which are of course $K_{3}$-free, solves the asymptotic question for
minimizing cliques in path-saturated graphs immediately. The lower bound on
$n$ comes from [13].

######  Proposition 5.4.

If $t\geq 3$ is odd, then $\operatorname{sat}_{K_{r}}(n,P_{t+1})=0$ for all
$n\geq 3\cdot 2^{\frac{t+1}{2}-1}-2$ and all $r\geq 3$. If $t\geq 4$ is even,
then $\operatorname{sat}_{K_{r}}(n,P_{t+1})=0$ for all $n\geq
2^{\frac{t}{2}+1}-2$ and all $r\geq 3$.

##  6 More general cases

Counting paths and stars in clique-saturated graphs, as well as the reverse,
is part of the larger question of counting trees in clique-saturated graphs
and counting cliques in tree-saturated graphs. Some results for the
traditional saturation problem on trees were proved by Kaszonyi and Tuza [13].
Many additional results on this subject are due to Faudree, Faudree, Gold, and
Jacobson [8]. Here we prove some initial results regarding the generalized
saturation problem for trees and cliques. We let $n_{T}(G)$ denote the number
of copies of a tree $T$ in $G$.

######  Proposition 6.1.

Let $G$ be a $K_{t}$-saturated graph with minimum degree $\delta$, and let
$r\leq 2t-4$. Then for any tree $T$ on $r$ vertices with minimum degree
$\delta$, the following hold

$\displaystyle n_{T}(G)$ $\displaystyle>0\text{ if }\delta=t-2$ (4)
$\displaystyle n_{T}(G)$ $\displaystyle>0\text{ if }\delta=t-1$ (5)
$\displaystyle n_{T}(G)$ $\displaystyle>0\text{ if }\delta\geq 2t-5.$ (6)

###### Proof.

Our aim is to show that for any given $T$ and $K_{t}$-saturated graph $G$,
these minimum degree restrictions guarantee at least one copy of $T$ in $G$.
Kritschgau et al. [12] demonstrated the exact structure of $K_{t}$-saturated
graphs with minimum degree $t-2$ and $t-1$. In particular, when $\delta=t-2$,
$G$ is the split graph $K_{t-2}+\overline{K}_{n-t+2}$. When $\delta=t-1$, $G$
is isomorphic to $(K_{t-1}-e)+\overline{K}_{n-t+1}$ or
$W_{t}(m_{1},1,m_{3},m_{4},1)$ for some $m_{1}+m_{3}+m_{4}=n-t+1$. Here $e$ is
any edge in $K_{t-1}$, and $W_{t}(m_{1},m_{2},m_{3},m_{4},m_{5})$ is the graph
obtained by taking a wheel with five vertices on the outer cycle and replacing
the central vertex with a clique of size $t-3$ and each vertex $v_{i}$ of the
outer cycle with an independent set of size $m_{i}$. Two vertices are adjacent
in $W_{t}(m_{1},m_{2},m_{3},m_{4},m_{5})$ if and only if they replaced
adjacent vertices in the original wheel. We now note that for the above
mentioned graphs, we can utilize the large clique to help find any tree $T$ on
$t$ vertices. For the final case, we note the well known result that if a
graph has minimum degree $\delta$, then it must contain any tree on $\delta+1$
vertices. ∎

Mimicking a technique of Kaszonyi and Tuza, we provide a lower bound on $r$
for which $\operatorname{sat}_{K_{r}}(n,F)=0$ for a $t$-vertex graph $F$ in
terms of its independence number. To this end, let $u(F)=t-\alpha(F)-1$ where
$\alpha$ is the independence number of $F$. Let $d$ be the minimum number of
edges in a subgraph of $G$ induced by an independent set $S$ of size $\alpha$
and one other vertex $v$. Note that the graph induced by $v$ and $S$ is the
star $S_{d}$ and some number of isolated vertices. It is trivially true that
an $F$-saturated graph can not contain any copy of $K_{t}$ since $F$ has $t$
vertices. The following proposition shows that we can find $F$-saturated
graphs whose largest cliques are smaller. Before proving our result, we state
a key lemma of Kaszonyi and Tuza [13].

######  Lemma 6.2 (Kaszonyi and Tuza, 1986).

Let $\mathcal{F}^{\prime}=\\{F_{i}\setminus\\{x\\}:x\in
V(F_{i}),F_{i}\in\mathcal{F}\\}$ and suppose that some vertex $x\in V(G)$ has
degree $d(x)=n-1$. Then $G$ is $\mathcal{F}$-saturated if and only if
$G\setminus\\{x\\}$ is $\mathcal{F}^{\prime}$-saturated.

Here we say that a graph $G$ is $\mathcal{F}$-saturated for a family
$\mathcal{F}$ of forbidden subgraphs $F_{1},\dots,F_{k}$ if $G$ contains no
$F_{i}$ but the addition of any missing edge creates at least one copy of some
$F_{i}$.

######  Proposition 6.3.

Let $F$ be a graph on $t$ vertices. Then for $n$ sufficiently large,
$\operatorname{sat}_{K_{r}}(n,F)=0$ for all $r\geq t-\alpha+d$.

###### Proof.

Let $u$ be as defined above. Suppose $G$ is $F$-saturated with $u$ vertices of
degree $n-1$. Pick $u$ such vertices and remove them one by one. Setting
$\mathcal{F}=\\{F\\}$, we have that $G$ is $\mathcal{F}$-saturated. After
repeated application of Lemma 6.2, we obtain a graph $G^{\prime}$ that is
$\mathcal{F^{\prime}}$-saturated where $S_{d}\in\mathcal{F^{\prime}}$. Thus
the maximum degree of $G^{\prime}$ is $d-1$ and $\omega(G^{\prime})\leq d$
where $\omega$ is the clique number of $G$. Hence the largest clique in $G$
has size at most $t-\alpha+d-1$, and the proof is complete. ∎

Based on the results above for stars and paths, along with the fact that among
all trees $T$, the star $S_{t}$ has the largest saturation number [13], one
may suspect that for any tree $T$ there exist triangle-free graphs on $n$
vertices for $n$ sufficiently large that are $T$-saturated. We note that this
is true for any tree $T$ on $t\leq 6$ vertices. However, the following example
$T^{*}$ shows that this does not hold for all trees.

Figure 4: $T^{*}$

######  Proposition 6.4.

There does not exist a $K_{3}$-free graph that is $T^{*}$-saturated.

###### Proof.

Suppose $G$ is a $T^{*}$-saturated graph that is $K_{3}$-free; clearly
$n=n(G)\geq 7$. Since $G$ is $K_{3}$-free, the neighborhood of any vertex must
be an independent set. If $G$ has a vertex of degree $2$, then adding the
missing edge between its neighbors must create a copy of $T^{*}$. In
particular, this copy must use the added edge. There are two cases. Either the
added edge is incident to the degree $3$ vertex in $T^{*}$, or it is incident
to a degree $1$ vertex in the created copy of $T^{*}$. In either case, we can
replace the added edge with one of the original edges, contradicting the fact
that $G$ is $T^{*}$-free. Thus $G$ has no vertex of degree $2$.

Now, the maximum degree of $G$ must be at least $3$. Otherwise our graph is a
matching along with some isolated vertices, but such a graph is not
$T^{*}$-saturated. We will only focus on a component containing a vertex of
degree at least $3$ as any edge added within that component must create
$T^{*}$. Let $x$ be a vertex of degree at least $3$. If $x$ has three
neighbors $a,b,c$ of degree at least $3$, then their neighborhoods must be
precisely $x$ and two other common vertices. Otherwise $G$ already contains
$T^{*}$. There must be another vertex $u$ in this component of $G$ because it
has missing edges and not enough vertices to create a copy of $T^{*}$. A quick
check shows that no matter which vertex we join $u$ to, we must already have a
copy of $T^{*}$, contradicting the condition that $G$ is $T^{*}$-saturated.

We also note that if $x$ has a unique neighbor of degree at least $3$, then
adding an edge between two of its neighbors of degree $1$ will not create a
copy of $T^{*}$. Therefore every vertex of degree at least $3$ is adjacent to
at least one vertex of degree $1$ and exactly two vertices of degree at least
$3$. Therefore $G$ is isomorphic to a cycle whose vertices each have at least
one pendant. However, these graphs are not $T^{*}$-saturated. This can be seen
by adding an edge between a vertex on the cycle and a pendant of a neighboring
vertex as in Figure 5. This contradicts the only remaining case. Therefore no
such graph $G$ exists. ∎

Figure 5: Example of a cycle with pendants. The dotted edge does not induce
$T^{*}$ when added.

##  7 Concluding remarks

It is still unknown what the value of $\operatorname{sat}_{S_{2}}(n,K_{3})$
is. Ergemlidze, Methuku, Tait, and Timmons show in [7] that the split graph is
not always optimal for this problem and remark that there is a connection to
Moore graphs with diameter $2$ and girth $5$. It would be interesting to know
what the exact value of the generalized saturation number is in this specific
case.

It would also be interesting to more closely study
$\operatorname{sat}_{S_{r}}(n,S_{t})$ when $t$ is even and when $t+1\leq n\leq
2t-1$. There is less control over the structure of $S_{t}$-saturated graphs in
this setting and more care is required. We are also interested in refining our
bounds on $n$ for the existence of $S_{t}$-saturated graphs that are
$K_{r+1}$-free.

## References

  * [1] N. Alon, P. Erdős, R. Holzman, and M. Krivelevich, On $k$‐saturated graphs with restrictions on the degrees, J. Graph Theory 23 (1996), 1-20.
  * [2] N. Alon and C. Shikhelman, Many $T$ copies in $H$-free graphs, J. Combinatorial Theory, Series B 121 (2016), 146–172.
  * [3] B. Bollobás, Modern Graph Theory, Springer, New York (1998).
  * [4] D. Chakraborti and P. Loh, Minimizing the numbers of cliques and cycles of fixed size in an $F$-saturated graph, European J. Combinatorics, Vol. 90 (2020).
  * [5] S. Das, A brief note on estimates of binomial coefficients. http://page.mi.fu-berlin.de/shagnik/notes/binomials.pdf.
  * [6] P. Erdős, A. Hajnal, and J. W. Moon, A problem in graph theory, Amer. Math. Monthly 71 (1964), 1107-1110.
  * [7] B. Ergemlidze, A. Methuku, M. Tait, and C. Timmons, Minimizing the number of complete bipartite graphs in a $K_{s}$-saturated graph, arXiv:2101.00507, 2021.
  * [8] J.R. Faudree, R.J. Faudree, R.J. Gould, and M.S. Jacobson, Saturation numbers for trees, Electronic J. Combin. 16 (2009), #R91.
  * [9] J.R. Faudree, R.J. Faudree, and J. Schmitt, A survey of minimum saturated graphs, Electronic J. Combin. 18 (2011), #DS19.
  * [10] J. Gallian, A dynamic survey of graph labeling, Electronic J. Combin. 1 (2018), #DS6.
  * [11] D.G. Hoffman and C.A. Rodger, The chromatic index of complete multipartite graphs, _J. Graph Theory_ 16 (1992), 159-163.
  * [12] J. Kritschgau, A. Methuku, M. Tait, and C. Timmons, Few $H$ copies in $F$-saturated graphs, _J. Graph Theory_ 94 (2020), 320-348.
  * [13] L. Kaszonyi and Zs. Tuza, Saturated graphs with minimal number of edges, _J. Graph Theory_ 10 (1986), 203-210.
  * [14] D. Mackay, Information Theory, Inference, and Learning Algorithms, Cambridge University Press (2003), 2.
  * [15] R.R. Martin and J.J. Smith, Induced Saturation Number, Discrete Mathematics 312 (21) (2012), 3096-3106.
  * [16] OEIS Foundation Inc. (2021), The On-Line Encyclopedia of Integer Sequences, http://oeis.org/A001571.
  * [17] A. Sidorenko, What we know and what we do not know about Turán numbers, _Graphs and Combinatorics_ 11 (1995), 179-199.
  * [18] P. Turán, On an extremal problem in graph theory, _Matematikai és Fizikai Lapok_ , 48 (1941), 436–452.