# Singular Perturbation-based Reinforcement Learning of Two-Point Boundary
Optimal Control Systems

Vasanth Reddy, Hoda Eldardiry and Almuatazbellah Boker Vasanth Reddy and Hoda
Eldardiry are with Department of Computer Science, Virginia Tech, Blacksburg,
VA, USA. emails<EMAIL_ADDRESS>and<EMAIL_ADDRESS>Boker is
with Bradley Department of Electrical and Computer Engineering, Virginia Tech,
Blacksburg, VA, USA. email<EMAIL_ADDRESS>
###### Abstract

This work presents a technique for learning systems, where the learning
process is guided by knowledge of the physics of the system. In particular, we
solve the problem of the two-point boundary optimal control problem of linear
time-varying systems with unknown model dynamics using reinforcement learning.
Borrowing techniques from singular perturbation theory, we transform the time-
varying optimal control problem into a couple of time-invariant subproblems.
This allows the utilization of an off-policy iteration method to learn the
controller gains. We show that the performance of the learning-based
controller approximates that of the model-based optimal controller and the
accuracy of the approximation improves as the time horizon of the control
problem increases. Finally, we provide a simulation example to verify the
results of the paper.

###### Index Terms:

optimal control; singular perturbation; reinforcement learning

##  I INTRODUCTION

Control and analysis of time varying (dynamic) systems has been extensively
investigated over the last decade. Applications such as rocket landing [1, 2],
energy conservation in electronic circuits [3, 4] can be categorized as
finite-horizon time-varying systems. Solving this category of problems
requires solving the time varying Riccati equation for linear time-variant
systems or time-varying Hamiltonaian Jacobi equation for nonlinear systems.
Solving time-variant equation is bit complicated and tough to solve than
compared to the time-invariant equations. The work in [5] illustrates that the
two value boundary problems exhibits two-time scale phenomenon even if the
original system is not singularly perturbed. In this case, the work [5] shows
that it is possible to approximate the original time-varying system into two
time-invariant systems. One is initial boundary problem which stabilizes the
original system in forward time and the other is the final boundary system
which stabilized the terminal layer in reverse time. As the perturbation
parameter, which is related to the time-horizon of the control problem,
decreases the accuracy of the approximation increases. A number of research
papers have shown the use of the above approximation in nonlinear, fixed end
point control problems [6], nonlinear problems with singular arcs [7] and in
optimal control of quasi linear systems [8]. In the recent times, this
approximation is well used to study the turnpike properties in wave equations
[9] and in semi-linear control [10].

The approximation solution for the two value boundary is provided assuming
that the dynamics of the model is known. However, in the real time
applications the dynamics of model may not be known, or suffer from modeling
uncertainties, and in that case it is difficult to solve the initial and final
boundary problems. In the past, the research work [11] introduced adaptive
controls laws through which we can learn the control of the model from the
input-output data. In the recent years the gain in momentum of Reinforcement
Learning [12] have opened up the different possibilities of learning the
controller. Adaptive Dynamic Programming is one of the first learning
techniques in Reinforcement Learning. It uses an iteration method proposed in
previous work [13] with a change in variables to find the optimal control
gain. Learning methods such as Q-learning [14], Actor-Critic [15] have been
effective in learning the controller for continuous time systems when the
model dynamics are unknown.

The main aim of this paper is to learn the controller for the finite horizon
time varying system when boundary conditions are given. In the past, research
work has been carried out in learning the optimal control when the system
dynamics are unknown using adaptive dynamic programming [13], actor-critic
[15] and Q-learning [14] but they assume that the system is time invariant.
Extending this work to the time varying systems, later work [16] proposed an
data-driven approach and other work [17, 18] used policy iteration method to
find the controllers but they are restricted to only discrete time-varying
systems. Previous work [20] investigated continuous time periodic systems
which is an important applications of the time-varying systems. It used
adaptive programming to learn the controller and off-policy value iteration
[21] but considered the infinite horizon without any boundary conditions.
Limited work has been done and proportionately less results are available for
finite horizon time varying systems. More recent work [22] proposed dual loop
iterative algorithm but they considered the fact that the state transition
matrix is unknown.

In order to address the above problems we adopt the idea of solving the finite
horizon time varying problems with given boundary conditions from seminal work
[26]. The idea is: When the time period in which the cost function needs to be
optimized is large, the time-varying system exhibits the two-time scale
property, where the system dynamics evolve at faster time scale relative to
the time-scale of the control effort. Then [26] shows that the system can be
reduced into two time-invariant problems. The final original state thus can be
approximated by superimposing the solutions of initial and final layer
problems. We further use the idea of offline learning [23] to estimate the
control gain of two boundary problems. Thus we reduce the complexity of
original system into two simple problems and then learning the two individual
controllers. We empirically show that the controller learned from two
individual is nearly approximate to that of the original controller. We also
show that the accuracy of the state and controller increases as the time
interval to optimize the cost function increases. We demonstrate the above
point by taking up a linear time-variant system example.

In summary, the key contributions of our proposed model are twofold:

  1. 1.

We provide a solution for the two-boundary optimal control problem for linear
time-varying systems that does not require knowledge of system model.

  2. 2.

We introduce a reinforcement learning framework that is based on an insight
from the physical dynamics. This framework is simple to implement and results
in a suboptimal solution, which converges to the optimal one as the control
time interval gets large.

The rest of this paper is organized as follows. Section II illustrates the
system setup and problem formulation. Section III describes the two-time scale
reduction of original problem. Section IV outlines the learning algorithm to
estimate the control gains of the system. Section V presents the numerical
example and illustrates the simulations.

##  II Problem Formulation

Consider the linear time-varying system expressed by the differential
equation:

$\frac{dx}{dt}=A(t)x(t)+B(t)u(t)$ (1)

where $x(t)\in\mathbb{R}^{n}$, $u(t)\in\mathbb{R}^{m}$,
$A(t)\in\mathbb{R}^{n\times n}$ and $B(t)\in\mathbb{R}^{n\times m}$ are the
system states, control input, state matrix and input matrix, respectively. The
matrices $A(t)$ and $B(t)$ are smooth functions of time $\forall\;t\in[0,T]$
and can be unknown. The control objective is to design $u(t)\in\mathbb{R}^{m}$
to drive the system states $x(t)$ from the initial state $x(0)=x_{0}$ to the
final state $x(T)=x_{T}$ within a time period $T$ and meanwhile minimize the
objective function

$J=\int_{0}^{T}x^{\top}(t)Q(t)x(t)+u^{\top}(t)R(t)u(t)\hskip 5.69054ptdt$ (2)

where, $Q(t)=Q^{\top}(t)\succeq 0$ and $R(t)\succ 0\;\;\forall\;t\in[0,T].$
The matrices $Q(t)$ and $R(t$) are assumed to be smooth functions of time. We
further have the following assumptions:

######  Assumption 1.

The pair $(A(t),B(t))\;\;\forall\;t\in[0,T]$ is controllable and the pair
$(A(t),\sqrt{Q(t}))\;\;\forall\;t\in[0,T]$ is observable.

######  Assumption 2.

The time $T$ needed to accomplish the control objective is long compared to
the system dynamics.

Assumption 1 is a standard assumption according to the theory of optimal
control [28]. Assumption 2 implies that the system is slowly varying relative
to the control objective. This will be explained further in the next section.

To solve the optimal control problem, we define the Hamiltonaian function for
the system (1) as [28]:

$\mathcal{H}=x^{\top}(t)Q(t)x(t)+u^{\top}(t)R(t)u(t)+\\\
p^{\top}(t)(A(t)x(t)+B(t)u(t))$ (3)

where, $p(t)\in\mathbb{R}^{n}$ is the co-state equation that satisfies:

$\dot{p}(t)=-\nabla_{x}\mathcal{H}=-Q(t)x(t)-A^{\top}(t)p(t).$ (4)

The control law $u(t)$ for the dynamic system (1) that minimizes the objective
function (2) is given by $\nabla_{u}\mathcal{H}=0$:

$u(t)=-R\raisebox{4.95134pt}{$\scriptscriptstyle-\\!1$}(t)B^{\top}(t)p(t).$
(5)

Our objective is to learn the optimal controller $u(t)$ given by (5) for the
system (1) without the need to know the system matrices $A(t)$ and $B(t)$.

##  III Singular Perturbation-based Design

It is known that for control problems that are formulated over a finite time
interval $t\in[0,T]$, the closed-loop system dynamics behave in two time
scales [29]. The separation of time scales is dependent on the length of the
time interval $T$. In this work, we leverage this phenomenon by considering
the case when the time needed to transfer the system state from one instant to
another is small compared with $T$. This allows the system to be modeled in a
singularly perturbed form. Accordingly, previous work [29] has shown that it
is possible to achieve a sub-optimal solution to the control problem when $T$
is sufficiently long and matrices $A(t)$ and $B(t)$ are known. In the next
sections, we show that it is possible to achieve a similar result without
requiring the system matrices to be known thanks to employing a reinforcement
learning algorithm. Towards this goal, we start by setting up the singular
perturbation model of the system. Normalizing the time period $0$ to $T$ to
the interval $[0,1]$ by introducing the scaled time

$\tau=\frac{t}{T}$ (6)

and defining

$\varepsilon=1/T$ (7)

and then reconstructing (1), (2), (4), and (5) to obtain

$\displaystyle\varepsilon\begin{bmatrix}\frac{dx}{d\tau}\\\
\frac{dp}{d\tau}\end{bmatrix}=$ $\displaystyle\begin{bmatrix}A(\tau)&&0\\\
-Q(\tau)&&-A^{T}(\tau)\end{bmatrix}\begin{bmatrix}x\\\
p\end{bmatrix}+\begin{bmatrix}B(\tau)\\\ 0\end{bmatrix}u,$ (8) $\displaystyle
J=$ $\displaystyle
T*\int_{0}^{1}x^{\top}(\tau)Q(\tau)x(t)+u^{\top}(\tau)R(\tau)u(\tau)\hskip
5.69054ptdt,$ (9) $\displaystyle u(\tau)=$
$\displaystyle-R\raisebox{4.95134pt}{$\scriptscriptstyle-\\!1$}(\tau)B^{\top}(\tau)p(\tau),$
(10)

where $x(0)=x_{0}$ and $x(1)=x_{T}$. For the system described by (8) to be in
standard singular perturbation form, we make the following assumption:

######  Assumption 3.

The eigenvalues of the Hamiltonian matrix

$M_{H}\triangleq\begin{bmatrix}A(\tau)&&-B(\tau)R^{-1}(\tau)B^{\top}(\tau)\\\
-Q(\tau)&&-A^{\top}(\tau)\end{bmatrix}$ (11)

lie off the imaginary axis $\forall\;t\in[0,1]$.

This assumption implies that $M_{H}$, which is the closed-loop matrix after
substituting (10) in (8), is nonsingular $\forall\;t\in[0,1]$.

We are going next to decouple the dynamics of (8). To accomplish this task, we
use the transformation [29]

$\left[\begin{array}[]{l}x\\\
p\end{array}\right]=\left[\begin{array}[]{cc}I&I\\\
P_{a}(\tau,\varepsilon)&P_{b}(\tau,\varepsilon)\end{array}\right]\left[\begin{array}[]{l}x_{a}\\\
x_{b}\end{array}\right].$ (12)

It is shown in [Lemma 2.3, [29]] that, under the assumptions of this paper,
the transformation (12) is nonsingular for sufficiently small $\varepsilon.$
Accordingly, using (12), system (8) with (10) can be transformed into

$\displaystyle\varepsilon\frac{d}{d\tau}x_{a}=$ $\displaystyle
A(\tau)x_{a}+B(\tau)u_{a}(\tau),$ (13)
$\displaystyle\varepsilon\frac{d}{d\tau}x_{b}=$ $\displaystyle
A(\tau)x_{b}+B(\tau)u_{b}(\tau),$ (14)

where

$\displaystyle u_{a}=$
$\displaystyle-R\raisebox{4.95134pt}{$\scriptscriptstyle-\\!1$}(\tau)B^{\top}(\tau)P_{a}(\tau,\varepsilon),$
(15) $\displaystyle u_{b}=$
$\displaystyle-R\raisebox{4.95134pt}{$\scriptscriptstyle-\\!1$}(\tau)B^{\top}(\tau)P_{b}(\tau,\varepsilon),$
(16)

and $P_{a}(\tau,\varepsilon)\geq 0$ and $P_{b}(\tau,\varepsilon)\leq 0$ are
the roots of the differential Riccati equation

$\displaystyle\varepsilon\dot{P}=$ $\displaystyle-A^{\top}(\tau)P-PA(\tau)$
(17)
$\displaystyle+PB(\tau)R\raisebox{4.95134pt}{$\scriptscriptstyle-\\!1$}(\tau)B^{\top}(\tau)P-Q(\tau).$

We transform next the singular perturbation system (13)-(14) into the boundary
layer system by considering the time-scale change

$\gamma=\frac{\tau}{\varepsilon},\quad\beta=\frac{1-\tau}{\varepsilon}.$ (18)

In view of (18), the boundary layer system is obtained by setting
$\varepsilon\to 0$ in (13)-(17). This leads to the initial regulator problem

$\frac{d}{d\gamma}x_{a}=A(0)x_{a}+B(0)u_{a},$ (19)

with the feedback controller $u_{a}$ in the form

$u_{a}(\gamma)\triangleq-
K_{a}x_{a}(\gamma)=-R\raisebox{4.95134pt}{$\scriptscriptstyle-\\!1$}(0)B^{\top}(0)P_{a}(0)x_{a}(\gamma),$
(20)

which minimizes the cost function

$J(x_{a},u_{a})=\int_{0}^{\infty}x_{a}^{\top}Q(0)x_{a}+u_{a}^{\top}R(0)u_{a}\hskip
2.84526ptd\gamma,$ (21)

and the terminal regulator problem

$\frac{d}{d\beta}x_{b}=-A(1)x_{b}-B(1)u_{b},$ (22)

with the feedback controller

$u_{b}(\beta)\triangleq-
K_{b}x_{b}(\beta)=-R\raisebox{4.95134pt}{$\scriptscriptstyle-\\!1$}(1)B^{\top}(1)P_{b}(1)x_{b}(\beta),$
(23)

which minimizes the cost function

$J(x_{b},u_{b})=\int_{0}^{\infty}x_{b}^{\top}Q(1)x_{b}+u^{\top}_{b}R(1)u_{b}\hskip
2.84526ptd\beta.$ (24)

Based on this setup, we have the following theorem.

######  Theorem 1 (Theorem 2.1 in [29]).

Under Assumptions 1-3, there exists $\varepsilon^{*}>0$ such that for all
$\varepsilon\in(0,\varepsilon^{*}]$ the solution $x(\tau),p(\tau)$ of (8) and
the optimal control $u(\tau)$ satisfy

$\displaystyle x(\tau)=$ $\displaystyle
x_{a}(\gamma)+x_{b}(\beta)+\mathcal{O}(\varepsilon),$ (25) $\displaystyle
p(\tau)=$ $\displaystyle
P_{a}(0)x_{a}(\gamma)+P_{b}(1)x_{b}(\beta)+\mathcal{O}(\varepsilon),$ (26)
$\displaystyle u(\tau)=$ $\displaystyle-
K_{a}x_{a}(\gamma)-K_{b}x_{b}(\beta)+\mathcal{O}(\varepsilon).$ (27)

Theorem 1 implies that if the initial and terminal regulator problems, which
are now problems for linear time-invariant systems, are solved then the
solution will approximate that of the original control problem (1)-(5) for
sufficiently small $\varepsilon$. In the next section, we will rely on this
result and develop a reinforcement learning algorithm to solve the initial and
terminal regulator problems (19)-(24) without the need for $A(t)$ and $B(t)$
to be known.

##  IV Reinforcement Learning

In this section, we follow a reinforcement learning approach to learn the
initial and terminal regulator problems (19)-(24). In particular, we learn the
controllers using an offline policy.

######  Remark 1.

In view of Theorem 1, we use the original state $x(t)$ for the offline
learning procedure. It should be noted that, according to (6) and (18), the
time-scales $\gamma$ and $\beta$ are the forward and reverse times of $t$,
respectively.

(i) Initial Regulator problem: The objective is to learn the feedback control
gain $K_{a}\triangleq
R\raisebox{4.95134pt}{$\scriptscriptstyle-\\!1$}(0)B^{\top}(0)P_{a}(0)$ for
the system described in (19) without knowing the system dynamics. In view of
Remark (1), learning is done using the online measurement data of system
states $x$ and control $u_{a}$ such that control $u_{a}=-K_{a}x$ optimizes the
cost function described in (21). Note that $P_{a}(0)$ is the solution to the
algebraic Riccati equation:

$\displaystyle A^{\top}(0)P_{a}(0)+P_{a}(0)A(0)-P_{a}(0)B(0)$ $\displaystyle
R\raisebox{4.95134pt}{$\scriptscriptstyle-\\!1$}(0)B^{\top}(0)P_{a}(0)$ (28)
$\displaystyle+Q(0)=0.$

The optimal feedback gain is given by
$K^{*}_{a}=-R\raisebox{4.95134pt}{$\scriptscriptstyle-\\!1$}(0)B^{\top}(0)P_{a}$.
The optimal values are then found using the Kleimanns algorithm [19] as
follows.

  1. 1.

Solve for $\tilde{P}^{k}$ of the lyapunov equation

$\displaystyle A_{k}^{\top}(0)\tilde{P}_{a}^{k}+$
$\displaystyle\tilde{P}_{a}^{k}A_{k}(0)+Q(0)$ (29)
$\displaystyle+\tilde{P}^{k}_{a}B(0)R\raisebox{4.95134pt}{$\scriptscriptstyle-\\!1$}(0)B^{\top}(0)\tilde{P}^{k}_{a}=0.$

  2. 2.

Update the feedback gain:

$\tilde{K}^{k+1}_{a}=R\raisebox{4.95134pt}{$\scriptscriptstyle-\\!1$}(0)B^{\top}(0)\tilde{P}^{k}_{a},$
(30)

where $A_{k}(0)=A(0)-B(0)K^{k}_{a}$. The matrix $P_{a}(0)^{k}$ and the gain
$K_{a}^{k+1}$ can be learned iteratively following the above steps but only
when the model dynamics are known. As we assumed that the model dynamics are
unknown, we follow a few steps to eliminate the use of model dynamics $A(0)$
and $B(0)$ in learning the controller.

Initialization: Consider an arbitrary control signal $u_{0}$ to excite the
system (19). Accordingly, we define the control policy
$u_{a}=u_{0}-\tilde{K}^{k}_{a}x_{a}+\tilde{K}^{k}_{a}x_{a}$ with
$\tilde{K}^{k}_{a}>0$ and feed it back to (19) to get:

$\displaystyle\dot{x}_{a}$
$\displaystyle=A(0)x_{a}+B(0)(u_{0}-\tilde{K}^{k}_{a}x_{a}+\tilde{K}^{k}_{a}x_{a})$
(31)
$\displaystyle=(A(0)-B(0)\tilde{K}^{k}_{a})x_{a}+B(0)(u_{0}+\tilde{K}^{k}_{a}x_{a})$
$\displaystyle\dot{x}_{a}$
$\displaystyle=A_{k}(0)x_{a}+B(0)(u_{0}+\tilde{K}^{k}_{a}x_{a}).$

Towards eliminating the dependence of $A(0)$ and $B(0)$, we define the
Lyapunov function $V^{k}(x_{a})=x^{\top}_{a}\tilde{P}^{k}_{a}x_{a}$. Taking
the derivative of this function along the system (31) leads to

$\displaystyle\frac{d}{dt}(x^{\top}_{a}\tilde{P}_{a}^{k}x_{a})=$
$\displaystyle
x^{\top}_{a}(A_{k}^{\top}(0)\tilde{P}_{a}^{k}+\tilde{P}_{a}^{k}A_{k}(0))x_{a}$
(32)
$\displaystyle+2(u_{0}+\tilde{K}^{k}_{a})^{\top}B(0)^{\top}\tilde{P}^{k}x_{a}.$

Replacing
$-Q_{k}(0)=(A_{k}^{\top}(0)\tilde{P}_{a}^{k}+\tilde{P}_{a}^{k}A_{k}(0))=-Q(0)-\tilde{K}^{\top}R(0)\tilde{K}$
from (29) and $B^{\top}(0)\tilde{P}^{k}=R(0)\tilde{K}^{k+1}_{a}$ from (30)
leads to

$\displaystyle\frac{d}{dt}(x^{\top}_{a}\tilde{P}_{a}^{k}x_{a})=-x^{\top}_{a}Q_{k}(0)x_{a}+2(u_{0}+\tilde{K}^{k}_{a})^{\top}R(0)\tilde{K}^{k+1}_{a}x_{a}$
(33)

Notice that (33) is independent of $A(0)$ and $B(0).$ Integrating both sides
of (33) on the interval $[t,t+\delta t]$

$\displaystyle x^{\top}_{a}(t+\delta t)$
$\displaystyle\tilde{P}_{a}^{k}x_{a}(t+\delta
t)-x^{\top}_{a}(t)\tilde{P}_{a}^{k}x_{a}(t)=$ (34)
$\displaystyle-\int_{t}^{t+\delta t}x_{a}^{\top}Q_{k}(0)x_{a}\;dw$
$\displaystyle 2\int_{t}^{t+\delta
t}\left(\tilde{K}^{k}_{a}x_{a}+u_{0}\right)^{T}R(0)\tilde{K}^{k+1}_{a}x_{a}\;dw$

Rearranging the terms (34) leads to the offline policy iteration equation

$\displaystyle x^{\top}_{a}(t+\delta t)$
$\displaystyle\tilde{P}_{a}^{k}x_{a}(t+\delta
t)-x^{\top}_{a}(t)\tilde{P}_{a}^{k}x_{a}(t)$ (35)
$\displaystyle-2\int_{t}^{t+\delta
t}\left(\tilde{K}^{k}_{a}x_{a}+u_{0}\right)^{T}R(0)\tilde{K}^{k+1}_{a}x_{a}\;dw$
$\displaystyle=-\int_{t}^{t+\delta t}x_{a}^{\top}Q_{k}(0)x_{a}\;dw$

We then express (35) in compact form using the Kronecker product ($\otimes$)

$x_{a}^{\top}\tilde{P}^{k}_{a}x_{a}=\left(x_{a}^{\top}\otimes
x_{a}^{\top}\right)\operatorname{vec}\left(\tilde{P}^{k}_{a}\right),$ (36)

and then (36) is used to transform the term from (35)
$x^{\top}_{a}(t+\delta t)\tilde{P}_{a}^{k}x_{a}(t+\delta
t)-x^{\top}_{a}(t)\tilde{P}_{a}^{k}x_{a}(t)$
into:

$\displaystyle x^{\top}_{a}(t+\delta t)\tilde{P}_{a}^{k}x_{a}(t+\delta t)$
$\displaystyle-x^{\top}_{a}(t)\tilde{P}_{a}^{k}x_{a}(t)=$ (37)
$\displaystyle\left[\left.x_{a}^{\top}\otimes
x_{a}^{\top}\right|_{t}^{t+\delta
t}\right]\left[\operatorname{vec}(\tilde{P}^{k}_{a})\right].$

And the next term from (35)

$\displaystyle\left(u_{0}+\tilde{K}_{a}^{k}x\right)^{\top}$ $\displaystyle
R(0)\tilde{K}_{a}^{k+1}x_{a}=$ (38) $\displaystyle\left[\left(x_{a}\top\otimes
x_{a}^{\top}\right)\left(I_{n}\otimes\left(K^{k}\right)^{\top}R(0)\right)+\right.$
$\displaystyle\left.\left(x_{a}^{\top}\otimes
u_{0}^{\top}\right)\left(I_{n}\otimes R(0)\right)\right]\tilde{K}_{a}^{k+1}$

Using (38) to transform the term from (35)
$-2\int_{t}^{t+\delta
t}\left(\tilde{K}^{k}_{a}x_{a}+u_{0}\right)^{T}R(0)\tilde{K}^{k+1}_{a}x_{a}\;dw$
into:

$\displaystyle-2\int_{t}^{t+\delta
t}\left(\tilde{K}^{k}_{a}x_{a}+u_{0}\right)^{T}R(0)\tilde{K}^{k+1}_{a}x_{a}\;dw=$
(39)
$\displaystyle-\left[2\left(\int_{t_{1}}^{t_{1}+\tilde{t}}x_{a}^{\top}\otimes
x_{a}^{\top}dw\right)\left(I_{n}\otimes(\tilde{K}^{k})^{\top}R(0)\right)\right]\kappa$
$\displaystyle-\left[2\left(\int_{t_{1}}^{t_{1}+\tilde{t}}x_{a}^{\top}\otimes
u_{0}^{\top}dw\right)\left(I_{n}\otimes R(0)\right)\right]\kappa$

where $\kappa=\left[\operatorname{vec}({\tilde{K}^{k+1}_{a}})\right]$ and
finally the last term from (35):

$x_{a}^{\top}Q_{k}(0)x_{a}=\left(x_{a}^{\top}\otimes
x_{a}^{\top}\right)\operatorname{vec}\left(Q_{k}(0)\right).$ (40)

Using (40) to transform the term $-\int_{t}^{t+\delta
t}x_{a}^{\top}Q_{k}(0)x_{a}\;dw$ into:

$\displaystyle-\int_{t}^{t+\delta t}$ $\displaystyle
x_{a}^{\top}Q_{k}(0)x_{a}\;dw=$ (41)
$\displaystyle-\left[\int_{t_{1}}^{t_{1}+\delta{t}}x_{a}^{\top}\otimes
x_{a}^{\top}dw\right]\operatorname{vec}\left(Q_{k}(0)\right)$

Using (37), (39) and (41) to express the offline policy iteration (35) in a
compact form:

$\displaystyle\left[\left.x_{a}^{\top}\otimes
x_{a}^{\top}\right|_{t}^{t+\delta
t}\right]\left[\operatorname{vec}(\tilde{P}^{k}_{a})\right]$ (42)
$\displaystyle-2\left[\left(\int_{t_{1}}^{t_{1}+\tilde{t}}x_{a}^{\top}\otimes
x_{a}^{\top}dw\right)\left(I_{n}\otimes(\tilde{K}^{k})^{\top}R(0)\right)\right]\kappa$
$\displaystyle-2\left[\left(\int_{t_{1}}^{t_{1}+\tilde{t}}x_{a}^{\top}\otimes
u_{0}^{\top}dw\right)\left(I_{n}\otimes R(0)\right)\right]\kappa$
$\displaystyle=-\left[\left.x_{a}^{\top}\otimes
x_{a}^{\top}\right|_{t}^{t+\delta
t}\right]\operatorname{vec}\left(Q_{k}(0)\right)$

We can now express (42) in the compact matrix form as

$\tilde{\psi}\left[\begin{array}[]{c}\operatorname{vec}\left(\tilde{P}^{k}_{a}\right)\\\
\operatorname{vec}\left(\tilde{K}^{k+1}_{a}\right)\end{array}\right]=\tilde{\Gamma}$
(43)

where,
$\tilde{\psi}=\left[\tilde{\delta}_{xx},-2\tilde{I}_{xx}\left(I_{n}\otimes\left(\tilde{K}^{k}\right)^{\top}R(0)\right)-2\tilde{I}_{x\bar{u}_{0}}\left(I_{n}\otimes
R\right)\right]$, $\tilde{\delta}_{xx}=\left[\left.x_{a}^{\top}\otimes
x_{a}^{\top}\right|_{t}^{t+\delta t}\right]$,
$\tilde{I}_{xx}=-2\left[\left(\int_{t_{1}}^{t_{1}+\tilde{t}}x_{a}^{\top}\otimes
x_{a}^{\top}dw\right)\left(I_{n}\otimes(\tilde{K}^{k})^{\top}R(0)\right)\right]$
and
$\tilde{I}_{xu_{0}}=-2\left[\left(\int_{t_{1}}^{t_{1}+\tilde{t}}x_{a}^{\top}\otimes
u_{0}^{\top}dw\right)\left(I_{n}\otimes R(0)\right)\right]$.

This way offline policy iteration (35) is expressed in compact form (43). It
should be emphasized that the learning is going to be done through the use of
the state $x(t)$ according to Remark (1). In the next step, we collect this
data offline to estimate the feedback control gain.

Data Collection: During learning, we collect online measurement data,
including state space $x(t)$ and control policy $u_{0}$, for the time period
$[t_{i},t_{j}]$ with the sampling interval $t_{i+1}-t_{i}=\delta t=\tilde{t}$.
This is followed by computing the matrices $\delta_{xx}$, $I_{xx}$ and
$I_{xu_{0}}$ as follows:

$\delta_{xx}=\left[\left.x^{\top}\otimes
x^{\top}\right|_{t_{1}}^{t_{1}+\tilde{t}},\quad\ldots,\left.\quad
x^{\top}\otimes x^{\top}\right|_{t_{j}}^{t_{j}+\tilde{t}}\right]^{\top}$ (44)
$I_{xx}=\left[\int_{t_{1}}^{t_{1}+\tilde{t}}x^{\top}\otimes
x^{\top}dw,\ldots,\quad\int_{t_{l}}^{t_{l}+\tilde{t}}x^{\top}\otimes
x^{\top}dw\right]^{\top}$ (45)
$I_{xu_{0}}=\left[\int_{t_{1}}^{t_{1}+\tilde{t}}x^{\top}\otimes
u_{0}^{\top}dw,\ldots,\quad\int_{t_{l}}^{t_{l}+\tilde{t}}x^{\top}\otimes
u_{0}^{\top}dw\right]^{\top}$ (46)

######  Assumption 4.

There exists a large number $j>0$ such that rank([$I_{xx}\quad I_{xu_{0}}$]) =
$\frac{n(n+1)}{2}+mn$.

Assumption 4 ensures the collection of enough data for the learning process
[23].

Policy Iteration: This step further involves two sub-steps. i) Policy
evaluation; Evaluating the effectiveness of the current policy using the data
from the present data step. and ii) Policy improvement; After we evaluate the
current policy we then update the past policy with this new one. These two
steps will be performed simultaneously until the threshold is met. This is
given as:

$\tilde{\psi}_{k}\left[\begin{array}[]{c}\operatorname{vec}\left(\tilde{P}^{k}_{a}\right)\\\
\operatorname{vec}\left(\tilde{K}^{k+1}_{a}\right)\end{array}\right]=\tilde{\Gamma}_{k},$
(47)

where

$\displaystyle\tilde{\psi}_{k}=\left[\delta_{xx},-2I_{xx}\right.$
$\displaystyle\left(I_{n}\otimes\left(\tilde{K}^{k}\right)^{\top}R(0)\right)$
(48) $\displaystyle\left.-2I_{x\tilde{u}_{0}}\left(I_{n}\otimes
R\right)\right],$
$\tilde{\Gamma}_{k}=-I_{xx}\operatorname{vec}\left(Q_{k}\right).$ (49)

At the end of the learning (i.e at the end of convergence), the feedback gain
can be obtained as $K_{a}=\tilde{K}^{k+1}_{a}$ and the controller for the
system (19) is $u_{a}=-K_{a}x_{a}$.

(ii) Terminal Regulator problem: We follow the same steps as in the initial
regulator problem except the initialization of the control gain should satisfy
$K_{b}<0$. Note that controller for the system (22) is
$u_{b}=-K_{b}^{*}x_{b}.$ Where, $K_{b}^{*}$ is the optimal feedback gain
control.

The pseduocode for the learning algorithm is given in Algorithm (1)

Initialize $K_{a}>0$ ;

while  _$rank([I_{xx}\quad I_{xu_{0}}]) <\frac{n(n+1)}{2}+mn$_ do

Collect the online measurement data $x(t)$ using the excitation control
$u_{a}=u_{0}$;

Construct the matrices $\delta_{xx}$, $I_{xx}$ and $I_{xu_{0}}$

end while

while  _$|P^{k}_{a}-P^{k+1}_{a}| <$ Threshold_ do

Estimate the values of $P_{a}^{k}$ and $K_{a}^{k+1}$ through (47)

end while

$u_{a}=-K_{a}^{k+1}x$;

Initialize $K_{b}<0$;

while  _$rank([I_{xx}\quad I_{xu_{0}}]) <\frac{n(n+1)}{2}+mn$_ do

Collect the online measurement data $x(t)$ using the excitation control
$u_{b}=u_{0}.$

Construct the matrices $\delta_{xx}$, $I_{xx}$ and $I_{xu_{0}}$

end while

while  _$|P^{k}_{b}-P^{k+1}_{b}| <$ Threshold_ do

Estimate the values of $P_{b}^{k}$ and $K_{b}^{k+1}$ through (47)

end while

$u_{b}=-K_{b}^{k+1}x$

Algorithm 1 Offline policy iteration on two value boundary problems

Following the learning procedure described in this section, and in a similar
way to the result reported in Theorem 1, the closed-loop performance of the
learned-control system, comprised of (1) and $u_{\text{learned}}=u_{a}+u_{b},$
will approximate that of the original control system, comprised of (1) and
(5), provided that $\varepsilon$ is sufficiently small or $T$ is sufficiently
long. This will be verified in the simulation example given in the next
section.

##  V Simulation Example

(a) state trajectory for $\varepsilon$ = 0.9

(b) state trajectory for $\varepsilon$ = 0.5

(c) state trajectory for $\varepsilon$ = 0.1

(d) Controller for $\varepsilon$ = 0.9

(e) Controller for $\varepsilon$ = 0.5

(f) Controller for $\varepsilon$ = 0.1

Figure 1: Plots (a), (b) and (c) illustrate the state space trajectory for the
state $x(t)$ for different values of $\varepsilon$ and Plots (d), (e) and (f)
illustrates the control law $u(t)$ for different values of $\varepsilon$.

Consider an object with a dissipating mass $m(t)$ on a frictionless
environment that is described by the following equation [28]

$\frac{dx}{dt}=\frac{1}{m(t)}x+B(t)u$ (50)

where $x(t)$ is the position of the body. We assume that the time-varying
dissipating mass is unknown. In the absence of the external disturbances, the
force $u(t)$ is applied on the object to move it from one position to another.
A controller is sought to achieve the control objective while keeping the
force and position minimum in between the initial and final values. That is,
the controller is needed to minimize the objective function

$J=\frac{1}{2}\int_{0}^{T}q(t)x^{2}(t)+r(t)u^{2}(t)\hskip 5.69054ptdt$ (51)

The initial and final conditions of the system are specified as: $x_{0}=0.5$
and $x_{T}=0.9$ and the cost function parameters are specified as $q(t)=1$,
$r(t)=1$. For simulation purposes, we assume that the mass is given by
$m(t)=\frac{-1}{(1+0.2t)},$ and $B(t)=1.$ During the offline data collection,
we excite the system using the controller $u_{0}=\sum_{0}^{100}sin(wt)$ with
the time interval of 0.01 seconds, where, $w$ is the frequency. where, $w$ is
the random value. The control gains $K_{a}$ and $K_{b}$ are found using the
learning method described in Section IV and found to be 0.410 and -2.46,
respectively.

To compare our results, we found $K_{a}$ and $K_{b}$ values assuming that
$A(t)$ and $B(t)$ are known through the procedure outlined in Section III by
solving the problems (19)-(24). Accordingly, the Riccati equation for the
system (50) for which the controller needs to minimize the objective function
(51) is

$\displaystyle P^{2}+2(1+0.2t)-1$ $\displaystyle=0.$ (52)

The two roots for the Riccati equation (52) are:

$P=-(1+0.2t)\pm\sqrt{(1+0.2)^{2}+1}.$ (53)

Since $P_{a}\geq 0$ and $P_{b}\leq 0$ the values of $P_{a}(0)$ and $P_{b}(1)$
are:

$P_{a}(0)=-1+\sqrt{2}=0.414,\quad P_{b}(1)=-1-\sqrt{2}=-2.414.$ (54)

After finding the controllers $u_{a}$ and $u_{b}$, we simulate the system
through finding the time $t_{c}$ for which $x_{a}(t_{c})=x_{b}(1-t_{c})$.
Recall that $x_{a}$ and $x_{b}$ refer to the state trajectories in the forward
and reverse time respectively. We then use the controller $u_{a}$ in the time
interval $[0,t_{c}]$ and the controller $u_{b}$ in the time interval
$[t_{c},1]$. Note that we are normalizing the time interval to $[0,1]$ instead
of $[0,T]$ to make the comparison between the controllers clear.

The optimal state trajectory and the optimal controller is found using the two
value boundary problem solver from MATLAB command bvp4c using the knowledge of
$A(t)$ and $B(t)$. We then compare the state space trajectory and the
controller obtained using our learning method with that of the approximate
method and the optimal controller with $A(t)$ and $B(t)$ known. From Figure 1,
we can see that the learning-based controller accurately approximates the
optimal controller as $\varepsilon$ is decreased (or control time period $T$
increases). This implies that the performance of the learning controller is a
sub-optimal one and converges to the optimal performance as the time interval
$T$ gets large.

##  VI CONCLUSIONS AND FUTURE WORKS

We proposed optimal controller design using reinforcement learning for time
varying systems with bounded conditions. The proposed design leverages the
fast time scale occurring at the boundary conditions to reduce the time-
varying problem into two simple time-invariant problems. Further, we design
the sub-optimal controller to approximate the controller for time-varying
systems. The accuracy of the controller performance improves as the problem
time horizon increases. We presented simulation results to support our claims
using a dissipating mass system on a friction-less environment. In the future,
we plan to extend our work in learning the controllers of nonlinear systems.

## References

  * [1] Szmuk, Michael, and Behcet Acikmese. ”Successive convexification for 6-dof mars rocket powered landing with free-final-time.” 2018 AIAA Guidance, Navigation, and Control Conference. 2018.
  * [2] Fortuna, M., A. Klepka, K. Dziedziech, W. J. Staszewski, and T. Uhl. ”Time-variant modal analysis of a CanSat rocket.”
  * [3] Wang, Xinning, Chong Li, Dalei Song, and Robert Dean. ”A Nonlinear Circuit Analysis Technique for Time-Variant Inductor Systems.” Sensors 19, no. 10 (2019): 2321.
  * [4] Mahdavi, J., A. Emaadi, M. D. Bellar, and M. Ehsani. ”Analysis of power electronic converters using the generalized state-space averaging approach.” IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications 44, no. 8 (1997): 767-770.
  * [5] Wilde, R., and P. Kokotovic. ”A dichotomy in linear control theory.” IEEE Transactions on Automatic control 17.3 (1972): 382-383.
  * [6] Chow, J. H. ”A class of singularly perturbed, nonlinear, fixed-endpoint control problems.” Journal of Optimization Theory and Applications 29.2 (1979): 231-251.
  * [7] Ardema, Mark. ”Nonlinear singularly perturbed optimal control problems with singular arcs.” Automatica 16.1 (1980): 99-104.
  * [8] Sannuti, Peddapullaiah. ”Asymptotic expansions of singularly perturbed quasi-linear optimal systems.” SIAM Journal on Control 13.3 (1975): 572-592.
  * [9] Gugat, Martin, Emmanuel Trélat, and Enrique Zuazua. ”Optimal Neumann control for the 1D wave equation: Finite horizon, infinite horizon, boundary tracking terms and the turnpike property.” Systems & Control Letters 90 (2016): 61-70.
  * [10] Pighin, Dario. ”The turnpike property in semilinear control.” arXiv preprint arXiv:2004.03269 (2020).
  * [11] Ioannou, Petros, and Bariş Fidan. Adaptive control tutorial. Society for Industrial and Applied Mathematics, 2006.
  * [12] Sutton, Richard S., and Andrew G. Barto. ”Reinforcement learning: an introduction MIT Press.” Cambridge, MA 22447 (1998).
  * [13] Kleinman, David. ”On an iterative technique for Riccati equation computations.” IEEE Transactions on Automatic Control 13.1 (1968): 114-115.
  * [14] Vamvoudakis, Kyriakos G. ”Q-learning for continuous-time linear systems: A model-free infinite horizon optimal control approach.” Systems & Control Letters 100 (2017): 14-20.
  * [15] Vamvoudakis, Kyriakos G., and Frank L. Lewis. ”Online actor–critic algorithm to solve the continuous-time infinite horizon optimal control problem.” Automatica 46.5 (2010): 878-888
  * [16] Kiumarsi, Bahare, Frank L. Lewis, Mohammad-Bagher Naghibi-Sistani, and Ali Karimpour. ”Optimal tracking control of unknown discrete-time linear systems using input-output measured data.” IEEE transactions on cybernetics 45, no. 12 (2015): 2770-2779.
  * [17] Zhao, Qiming, Hao Xu, and Jagannathan Sarangapani. ”Finite‐horizon near optimal adaptive control of uncertain linear discrete‐time systems.” Optimal Control Applications and Methods 36, no. 6 (2015): 853-872.
  * [18] Pang, Bo, Tao Bian, and Zhong-Ping Jiang. ”Adaptive dynamic programming for finite-horizon optimal control of linear time-varying discrete-time systems.” Control Theory and Technology 17, no. 1 (2019): 73-84.
  * [19] Kleinman, David. ”On an iterative technique for Riccati equation computations.” IEEE Transactions on Automatic Control 13, no. 1 (1968): 114-115.
  * [20] Pang, Bo, Zhong-Ping Jiang, and Iven Mareels. ”Reinforcement learning for adaptive optimal control of continuous-time linear periodic systems.” Automatica 118 (2020): 109035.
  * [21] Pang, Bo, and Zhong-Ping Jiang. ”Adaptive optimal control of linear periodic systems: An off-policy value iteration approach.” IEEE Transactions on Automatic Control (2020).
  * [22] Fong, Justin, Ying Tan, Vincent Crocher, Denny Oetomo, and Iven Mareels. ”Dual-loop iterative optimal control for the finite horizon LQR problem with unknown dynamics.” Systems & Control Letters 111 (2018): 49-57.
  * [23] Jiang, Yu, and Zhong-Ping Jiang. Robust adaptive dynamic programming. John Wiley & Sons, 2017.
  * [24] Jiang, Yu, and Zhong-Ping Jiang. ”Computational adaptive optimal control for continuous-time linear systems with completely unknown dynamics.” Automatica 48.10 (2012): 2699-2704.
  * [25] Ross, I. Michael. ”Space Trajectory Optimization and,”.” Modern astrodynamics 1 (2006): 155.
  * [26] Wilde, R., & Kokotovic, P. (1972). A dichotomy in linear control theory. IEEE Transactions on Automatic control, 17(3), 382-383.
  * [27] Anderson, Brian DO, and John B. Moore. Optimal control: linear quadratic methods. Courier Corporation, 2007.
  * [28] Athans, Michael, and Peter L. Falb. Optimal control: an introduction to the theory and its applications. Courier Corporation, 2013.
  * [29] Kokotović, Petar, Hassan K. Khalil, and John O’reilly. Singular perturbation methods in control: analysis and design. Society for Industrial and Applied Mathematics, 1999.


# True optical spacial derivatives for plasma density measurements

P.-A. Gourdain<EMAIL_ADDRESS>Department of Physics and Astronomy,
University of Rochester, Rochester NY 14627, USA  Laboratory for Laser
Energetics, University of Rochester, Rochester NY 14627, USA  I. N. Erez
Department of Physics and Astronomy, University of Rochester, Rochester NY
14627, USA  Laboratory for Laser Energetics, University of Rochester,
Rochester NY 14627, USA  M. E. Evans  Department of Physics and Astronomy,
University of Rochester, Rochester NY 14627, USA  Laboratory for Laser
Energetics, University of Rochester, Rochester NY 14627, USA  H. R. Hasson
Department of Physics and Astronomy, University of Rochester, Rochester NY
14627, USA  Laboratory for Laser Energetics, University of Rochester,
Rochester NY 14627, USA  J. Nagasako  Department of Physics and Astronomy,
University of Rochester, Rochester NY 14627, USA  J. R. Young  Department of
Physics and Astronomy, University of Rochester, Rochester NY 14627, USA
Laboratory for Laser Energetics, University of Rochester, Rochester NY 14627,
USA  I. West-Abdallah  Department of Physics and Astronomy, University of
Rochester, Rochester NY 14627, USA  Laboratory for Laser Energetics,
University of Rochester, Rochester NY 14627, USA

###### Abstract

This paper shows analytically and numerically that a vortex plate coupled to a
neutral density filter can deliver a true optical derivative when placed at
the focal plane of a $2f$ lens pair. This technique turns spatial variations
in intensity into an intensity, which square root is the spatial derivative of
the initial intensity variation. More surprisingly, it also turns any spatial
variations in phase into an intensity, which square root is the spatial
derivative of the initial phase variation. Since the optical derivative drops
the DC component of the signal, it is possible to measure the full electron
plasma turbulence spectrum optically, without using any interferometer.

##  1 Introduction

The differentiation of a measured signal has always a task difficult to
accomplish. This operation increases the noise to levels, with disastrous
consequences on the subsequent analysis of a signal. This problem is common in
scientific applications and, while the operation itself does not amplify the
noise levels, the elimination of the signal average (also called ”DC” value)
decreases the signal-to-noise ratio. Yet, taking the space derivative of a
signal can be useful. For instance, the derivative can enhance the contrast of
an image. When light is used as a probe, the analog derivative operation
becomes relatively straightforward, using optical systems to perform the
derivative operation before the signal is recorded[1], leading to practical
measurements such as mechanical shear [2]. In fact, almost any optical method
has its own optical derivation technique, from schlieren imaging to [3] to
shearing interferometry[4]. Methods have been perfected over the years to
yield really high sensitivity [5, 6, 7]. Another advantage of using optics is
the simplicity of doing a Fourier transform, which naturally appears on the
focal plane of a converging lens. Any optical operation done on this plane is
automatically done in Fourier space, and transferred back to the image when it
is reconstructed on the other side of the lens. Using different filtering
techniques ones can perform first order optical phase derivatives[8],
fractional derivatives[9, 10] and even two-dimensional first derivatives[11].

As manufacturing methods for optical devices reach sub-wavelength precision,
new possibilities have come to light to form the derivative of an optical
signal: vortex plates [12, 13]. By carving a spiral (stair-case like) cavity
on the order of the light wavelength, one can generate vectorial beams[14, 15,
16, 17]. When they are inserted on the focal plane of a thin lens, they can
greatly improve the quality of the image from phase contrast imaging[18, 19].
However, a vortex plate coupled to a linearly varying neutral density filter
placed on the focal plane of the $2f$ lens pair of Fig. 1 can yield a spatial
derivative of extremely high quality. In this paper, we show how to construct
an optical derivative using the mathematical foundations behind the optical
Fourier transforms. We then use numerical simulations to show how this setup
can be used to measure the electron density and turbulent fluctuations of a
dense plasma.

##  2 True optical derivatives

###  2.1 Construction of a true optical derivative

Lenses can decompose the image of an object into its spatial frequency
components on the lens’ focal plane

$U(f_{x},f_{y})=\int_{-\infty}^{+\infty}\int_{-\infty}^{+\infty}u(x,y)e^{i2\pi
xf_{x}}e^{i2\pi yf_{y}}dxdy$ (1)

where the complex intensity $U(f_{x},f_{y})$ is now the Fourier transform of
the object on the focal plane of the lens[20].

Object plane$u(x,y)$$-f$$0$Fourier (focal) plane$U(f_{x},f_{y})$$f$$2f$Image
plane$u^{\prime}(x,y)$$3f$ Figure 1: Two-$f$ system uses two identical lenses
of focal length $f$

####  2.1.1 Normalized spatial derivative using a vortex plate

Following Ref. 14, using monochromatic coherent light, any image in the object
plane $u(x,y)$ can be decomposed using the Fourier theorem as a discrete sum
of sine and cosine functions

$u(x,y)=\sum_{n=-\infty}^{+\infty}A_{n}\cos(\textbf{k}_{n}\cdot\textbf{r})+B_{n}\sin(\textbf{k}_{n}\cdot\textbf{r}),$

where $\textbf{k}_{n}\cdot\textbf{r}=k_{x,n}x+k_{y,n}y$. While looking at the
whole signal might be overwhelmingly complex to understand how the vortex
plate operates, we can look at the components of $u(x,y)$ individually,
labeled $u_{\textbf{k}}(x,y)=\cos(k_{x}x+k_{y}y)$. We drop the amplitudes
$A_{n}$ and $B_{n}$ here for clarity. The corresponding signal on the lens
focal plane of Fig. 1 is given by

$U_{\textbf{k}}(f_{x},f_{y})=\pi\delta\left(k_{x}/2\pi-
f_{x}\right)\delta\left(k_{y}/2\pi-
f_{y}\right)-\pi\delta\left(k_{x}/2\pi+f_{x}\right)\delta\left(k_{y}/2\pi+f_{y}\right),$
(2)

which evidently gives back $u^{\prime}_{\textbf{k}}(x,y)=\cos(k_{x}x+k_{y}y)$
on the image plane located at $2f$. However, when a vortex plate of charge
$l=1$ is used on the Fourier plane, Eq. 2 turns into

$U_{\textbf{k}}(f_{x},f_{y})=\left[\pi\delta\left(\frac{k_{x}}{2\pi}-f_{x}\right)\delta\left(\frac{k_{y}}{2\pi}-f_{y}\right)-\pi\delta\left(\frac{k_{x}}{2\pi}+f_{x}\right)\delta\left(\frac{k_{y}}{2\pi}+f_{y}\right)\right]\exp\left[-i\arctan(f_{x},f_{y})\right].$
(3)

Note that the function $\arctan(f_{x},f_{y})$ gives the angle of the point
$(f_{x},f_{y})$. Back on the image plane we now have

$u^{\prime}_{\textbf{k}}(x,y)=-\left(k_{x}+ik_{y}\right)\frac{\sin\left(k_{x}x+k_{y}y\right)}{\sqrt{k_{x}^{2}+k_{y}^{2}}}.$
(4)

At this point, we can compute the intensity $I_{\textbf{k}}$ of the mode wave
number k as

$I_{\textbf{k}}=\left(k_{x}+ik_{y}\right)\frac{\sin\left(k_{x}x+k_{y}y\right)}{\sqrt{k_{x}^{2}+k_{y}^{2}}}\overline{\left(k_{x}+ik_{y}\right)\frac{\sin\left(k_{x}x+k_{y}y\right)}{\sqrt{k_{x}^{2}+k_{y}^{2}}}}$

or $I_{\textbf{k}}=\sin^{2}\left(\textbf{k}\cdot\textbf{r}\right)$. We see
that the square root of the intensity on the image plane located at $2f$ is

$\sqrt{I_{\textbf{k}}}=\left|\sin\left(\textbf{k}\cdot\textbf{r}\right)\right|,$
(5)

which can be written as a normalized derivative

$\sqrt{I_{\textbf{k}}}=\left|\frac{\partial\cos\left(\textbf{k}\cdot\textbf{r}\right)}{\partial\textbf{k}\cdot\textbf{r}}\right|,$
(6)

which simply corresponds to $|d\cos x/dx|$. Following the same reasoning for
$u_{\textbf{k}}=\sin\left(\textbf{k}\cdot\textbf{r}\right)$ we get on the
image plane

$\sqrt{I_{\textbf{k}}}=\left|\cos\left(\textbf{k}\cdot\textbf{r}\right)\right|=\left|\frac{\partial\sin\left(\textbf{k}\cdot\textbf{r}\right)}{\partial\textbf{k}\cdot\textbf{r}}\right|.$
(7)

####  2.1.2 True optical derivative using a vortex plate and a neutral density
filter

However, Eq. 3 shows that it is relatively straightforward to recover a true
derivative. If we add next to the vortex plate a neutral density filter, which
transmission $T$ varies linearly with the radius as

$T(f_{x},f_{y})=\sqrt{f_{x}^{2}+f_{y}^{2}},$ (8)

we now get on the Fourier plane

$U_{\textbf{k}}(f_{x},f_{y})=\pi\left[\delta\left(\frac{k_{x}}{2\pi}-f_{x}\right)\delta\left(\frac{k_{y}}{2\pi}-f_{y}\right)-\delta\left(\frac{k_{x}}{2\pi}+f_{x}\right)\delta\left(\frac{k_{y}}{2\pi}+f_{y}\right)\right]\sqrt{f_{x}^{2}+f_{y}^{2}}\exp\left[-i\arctan(f_{x},f_{y})\right].$
(9)

Back to the image plane, Eq. 9 yields

$u^{\prime}_{\textbf{k}}(x,y)=-\left(k_{x}+ik_{y}\right)\sin\left(k_{x}x+k_{y}y\right).$
(10)

The square root of the intensity on the image plane is now

$\sqrt{I_{\textbf{k}}}=\left|\textbf{k}\sin\left(\textbf{k}\cdot\textbf{r}\right)\right|=\left|\frac{\partial\cos\left(\textbf{k}\cdot\textbf{r}\right)}{\partial\textbf{r}}\right|.$
(11)

Using the same reasoning Eq. 11 turns into

$\sqrt{I_{\textbf{k}}}=\left|\textbf{k}\cos\left(\textbf{k}\cdot\textbf{r}\right)\right|=\left|\frac{\partial\sin\left(\textbf{k}\cdot\textbf{r}\right)}{\partial\textbf{r}}\right|$
(12)

when we look at the sine component of $u$. With the help of the linearly
varying neutral density filter, we obtained the actual spatial derivative of
the signal $u_{\textbf{k}}(x,y)$ in the image plane.

a) b) c) d)

Figure 2: A mask of the spirit logo of the authors’ university is placed at
the object location shown in Fig. 1 leading to a) the bright-field image of
this logo, located on the image plane. b) When a blade is inserted so its edge
rests on the optical axis, we obtain a schlieren image. c) The image edges are
sharper when a vortex plate is placed on the focal plane, yielding the
normalized optical derivative. d) The image can be made much sharper by adding
a neutral density filter, which produces the true optical derivative. All
intensities are absolute.

###  2.2 Numerical validation

In the rest of the paper, we use ray tracing[21] with Rayleigh-Sommerfeld
diffraction [22] to compute the effect of each optical element on the
intensity and phase of a Gaussian laser beam. For practical reason we choose
to work using a wavelength $\lambda=$532 nm. The beam size $d$ is 8mm, the
focal length of each lens is $f=10\textit{cm}$ and the total number of rays is
1024. We use numerical simulations here to highlight the difference between
the normalized optical derivative and the true optical derivative. We also
computed a schlieren image for comparison. The image of the backlit mask on
the image plane is shown in Fig. 2-a. A well known method to enhance contrast
uses schlieren imaging[23], shown in Fig. 2-b. We can greatly improve the
contrast using vortex plate. As Fig. 2-c shows, the mask edges appear more
clearly on the image plane. THe normalized derivation causes the ”halo”
surrounding the mask edges as large gradients have the same intensities as
smaller ones. In other words, the derivative of large $k$ modes is similar to
the derivative for low $k$ modes, leading to a spread of the derivative,
regardless of its $k$ value. This result matches qualitatively Fig. 3 of Ref.
[19] using a spiral phase plate. Finally, if we add the neutral density filter
with profile given by Eq. 8 we finally get the true optical derivative, shown
in Fig. 2-d. Based on Eqs. 11 and 12 we expect the intensity to be
proportional to the characteristic wave number $k$ of the edge transition.

Figure 3: The difference between the square root of the intensity from the
vortex plate alone (VP) and the the vortex plate coupled to a neutral density
filter (VP+ND) for a back-lit cylinder with a transmission profile given by
$P(x)=1-\exp(-(x/\sigma)^{2})$. The analytic derivative of the profile
$P^{\prime}(r)=\frac{2x}{\sigma^{2}}\exp(-(x/\sigma)^{2})$ is also given for
reference (Derivative). The mask transmission is also shown for reference. All
line-outs have been normalized

We now use a mask that changes smoothly as

$P(x,y)=1-\exp\left(-\frac{x^{2}}{\sigma^{2}}\right),$ (13)

to track numerically the value of the derivative and shown on Fig. 3. This
approach allows to check numerically the spatial dependence of the true
optical derivative. Fig. 3 shows that the optical derivative matches the
analytical derivative up to the simulation precision limited by the
discretization inherent to the Rayleigh-Sommerfeld propagation scheme [22].
The separation between rays lead to some oscillations clearly visible on the
line-out. These oscillations are due to the reduction in intensity, which
decreases the signal to noise ratio of the computation. However, this is the
maximum intensity for each ray that counts, and the intensity there always
matches the analytical derivative. We can see that the normalized derivative
using the vortex plate alone does not match as well the analytical derivative.
Note that the RS propagation error is less pronounced for the vortex plate
line-out (though still visible), since the actual intensity is an order of
magnitude larger compared to the vortex plate coupled with the neutral density
filter.

##  3 Plasma density measurements

We now pivot to the main topic of the paper. When a gas is ionized and turned
into plasma with electron number density $N_{e}$, the index of refraction $n$
of the medium [24] is given by

$n=\sqrt{1-\frac{N_{e}}{N_{c}}},$ (14)

where the critical electron density $N_{c}\left[\text{cm}^{-3}\right]\approx
10^{21}\lambda[\mu\text{m}]^{-2}$. In this case, the phase change caused by
electrons is given by

$\Delta\phi=\frac{\pi}{N_{c}\lambda}\int_{L}N_{e}dl$ (15)

With simulations using green light at 532 nm, a phase shift of $2\pi$
corresponds to an areal electron density of $4\times 10^{17}\text{cm}^{-2}$.

###  3.1 Plasma density gradients

Figure 4: a) The square root of the intensity on the optical axis along the
positive part of the (horizontal) x-axis for two phase profiles $P_{1}$ and
$P_{2}$. We scaled the peak of the square root of the intensity (VP+ND
$P_{1}$) for the profile $P_{1}$ using the peak of $\partial P_{1}/\partial x$
(derivative $P_{1}$) to calibrate the intensity. There is a clear agreement
between the analytical phase derivative and the measured phase. Keeping the
calibration unchanged, we found excellent agreement between the square root of
the intensity (VP+ND $P_{2}$) obtained for the phase profile $P_{2}$ and the
analytical partial derivative $\partial P_{2}/\partial x$ (derivative
$P_{2}$). We also show the square root of the intensity obtained with the
neutral density filter only (ND $P_{2}$). b) The integration of the square
root of the intensity obtained for the phase profile $P_{2}$ (integrated)
matches really well the analytical form of the phase profile $P_{2}$ (true).
Without the optical derivative, only the wrapped phase can be measured
(measured).

If the plasma density is far from the cut-off density then laser
interferometry can be used to measure the phase difference caused by free
electrons inside the plasma. However this approach requires phase
unwrapping[25], a task deceptively difficult. Here we propose to use the true
optical derivative to measure density gradients. If the measurement is
accurate enough, the density can be recovered by integrating the square root
of the intensity measured on the image plane. So we trade phase unwrapping
with absolute intensity measurement, which are prone to parasitic background
light. Further, we only have access to the absolute value of the derivative,
which makes integration challenging for plasma densities generated by complex
plasma structures (e.g. Ref. [26]).

For the sake of simplicity, we suppose here that the plasma is completely
transparent but has a density which line integrated phase varies as Eq. 13. We
looked at two cases. The case where $P_{1}(x,y)=5\pi P(x,y)$ and the case
$P_{2}(x,y)=15\pi P(x,y)$. The laser beam is then processed by the setup shown
in Fig. 1, leading to the results presented in Fig. 4. After computing the
intensity for the density profile corresponding to the distribution $P_{1}$,
we scaled the square root to match the analytical derivative of $P_{1}$, in
order to calibrate the simulation easily. Then we computed the intensity
variation caused by the profile $P_{2}$ keeping the scaling unchanged. Fig.
4-a shows that the analytical derivatives are following exactly the
derivatives obtained optically for both profile. We see that the optical and
analytical derivatives virtually fall on top of each other for both $P_{1}$
and $P_{2}$. Note that when we use the neutral density filter without the
vortex plate, we get an approximate optical derivative that does not match as
well the analytical derivative on axis.

The integral of the optical derivative of $P_{2}$ is shown in Fig. 4-b. As
expected, the integrated phase follows the true phase given by profile
$P_{2}$. If we wanted to measure the true phase, we would get the phase
wrapped modulo $2\pi$, also show in 4-b. Note that the proposed setup allows
to measured variations in phase or in intensity in the exact same manner.

###  3.2 Plasma turbulence

Figure 5: Phase fluctuations generated by Eq. 16 to simulate turbulence, with
$k_{1}=3\pi/d$, $k_{2}=8\pi/d$, and $\gamma_{1}=\gamma_{2}=10$ (left). The
intensity is constant throughout the object plane. The square root of the
intensity on the image plate for the vortex plate alone (center) and the
vortex plate coupled with neutral density filter (right).

Analog Fourier transforms using optical system to study the dominant modes
inside an image preceded their digital counterpart by several decades.
However, the removal of the zeroth order (i.e. DC) component [27] has always
been necessary when one is interested in measuring all the modes[28],
especially for low wave numbers. Going back to Eqs. 11 and 12, we clearly see
that the optical derivative naturally cancels the constant light background
(with wave number $k=0$). With the DC component removed from the Fourier
plane, it is now possible to record low-k modes. As a proof of principle, we
modelled plasma fluctuations following Ref. [29], using the products of two
sine functions,

$F(x,y)=\frac{\pi}{\gamma_{1}}\sin(k_{1}x)\sin(k_{1}y)+\frac{\pi}{\gamma_{2}}\sin(k_{2}x)\sin(k_{2}y).$
(16)

We included here two distinct modes $k_{1}$ and $k_{2}$. The corresponding
density fluctuations are shown on the left in Fig. 5 and the optical
derivatives are on the right of Fig. 5. We took $\gamma_{1}=\gamma_{2}=10$,
yielding a phase fluctuation areal density of $4\times 10^{16}\text{cm}^{-2}$.
When a vortex plate alone is used (center of Fig. 5), the periodicity of the
image is lost. But when the neutral density filter is added, the derivative
recovers the expected periodic structure. For our mode analysis, we now look
at the Fourier plane where we can find the wave number of the turbulence
directly.

Figure 6: The intensity on the Fourier (focal) plane, giving directly the
spatial spectrum of the turbulence. a) Intensity plotted on the linear scale
does not give much information on the turbulence spectrum. b) While the
spectrum can be recovered on a saturated image, the DC component tends to wash
out the low-k modes in practical implementations.

Now starting with the vortex plate alone, Fig. 6-a shows the DC component only
when the intensity is plotted on the linear scale. Numerically, it is always
possible to clip the color scale to regain some information on the dominant
modes, even if the mode amplitude cannot be measured accurately (see Fig.
6-b). Practically, the DC component tends to saturate a CCD detector, swamping
the nearby pixels and limiting the measurement of low-k modes. By adding the
neutral density filter, Fig. 7 shows the DC component of the signal has
disappeared when taking the spatial derivative of the image and all the modes
are now visible. Clipping the color only helps in seeing the mode harmonics.

Figure 7: The same density fluctuations as Fig. 6 but with the vortex plate
coupled to the neutral density filter. a) Even with the intensity on the
linear scale we can see the different modes clearly. Due to the low DC level,
even a saturated spectrum is fully usable.

##  4 Conclusions

In this paper, we have shown that a 2f lens pair can be used to perform a true
optical derivative by combining a vortex plate on the Fourier plane with a
neutral density filter with linear radial dependence. It is relatively
straightforward to obtain the derivative of two-dimensional intensity or phase
profiles, though an absolute calibration is required to measure the plasma
electron density directly, without an interferometer. However some
uncertainties remain since we do not have access to the sign of the
derivative, but only its absolute value. It is also possible to record
directly the wave number of the turbulence by using the analog Fourier
transform offered by the lens.

While this method is straightforward to implement numerically, some practical
considerations still remain. Since we solely rely on intensity measurements,
absolute calibration of intensity in the image plane is necessary, at least
for measuring density. However, the absolute calibration is not required to
measure the turbulence wave number. Ultimately, practical implementation will
require a uniform laser beam, as speckling will be amplified by the derivative
operation. Plasma light can be another source of noise that should be taken
under consideration. So the beam needs to be filtered properly to generate a
high quality backlighter.

In conclusion, we were able to demonstrate analytically and numerically that a
vortex plate coupled to a neutral density filter can deliver a true optical
derivative when placed at the focal plane of a $2f$ lens pair. The system can
be used to turn spatial variation in intensity into an intensity, which square
root is the spatial derivative of the initial intensity variation. What is
more surprising, the system also turns any spatial variation in phase into an
intensity which square root is the spatial derivative of the initial phase
variation, leading to a mean to measure phase without requiring
interferometry.

## Acknowledgements

This research was supported by the NSF CAREER Award PHY-1943939 and by the
Laboratory for Laser Energetics Horton Fellowships.

## References

## References

  * [1] R. Hoffman and L. Gross, “Modulation contrast microscope,” Appl. Opt., vol. 14, pp. 1169–1176, May 1975.
  * [2] R. Kulkarni and P. Rastogi, “Measurement of displacement and its derivatives from a phase fringe pattern,” Structural Integrity, vol. 5, p. 139 – 144, 2019.
  * [3] B. Zakharin and J. Stricker, “Schlieren systems with coherent illumination for quantitative measurements,” Appl. Opt., vol. 43, pp. 4786–4795, Sep 2004\.
  * [4] S. Velghe, J. Primot, N. Guérineau, M. Cohen, and B. Wattellier, “Wave-front reconstruction from multidirectional phase derivatives generated by multilateral shearing interferometers,” Optics Letters, vol. 30, no. 3, p. 245 – 247, 2005.
  * [5] Q. Kemao, “Two-dimensional windowed fourier transform for fringe pattern analysis: Principles, applications and implementations,” Optics and Lasers in Engineering, vol. 45, no. 2, pp. 304–317, 2007.  Phase Measurement Techniques and their applications.
  * [6] R. Legarda-Saenz and A. Espinosa-Romero, “Wavefront reconstruction using multiple directional derivatives and fourier transform,” Optical Engineering, vol. 50, no. 4, 2011.
  * [7] D. Post, B. Han, and P. Ifju, “Moiré interferometry,” in High Sensitivity Moiré, pp. 135–226, Springer, 1994.
  * [8] K. Qian, S. H. Soon, and A. Asundi, “Phase-shifting windowed fourier ridges for determination of phase derivatives,” Optics letters, vol. 28, no. 18, pp. 1657–1659, 2003.
  * [9] J. Lancis, T. Szoplik, E. Tajahuerce, V. Climent, and M. Fernández-Alonso, “Fractional derivative fourier plane filter for phase-change visualization,” Appl. Opt., vol. 36, pp. 7461–7464, Oct 1997.
  * [10] E. Tajahuerce, T. Szoplik, J. Lancis, V. Climent, and M. Fernandez, “Phase-object fractional differentiation using fourier plane filters,” Pure and Applied Optics: Journal of the European Optical Society Part A, vol. 6, p. 481, jul 1997.
  * [11] R. N. Bracewell, The Fourier transform and its applications, vol. 31999.  McGraw-Hill New York, 1986.
  * [12] R. Oron, N. Davidson, A. A. Friesem, and E. Hasman, “Chapter 6 - transverse mode shaping and selection in laser resonators,” in Progress in Optics (E. Wolf, ed.), vol. 42 of Progress in Optics, pp. 325–386, Elsevier, 2001\.
  * [13] S. Oemrawsingh, J. Van Houwelingen, E. Eliel, J. Woerdman, E. Verstegen, J. Kloosterboer, et al., “Production and characterization of spiral phase plates for optical wavelengths,” Applied optics, vol. 43, no. 3, pp. 688–694, 2004.
  * [14] Q. Zhan, “Cylindrical vector beams: from mathematical concepts to applications,” Adv. Opt. Photon., vol. 1, pp. 1–57, Jan 2009.
  * [15] E. J. Galvez, S. Khadka, W. H. Schubert, and S. Nomoto, “Poincaré-beam patterns produced by nonseparable superpositions of Laguerre–Gauss and polarization modes of light,” Appl. Opt., vol. 51, pp. 2925–2934, May 2012.
  * [16] R. W. Boyd and M. J. Padgett, “Quantum mechanical properties of light fields carrying orbital angular momentum,” in Optics in Our Time, pp. 435–454, Springer, Cham, 2016.
  * [17] F. Bouchard, H. Larocque, A. M. Yao, C. Travis, I. De Leon, A. Rubano, E. Karimi, G.-L. Oppo, and R. W. Boyd, “Polarization shaping for control of nonlinear propagation,” Physical Review Letters, vol. 117, no. 23, p. 233903, 2016.
  * [18] S. Fürhapter, A. Jesacher, S. Bernet, and M. Ritsch-Marte, “Spiral phase contrast imaging in microscopy,” Optics Express, vol. 13, no. 3, pp. 689–694, 2005.
  * [19] A. Jesacher, S. Fürhapter, S. Bernet, and M. Ritsch-Marte, “Shadow effects in spiral phase contrast microscopy,” Physical review letters, vol. 94, no. 23, p. 233902, 2005.
  * [20] J. Goodman, Introduction to Fourier Optics.  New York, NY: W.H. Freeman, 4 ed., May 2017.
  * [21] L. S. Brea, “Diffractio, python module for diffraction and interference optics,” 2019.
  * [22] F. Shen and A. Wang, “Fast-fourier-transform based numerical integration method for the Rayleigh-Sommerfeld diffraction formula,” Applied optics, vol. 45, no. 6, pp. 1102–1110, 2006.
  * [23] G. S. Settles and M. J. Hargather, “A review of recent developments in schlieren and shadowgraph techniques,” Measurement Science and Technology, vol. 28, no. 4, p. 042001, 2017.
  * [24] I. H. Hutchinson, Principles of Plasma Diagnostics.  Cambridge University Press, 2 ed., 2002.
  * [25] D. C. Ghiglia and M. D. Pritt, “Two-dimensional phase unwrapping: theory, algorithms, and software,” A Wiley Interscience Publication, 1998.
  * [26] H. R. Hasson, M. B. Adams, M. Evans, R. V. Shapovalov, I. West-Abdallah, J. Young, J. Greenly, D. Hammer, B. Kusse, C. Seyler, et al., “Design of a 3-d printed experimental platform for studying the formation and magnetization of turbulent plasma jets,” IEEE Transactions on Plasma Science, vol. 48, no. 11, pp. 4056–4067, 2020.
  * [27] E. B. Felstead, “Removal of the zero order in optical fourier transformers,” Appl. Opt., vol. 10, pp. 1185–1187, May 1971.
  * [28] A. P. Lang, “Interferometer for D.C. level removal in optical fourier transforms,” Optica Acta: International Journal of Optics, vol. 32, no. 2, pp. 123–133, 1985.
  * [29] S. Zweben, J. Caird, W. Davis, D. Johnson, and B. Le Blanc, “Plasma turbulence imaging using high-power laser Thomson scattering,” Review of Scientific Instruments, vol. 72, no. 1, pp. 1151–1154, 2001.


# Proper Distinguishing Colorings with Few Colors
for Graphs with Girth at Least 5

Daniel W. Cranston Department of Mathematics and Applied Mathematics, Virginia
Commonwealth University, Richmond, VA<EMAIL_ADDRESS>This research is
partially supported by NSA Grant H98230-16-0351.

###### Abstract

The distinguishing chromatic number, ${\chi_{D}}(G)$, of a graph $G$ is the
smallest number of colors in a proper coloring, $\varphi$, of $G$, such that
the only automorphism of $G$ that preserves all colors of $\varphi$ is the
identity map. Collins and Trenk conjectured that if $G$ is connected with
girth at least 5 and $G\neq C_{6}$, then ${\chi_{D}}(G)\leqslant\Delta+1$. We
prove this conjecture.

##  1 Introduction

A _$k$ -coloring_ $\varphi$ of a graph $G$ is a map
$\varphi:V(G)\to\\{1,\ldots,k\\}$. If $\varphi(v)\neq\varphi(w)$ whenever
$vw\in E(G)$, then $\varphi$ is _proper_. A vertex, $w$, is _fixed_ ††margin:
fixed by a coloring $\varphi$ if every automorphism $f$ that preserves all
colors (that is $\varphi(f(v))=\varphi(v)$ for all $v\in V(G)$) has $f(w)=w$.
A coloring $\varphi$ of a graph $G$ is _distinguishing_ ††margin:
distinguishing if it fixes every vertex; equivalently, if the only
automorphism $f$ of $G$ with $\varphi(f(v))=\varphi(v)$ for every vertex $v$
is the identity map. The _distinguishing chromatic number_ , _${\chi_{D}}(G)$_
††margin:  ${\chi_{D}}(G)$ , is the smallest number of colors in a proper
distinguishing coloring. In a breadth-first (search) spanning tree, _level
$i$_††margin:  level $i$ is the set of vertices at distance $i$ from the root.
We write $\Delta(G)$ for the maximum degree of a graph $G$, and write $\Delta$
when $G$ is clear from context.

The distinguishing chromatic number was introduced by Collins and Trenk [6].
They showed that ${\chi_{D}}(G)\leqslant 2\Delta$ for every connected graph
$G$, with equality only if $G\in\\{K_{\Delta,\Delta},C_{6}\\}$. Further, they
conjectured that no connected graph has ${\chi_{D}}(G)=2\Delta-1$. Laflamme
and Seyffarth [8] confirmed this conjecture for bipartite graphs, with the
exception of $K_{\Delta,\Delta-1}$. For every tree $T$, Collins and Trenk
proved ${\chi_{D}}(T)\leqslant\Delta+1$. Collins, Hovey, and Trenk [5] studied
${\chi_{D}}(G)$ in terms of ${\textrm{Aut}}(G)$, the automorphism group of
$G$. Cavers and Seyffarth [2] characterized graphs $G$ with
${\chi_{D}}(G)\in\\{|V(G)|-1,|V(G)|-2\\}$. Choi, Hartke, and Kaul [4] studied
${\chi_{D}}$ for cartesian products of graphs, and Cheng [3] studied it for
interval graphs.

The goal of this note is to prove Theorem 1, which was conjectured111Through a
minor oversight, the original conjecture did not exclude $C_{6}$. by Collins
and Trenk [6], and proved for bipartite graphs by Alikhani and Soltani [1].

######  Theorem 1.

If $G$ is connected with girth at least 5 and $G\neq C_{6}$, then
${\chi_{D}}(G)\leqslant\Delta+1$.

Theorem 1 is best possible in two ways. First, the star $K_{1,\Delta}$
requires $\Delta+1$ colors. In fact, Collins and Trenk characterized the trees
$T$ for which ${\chi_{D}}(T)=\Delta(T)+1$, and there are an infinite number of
these for each $\Delta$. Thus, we cannot improve the upper bound on
${\chi_{D}}$, even if we require larger girth, or impose some requirement on
$\Delta$. Second, for each $\Delta\geqslant 3$, they constructed infinitely
many graphs $G$ with girth 4, maximum degree $\Delta$, and
${\chi_{D}}(G)=2\Delta-2$. Thus, we cannot relax the girth bound.

######  Key Definition.

Let $G$ be a connected graph of girth at least 5, and $w\in V(G)$. Let $T$ be
a breadth-first spanning tree, rooted at $w$. Let $\sigma$ denote the vertex
order of $T$, and for each $v\in V(G)$, let $\sigma_{v}$ denote the set of
vertices that precede $v$ in $\sigma$. When $\sigma^{\prime}$ is a prefix of
$\sigma$, we often slightly abuse notation by writing $\sigma^{\prime}$ to
mean the set of vertices in that order. Let $\varphi^{\prime}$ be a proper
coloring of the subgraph induced by some $\sigma^{\prime}$. We say _color
greedily_ ††margin:  color greedily , with respect to $\sigma$ and
$\varphi^{\prime}$, to mean that we extend $\varphi^{\prime}$ to a proper
coloring $\varphi$ by coloring each $v\in\sigma\setminus\sigma^{\prime}$ in
order, subject to the following two constraints. (i) If $v$ has a neighbor in
$\sigma_{v}$ (other than its parent), then $\varphi(v)$ is the smallest color
not used on $N(v)\cap\sigma_{v}$. (ii) If $v$ has no neighbor in $\sigma_{v}$
(other than its parent), then $\varphi(v)$ is the smallest color not used on
$\sigma_{v}\cap S_{v}$, where $S_{v}$ consists of the siblings and parent of
$v$.

We begin with the following easy lemma. Its proof draws on ideas from a
similar result in [6], where $G$ has no girth constraint.

######  Lemma 2.

Let $G$ be a connected graph with girth at least 5, and $w\in V(G)$. Let $T$
be a breadth-first spanning tree, rooted at $w$, with vertex order $\sigma$.
Let $\varphi$ be a greedy coloring of $G$, with respect to $\sigma$ and a
coloring $\varphi^{\prime}$ of some non-empty prefix $\sigma^{\prime}$ of
$\sigma$. If $\varphi$ fixes each vertex in $\sigma^{\prime}$, then $\varphi$
is a proper distinguishing coloring.

###### Proof.

By construction, $\varphi$ is proper, so we need only prove that $\varphi$
fixes all vertices. We use induction on $|V(G)|$, at each step considering the
next vertex, $v$, in $\sigma$ that is not known to be fixed, along with all of
its siblings. By assumption $\varphi$ fixes every vertex in $\sigma^{\prime}$.
Consider the first vertex, $v$, that is not yet known to be fixed. By the
induction hypothesis, the parent, $x$, of $v$ is fixed. So, any automorphism
must map $N(x)$ to $N(x)$. Suppose that some sibling $y$ of $v$ has a
neighbor, $z$, that is already colored. Since $z$ is already colored, it comes
before $v$ and $y$ in $T$. So, by the induction hypothesis, $z$ is fixed.
Since $x$ and $z$ are fixed, and $G$ has no 4-cycle, $y$ is also fixed. So all
siblings of $v$ with a non-parent neighbor already colored are fixed. And by
construction each sibling of $v$ without such a neighbor already colored has a
color different from $v$ (or is fixed, since it is in $\sigma^{\prime}$). So
$v$ and all its siblings are fixed, which completes the proof. ∎

Lemma 2 plays a key role in our proof of Theorem 1. To illustrate how we use
it, we first prove a slightly weaker bound.

######  Proposition 3.

If $G$ is connected with girth at least 5, then
$\chi_{D}(G)\leqslant\Delta+2$.

###### Proof.

Choose an arbitrary vertex $w$, and let $T$ be a breadth-first spanning tree
from $w$. Let $\varphi^{\prime}(w)=\Delta+2$, and let
$\sigma^{\prime}=\\{w\\}$. Now we color greedily, with respect to
$\varphi^{\prime}$ and $\sigma$. Note that, except on $w$, this coloring only
uses colors from $\\{1,\ldots,\Delta+1\\}$, since each vertex $v$ must avoid
the colors either (i) on its neighbors, at most $\Delta$, or (ii) on its
parent and siblings, at most $1+(\Delta-1)$. Since $w$ is the only vertex
colored $\Delta+2$, it is fixed. Now $\varphi$ is a proper distinguishing
coloring by Lemma 2. Thus, ${\chi_{D}}(G)\leqslant\Delta+2$. ∎

##  2 Main Result

Before proving our main result, we need an observation about the largest color
possibly used in cases (i) and (ii) of a greedy coloring.

######  Observation 4.

Fix a connected graph $G$ with girth at least 5. Choose an arbitrary $w\in
V(G)$ and breadth-first spanning tree $T$, rooted at $w$. For any prefix
$\sigma^{\prime}$ of $\sigma$, proper coloring $\varphi^{\prime}$ of the
subgraph induced by $\sigma^{\prime}$, and greedy coloring $\varphi$, we have
the following. Each vertex in $V(G)\setminus N(w)$ colored by (i) uses a color
no larger than $\Delta+1$ and uses $\Delta+1$ only if all of its neighbors are
already colored, and all use distinct colors. Each vertex $v\in V(G)\setminus
N(w)$ colored by (ii) uses a color no larger than $\Delta$.

###### Proof.

The first statement is obvious. The second holds since $v$ has at most
$\Delta-2$ siblings. ∎

###### Proof of Theorem 1.

Assume the theorem is false, and $G$ is a counterexample minimizing
$\left|V(G)\right|$.

######  Claim 1.

$G$ has $\Delta\geqslant 3$.

We assume that $\left|V(G)\right|\geqslant 3$, since otherwise the theorem is
trivial. Since $G$ is connected, this implies that $\Delta\geqslant 2$. If $G$
is a path, then we color one end of the path with 1, and the remaining
vertices with 2 and 3 alternating. If $G$ is a cycle, then we color its
vertices (in cyclic order) as $1,2,3,1,2,\ldots$, where the vertices after the
first five alternate colors 3 and 2. It is easy to check that these colorings
are proper and distinguishing, unless $G=C_{6}$.

######  Claim 2.

$G$ is $\Delta$-regular.

Suppose, to the contrary, that $G$ has a vertex, $w$, with degree at most
$\Delta-1$. Let $T$††margin:  $w$, $T$ be a breadth-first spanning tree rooted
at $w$. Color $w$ with $\Delta+1$, then color $\sigma\setminus\\{w\\}$
greedily; call the resulting coloring _$\varphi$_ ††margin:  $\varphi$ . Note
that no other vertex with degree at most $\Delta-1$ uses color $\Delta+1$.
Thus, $w$ is fixed by $\varphi$. Now $\varphi$ is a proper distinguishing
coloring of $G$ by Lemma 2. Thus, ${\chi_{D}}(G)\leqslant\Delta+1$, a
contradiction.

$\Delta+1$$1$$1$$\Delta+1$$w$$x_{1}$$x_{3}$$x$$x_{2}$$y_{1}$ Figure 1: A
partial coloring, constructed in Claim 3.

######  Claim 3.

$G$ has no vertices $w,x,x_{3}$, with $x$ and $x_{3}$ adjacent, such that
${\textrm{dist}}(w,x)\geqslant 3$ and ${\textrm{dist}}(w,x_{3})=3$. In
particular, $G$ has diameter at most 3.

If $G$ has a pair of vertices $w$ and $x$ with ${\textrm{dist}}(w,x)=4$, then
let $x_{3}$ be a neighbor of $x$ on a shortest path from $x$ to $w$. Thus, the
second statement follows from the first. Now we prove the first. Assume the
contrary. Let $wx_{1}x_{2}x_{3}x$††margin:  $w$, $x_{i}$, $x$ be a path with
${\textrm{dist}}(w,x_{i})=i$ for each $i\in\\{1,2,3\\}$ and
${\textrm{dist}}(w,x)\geqslant 3$; see Figure 1. Let _$T$_ ††margin:  $T$ be a
breadth-first spanning tree rooted at $w$, such that each $x_{i}$ is the first
vertex at level $i$ of $T$. Let _$y_{1}$_ ††margin:  $y_{1}$ be the second
child of $w$. Color $T$ greedily except for the following modifications. Color
$w$ and $x_{2}$ with $\Delta+1$, color $x_{1}$ and $y_{1}$ with 1, and color
$x_{3}$ after all of its siblings so that the multiset of colors appearing on
$N(x_{2})$ differs from that appearing on $N(w)$. This final step is possible
because $x$ is uncolored at the time we color $x_{3}$, so we have at least two
options for $x_{3}$. Call the resulting coloring _$\varphi$_ ††margin:
$\varphi$ .

Clearly, $\varphi$ is proper and uses at most $\Delta+1$ colors. We must
verify that $\varphi$ fixes all vertices. The proof uses Lemma 2, so we must
show that $\varphi$ fixes $\sigma^{\prime}$. As in Observation 4, no vertex
other than $w$ and (possibly) $x_{2}$ uses color $\Delta+1$ and also has a
repeated color in its neighborhood. By construction, the multisets of colors
used on $N(x_{2})$ and $N(w)$ differ. Thus, $w$ is fixed. The only children of
$w$ that use a common color are $x_{1}$ and $y_{1}$; so all of its other
children are fixed. Consider a child of $y_{1}$, call it $y_{2}$. If $y_{2}$
is colored by (ii), then $\varphi(y_{2})\leqslant\Delta$, by Observation 4. If
$y_{2}$ is colored by (i), then $y_{2}$ has at most one colored neighbor
(other than $y_{1}$), since $G$ has girth at least 5. Thus,
$\varphi(y_{2})\leqslant 3\leqslant\Delta$. So $x_{1}$ has a neighbor (other
than $w$) colored $\Delta+1$, but $y_{1}$ has no such neighbor. Hence, $x_{1}$
and $y_{1}$ are fixed. Let $\sigma^{\prime}$ be the prefix of $\sigma$ ending
with $x_{2}$ and $\varphi^{\prime}$ the restriction of $\varphi$ to the
subgraph induced by $\sigma^{\prime}$. Now Lemma 2 implies that all vertices
are fixed, so $\varphi$ is a proper distinguishing coloring using at most
$\Delta+1$ colors, a contradiction.

$1$$\Delta+1$$2$$\Delta+1$$3$$4$$3$$2$$1$$3$$1$$w$$x_{1}$$y_{1}$$z_{1}$$x_{2}$$y_{2}$$z_{2}$$z_{3}$
Figure 2: A partial coloring, constructed in Claim 4.

######  Claim 4.

$G$ has diameter 2 or $\Delta=3$.

Suppose, to the contrary, that $\Delta\geqslant 4$ and $G$ has diameter at
least 3. Claim 3 implies that $G$ has diameter at most 3, so assume $G$ has
diameter 3. Choose $w,z_{1},z_{2},z_{3}\in V(G)$††margin:  $w$, $z_{i}$, $T$
such that $wz_{1}z_{2}z_{3}$ is a path and ${\textrm{dist}}(w,z_{i})=i$ for
each $i\in\\{1,2,3\\}$. Let _$T$_ be a breadth-first spanning tree rooted at
$w$. Each $z_{i}$ is at level $i$ in $T$. Further, by Claim 3, every neighbor
of $z_{3}$ is at level 2 in $T$. Choose $x_{1},x_{2},y_{1},y_{2}\in
V(G)$††margin:  $x_{i}$, $y_{i}$ such that $wx_{1}x_{2}z_{3}$ and
$wy_{1}y_{2}z_{3}$ are paths, and $x_{1},x_{2},y_{1},y_{2},z_{1},z_{2}$ are
distinct; see Figure 2. After possibly reordering some siblings, we can assume
that $x_{1}$, $y_{1}$, and $z_{1}$ are (respectively) the first, second, and
third children of $w$. We can also assume that $z_{2}$ is the first child of
$z_{1}$ and that $z_{3}$ is the last child of $z_{2}$ (even though $z_{3}$
would naturally be a child of $x_{2}$). Further, we assume $x_{2}$ and $y_{2}$
are the second children, respectively, of $x_{1}$ and $y_{1}$. Finally, by
reordering children of $y_{1}$ if needed, we assume that $z_{2}$ is not
adjacent to the first child of $y_{1}$. Since $\Delta\geqslant 4$ (and $G$ has
girth at least 5), $y_{1}$ has at least 3 children; one of these is $y_{2}$
and at most one is adjacent to $z_{2}$, since $G$ has no 4-cycle. Similarly,
we assume that $y_{2}$ is not adjacent to the first child of $x_{1}$.

Begin by coloring $w$ with $1$ and coloring $x_{1}$ and $z_{1}$ with
$\Delta+1$. We greedily color the rest of $T$ except for the following
modifications; none of these change the order of the vertices, only our choice
of color for a vertex when we reach it in the order. No child of $x_{1}$ uses
color 1 (so its children use colors $2,\ldots,\Delta$). Vertex $z_{2}$ uses 1
and no other child of $z_{1}$ uses 1. (If such a child, say _$z_{2}^{\prime}$_
††margin:  $z_{2}^{\prime}$ , has no colored neighbor other than $z_{1}$, then
this happens naturally as a result of a greedy coloring, since $z_{2}$ uses 1.
If $z_{2}^{\prime}$ does have a colored neighbor other than $z_{1}$, then it
has at most two: one child of $x_{1}$ and one child of $y_{1}$, since $G$ has
no 4-cycles. Since $\Delta\geqslant 4$, $z_{2}^{\prime}$ has some available
color from among $\\{2,3,4\\}$ that is not already used on any of its
neighbors, so $z_{2}^{\prime}$ can avoid 1; recall that $z_{1}$ uses
$\Delta+1>4$, so $z_{1}$ does not forbid a color in $\\{2,3,4\\}$.) Note that
$x_{2}$ and $y_{2}$ both use 3. When we color $z_{3}$ (as the last child of
$z_{2}$), we do so to ensure that the multisets of colors used on $N(w)$ and
$N(z_{2})$ differ; this is possible because $x_{2}$ and $y_{2}$ use the same
color, so $z_{3}$ has at least two available colors. Further, if possible, we
also require that $z_{3}$ not use color $\Delta+1$; so $z_{3}$ uses $\Delta+1$
only if all of its neighbors use distinct colors, except for $x_{2}$ and
$y_{2}$, which both use 3. Call the resulting coloring _$\varphi$_ ††margin:
$\varphi$ .

Now we show that $\varphi$ fixes all vertices. Since $\varphi(z_{2})=1$,
vertex $z_{1}$ is the unique vertex colored $\Delta+1$ with at least two
neighbors colored 1, by Observation 4. Thus $z_{1}$ is fixed. By design, no
child of $z_{1}$ other than $z_{2}$ uses color 1. By our choice of color for
$z_{3}$, the multisets of colors on $N(w)$ and $N(z_{2})$ differ. Thus, $w$ is
fixed and $z_{2}$ is fixed. Since we already know $z_{1}$ is fixed, each
neighbor of $w$ is fixed. Now, as in the proof of Lemma 2, by induction, we
show for each vertex in $N(w)$ that its children are fixed. Finally, consider
a vertex, $u$, at level 3 of $T$. By Claim 3, each neighbor of $u$ is at level
2\. Thus, since $G$ has no 4-cycle and $u$ has at least 2 fixed neighbors, $u$
is fixed. So ${\chi_{D}}(G)\leqslant\Delta+1$, a contradiction.

######  Claim 5.

$G$ has $\Delta=3$.

Suppose that $\Delta\geqslant 4$. By Claim 4, $G$ has diameter 2. Since $G$ is
$\Delta$-regular with diameter 2 and girth 5, we know that
$\left|V(G)\right|=\Delta^{2}+1$. Choose an arbitrary vertex $w$††margin:
$w$, $G^{\prime}$ , and let $G^{\prime}=G\setminus\\{w\cup N(w)\\}$. Note that
$G^{\prime}$ is regular, with degree $\Delta(G)-1$. Since $G$ has diameter 2,
for each $v_{1},v_{2}\in V(G^{\prime})$, if $v_{1}$ and $v_{2}$ have no common
neighbor (in $G$) among $N(w)$, then
${\textrm{dist}}_{G^{\prime}}(v_{1},v_{2})\leqslant 2$. This implies that
$G^{\prime}$ is connected. Since $\Delta(G)-1\geqslant 3$, by the minimality
of $G$ we know that
${\chi_{D}}(G^{\prime})\leqslant\Delta(G^{\prime})+1=\Delta(G)$; let
_$\varphi^{\prime}$_ ††margin:  $\varphi^{\prime}$ be a coloring of
$G^{\prime}$ showing this. To extend $\varphi^{\prime}$ to $G$, use color
$\Delta(G)+1$ on each vertex in $N(w)$ and use an arbitrary color (other than
$\Delta(G)+1$) on $w$; we call this coloring _$\varphi$_ ††margin:  $\varphi$
. Clearly $w$ is fixed by $\varphi$, since each other vertex has at most one
neighbor colored $\Delta(G)+1$. Further, each vertex of $G^{\prime}$ is fixed
by $\varphi^{\prime}$, so we get that each vertex of $G^{\prime}$ is fixed by
$\varphi$. Finally, each vertex $v\in N(w)$ has all of its neighbors fixed by
$\varphi$. Since $G$ has no 4-cycles, $v$ is also fixed by $\varphi$. Thus,
${\chi_{D}}(G)\leqslant\Delta(G)+1$, a contradiction.

######  Claim 6.

$G$ is either bipartite or vertex-transitive.

Suppose there exist vertices _$w,x_{1},y_{1}$_ ††margin:  $w,x_{1},y_{1}$ with
$x_{1},y_{1}\in N(w)$ and no automorphism maps $x_{1}$ to $y_{1}$. Let _$T$_
††margin:  $T$ be a breadth-first spanning tree, rooted at $w$, with $x_{1}$
and $y_{1}$ as the first children of $w$ in $T$. Color $w$ with $\Delta+1$,
color $x_{1}$ and $y_{1}$ with 1, and color the rest of $T$ greedily. Now $w$
is fixed, since it is the only vertex colored $\Delta+1$ with two neighbors
colored 1. Vertices $x_{1}$ and $y_{1}$ are fixed, since no automorphism maps
one to the other, and all other neighbors of $w$ are fixed, since they receive
distinct colors. All remaining vertices are fixed by Lemma 2. So
${\chi_{D}}(G)\leqslant\Delta+1$, a contradiction.

Instead, assume that for every vertex $w$ and $x_{1},y_{1}\in N(w)$††margin:
$w$, $x_{1}$, $y_{1}$ some automorphism maps $x_{1}$ to $y_{1}$. Thus, for
each pair of vertices $x_{1},y_{1}$ joined by a walk of even length, some
automorphism maps $x_{1}$ to $y_{1}$ (the proof is by induction on the length
of the walk). If $G$ is bipartite, we are done; so assume it is not. Let _$C$_
††margin:  $C$ be an odd cycle in $G$. Since $G$ is connected, for every pair
of vertices $x_{1},y_{1}\in V(G)$, there exists an $x_{1},y_{1}$-walk of even
length. Consider a walk from $x_{1}$ to $y_{1}$ that visits $C$. If the walk
has odd length, then we extend it by going around $C$ once. Thus, $G$ is
vertex-transitive, as desired.

######  Claim 7.

$G$ is either the Petersen graph or the Heawood graph; see Figure 3.

Recall that $G$ is 3-regular, by Claims 2 and 5. Choose an arbitrary vertex
$w$, and let $T$††margin:  $w$, $T$ be a breadth-first spanning tree rooted at
$w$. Since $G$ has girth at least 5, the number of vertices at level 2 is
$3(3-1)=6$. By Claim 3, $G$ has diameter at most 3, so any additional vertices
of $G$ are at level 3. Further, by Claim 3, no pair of vertices at level 3 are
adjacent. So each vertex at level 3 has all three of its neighbors at level 2.
Since each of the 6 vertices at level 2 has at most two neighbors at level 3,
the number of vertices at level 3 is at most $\frac{2}{3}(6)=4$. Thus,
$\left|V(G)\right|\leqslant 1+3+6+4=14$. If $G$ has girth at least 6, then $G$
must be the Heawood graph, since it is the unique 3-regular graph with girth
at least 6 and at most 14 vertices. Otherwise, $G$ has a 5-cycle. So Claim 6
implies that $G$ is vertex-transitive.

To finish, we simply check that the only 3-regular vertex-transitive graphs
with girth at least 5 and at most 14 vertices are the Petersen graph and the
Heawood graph. A convenient reference to verify this is [9], which catalogues
all vertex-transitive graphs on at most 19 vertices.

$2$$1$$2$$4$$3$$2$$4$$2$$3$$1$$2$$3$$2$$3$$2$$1$$2$$1$$4$$3$$2$$1$$2$$4$
Figure 3: Proper distinguishing 4-colorings of the Petersen graph and Heawood
graph.

######  Claim 8.

$G$ does not exist.

Consider the 4-colorings in Figure 3 of the Petersen graph (left) and Heawood
graph (right). Clearly, both colorings are proper. In the coloring of the
Petersen graph, every two vertices with the same color have distinct multisets
of colors on their neighborhoods. Thus, the coloring is distinguishing.

Now consider the coloring of the Heawood graph. The vertices colored 4 are
fixed, since the multisets on their neighborhoods differ. The same is true for
the vertices colored 2, except for two with the multiset $\\{1,1,3\\}$. But
for exactly one of these vertices the neighbor colored 3 has a neighbor
colored 4. Thus, the vertices colored 2 are fixed. Now every other vertex has
at least two neighbors fixed. Since $G$ has no 4-cycles, every vertex is
fixed. So the coloring is distinguishing. This proves claim 8, which finishes
the proof of Theorem 1. ∎

We conclude with a few remarks. The _distinguishing list chromatic number_ ,
_${\chi_{D}^{\ell}}(G)$_ ††margin:  ${\chi_{D}^{\ell}}(G)$ , is the smallest
$k$ such that given any list assignment $L$ with $\left|L(v)\right|\geqslant
k$ for all $v\in V(G)$, there exists a proper distinguishing coloring
$\varphi$ of $G$ such that $\varphi(v)\in L(v)$ for all $v\in V(G)$. In
general, ${\chi_{D}^{\ell}}(G)$ can be much larger than ${\chi_{D}}(G)$. For
example, form a graph $G$ from $K_{1000,1000}$ by adding a pendant edge at
each vertex and subdividing these edges so the resulting paths have distinct
lengths. The only automorphism of $G$ is the identity, so
${\chi_{D}}(G)=\chi(G)=2$. However, ${\chi_{D}^{\ell}}(G)$ is at least the
list-chromatic number, which is greater than 2 (and grows arbitrarily large on
complete bipartite graphs). In contrast, we note that the bound on
${\chi_{D}}$ in Proposition 3 also holds for ${\chi_{D}^{\ell}}$.

######  Proposition 5.

If $G$ is connected with girth at least 5, then
${\chi_{D}^{\ell}}(G)\leqslant\Delta+2$.

###### Proof.

The proof is nearly identical to that of Proposition 3. We choose an arbitrary
vertex $w$, choose $\alpha\in L(w)$, color $w$ with $\alpha$ and let
$L^{\prime}(v)=L(v)-\alpha$ for every other vertex $v$. Now find a breadth-
first spanning tree, $T$, rooted at $w$, and color greedily from $L^{\prime}$
with respect to $\sigma$. It is straightforward to check that the proof of
Lemma 2 still holds in this more general setting. ∎

######  Observation 6.

All proofs in this paper are constructive, and imply algorithms to find the
colorings, and these algorithms can be easily implemented to run in polynomial
time.

###### Proof.

We can easily check that a graph is regular, and compute a breadth-first
spanning tree. To determine diameter, we use an algorithm for all-pairs
shortest path. In general, computing the automorphisms of a graph can be
difficult. However, we only need to do this for graphs on at most 14 vertices,
so we can finish in constant time, simply considering every possible map from
$V(G)$ to $V(G)$, and checking whether it is an automorphism. ∎

######  Question 9.

When $G$ is connected with girth at least 5, is
${\chi_{D}^{\ell}}(G)\leqslant\Delta+1$?

Two extensions of list chromatic number are online list chromatic number,
denoted $\chi^{OL}$, and correspondence chromatic number, denoted
$\chi^{corr}$; see [10] and [7] for the definitions. When we require also that
our colorings be distinguishing, we get the parameters $\chi^{OL}_{D}$ and
$\chi^{corr}_{D}$. It is natural to study the maximum values of these
parameters on certains classes of graphs. In particular, what are the maximum
values on connected graphs with girth at least 5? Does the bound of
Proposition 5, or even Question 9, still hold?

### Acknowledgments

The author is grateful for his support by NSA grant H98230-16-0351. He also
thanks Howard Community College for its hospitality during the preparation of
this paper.

## References

  * [1] Saeid Alikhani and Samaneh Soltani.  The distinguishing chromatic number of bipartite graphs of girth at least six.  Algebraic Structures and their Applications, 3(2):81–87, Winter and Spring 2016.  Available at http://as.yazd.ac.ir/article_1061.html.
  * [2] Michael Cavers and Karen Seyffarth.  Graphs with large distinguishing chromatic number.  Electron. J. Combin., 20(1):Paper 19, 1–17, 2013.  Available at http://www.combinatorics.org/v20i1p19.
  * [3] Christine T. Cheng.  On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results.  Discrete Math., 309(16):5169–5182, 2009.  Available at https://www.sciencedirect.com/science/article/pii/S0012365X09001836.
  * [4] Jeong Ok Choi, Stephen G. Hartke, and Hemanshu Kaul.  Distinguishing chromatic number of Cartesian products of graphs.  SIAM J. Discrete Math., 24(1):82–100, 2010.
  * [5] Karen L. Collins, Mark Hovey, and Ann N. Trenk.  Bounds on the distinguishing chromatic number.  Electron. J. Combin., 16(1):Research Paper #88, 1–14, 2009.  Available at http://www.combinatorics.org/v16i1r88.
  * [6] Karen L. Collins and Ann N. Trenk.  The distinguishing chromatic number.  Electron. J. Combin., 13(1):Research Paper #16, 1–19, 2006.  Available at http://www.combinatorics.org/v13i1r16.
  * [7] Zdeněk Dvořák and Luke Postle.  Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8.  J. Combin. Theory Ser. B, 129:38–54, 2018.  Preprint available at https://arxiv.org/abs/1508.03437.
  * [8] Claude Laflamme and Karen Seyffarth.  Distinguishing chromatic numbers of bipartite graphs.  Electron. J. Combin., 16(1):Research Paper #76, 1–15, 2009.  Available at http://www.combinatorics.org/v16i1r76/pdf.
  * [9] Brendan D. McKay.  Transitive graphs with fewer than twenty vertices.  Math. Comp., 33(147):1101–1121, loose microfiche suppl, 1979.  Available at http://www.ams.org/journals/mcom/1979-33-147/S0025-5718-1979-0528064-2/.
  * [10] Xuding Zhu.  On-line list colouring of graphs.  Electron. J. Combin., 16(1):Research Paper #127, 1–16, 2009.  Available at http://www.combinatorics.org/v16i1r127.