# Multiplexed random-access optical memory in warm cesium vapor

Leon Meßner<EMAIL_ADDRESS>Institut für Physik, Humboldt-
Universität zu Berlin, Newtonstr. 15, 12489 Berlin, Germany.  Deutsches
Zentrum für Luft- und Raumfahrt e.V. (DLR), Institute of Optical Sensor
Systems, Rutherfordstr. 2, 12489 Berlin, Germany.  Elizabeth Robertson
Deutsches Zentrum für Luft- und Raumfahrt e.V. (DLR), Institute of Optical
Sensor Systems, Rutherfordstr. 2, 12489 Berlin, Germany.  Technische
Universität Berlin, Institut für Optik und Atomare Physik, Str. des 17 Juni
135, 10623 Berlin, Germany  Luisa Esguerra  Deutsches Zentrum für Luft- und
Raumfahrt e.V. (DLR), Institute of Optical Sensor Systems, Rutherfordstr. 2,
12489 Berlin, Germany.  Technische Universität Berlin, Institut für Optik und
Atomare Physik, Str. des 17 Juni 135, 10623 Berlin, Germany  Kathy Lüdge
Technische Universität Ilmenau, Institut für Physik, Weimarer Straße 25, 98693
Ilmenau, Germany  Janik Wolters  Deutsches Zentrum für Luft- und Raumfahrt
e.V. (DLR), Institute of Optical Sensor Systems, Rutherfordstr. 2, 12489
Berlin, Germany.  Technische Universität Berlin, Institut für Optik und
Atomare Physik, Str. des 17 Juni 135, 10623 Berlin, Germany

###### Abstract

The ability to store large amounts of photonic quantum states is regarded as
substantial for future optical quantum computation and communication
technologies. However, research for multiplexed quantum memories has been
focused on systems that show good performance only after an elaborate
preparation of the storage media. This makes it generally more difficult to
apply outside a laboratory environment. In this work, we demonstrate a
multiplexed random-access memory to store up to four optical pulses using
electromagnetically induced transparency in warm cesium vapor. Using a
$\Lambda$-System on the hyperfine transitions of the Cs D1 line, we achieve a
mean internal storage efficiency of 36% and a $1/\textrm{e}$ lifetime of 3.2
µs. In combination with future improvements, this work facilitates the
implementation of multiplexed memories in future quantum communication and
computation infrastructures.

##  I Introduction

Quantum memories are considered to be a main component for the realization of
many future second generation quantum technologies. Their potential use ranges
from synchronizing inputs into various types of quantum systems Heshami  _et
al._ (2016) to re-configurable optical reservoir computing Jaurigue  _et al._
(2021). They enable on-demand operation of otherwise probabilistic single-
photon sources and quantum gates Finkelstein  _et al._ (2018), which will
significantly enhance their rate of operation Bhaskar  _et al._ (2020).
Moreover, they have been identified as an essential device required to realize
a quantum repeater Briegel  _et al._ (1998), a key technology needed for long-
distance quantum communication. When specifically considering the
implementation of a global quantum communication network, satellite based
quantum communication has been hallmarked as a most promising system if
enhanced with a multiplexed quantum memory. It has been shown that a
significant increase in communication rate is already achievable with around
1000 randomly accessible storage modes Gündoğan  _et al._ (2021); Wallnöfer
_et al._ (2022). Consequently, the realization of suitable multiplexed quantum
memories will be an important milestone in extending quantum communication
over long distances.

Quantum memories have been demonstrated using a variety of storage protocols
in a number of single emitter and ensemble-based matter systems. These include
solid state systems, ultra-cold atoms and warm atomic vapors Heshami  _et al._
(2016). Although the routine formation of subnanokelvin Bose-Einstein
condensates in earth’s orbit has been demonstrated Aveline  _et al._ (2020)
and is pursued in future projects Frye  _et al._ (2021), reducing the
technological requirements for space-borne quantum memories is a key step.
This makes memories based on warm atomic vapors favored for applications, as
they require no vacuum, laser cooling or strong magnetic fields.

The memory used in this experiment utilizes the effect of electromagnetically
induced transparency (EIT) on the $\Lambda$-system composed by the
$6^{2}S_{1/2}F{=}3,F{=}4$ and the $6^{2}P_{1/2}F{=}3$ atomic hyperfine levels
of an ensemble of cesium atoms to map optical excitations to a long-lived
spin-wave, i.e. a coherence of the two hyperfine ground states of the atomic
ensemble Fleischhauer, Imamoglu, and Marangos (2005a); Gorshkov  _et al._
(2007). Due to its coherent ensemble origin, this spin-wave shows
comparatively low dephasing and loss. Subsequent retrieval of the spin-wave
excitation into the input optical mode can then be performed at some chosen
time that is smaller than the spin-wave lifetime. Light storage for up to 1 s
Katz and Firstenberg (2018) and single-photon operation Esguerra  _et al._
(2022); Buser  _et al._ (2022) have been demonstrated in separate experiments
in warm atomic vapors.

For a quantum memory to be most useful within a quantum communication system,
the memory must be scaleable with the possibility to access individual storage
modes in a way that is not significantly limited by the used technology.
Various forms of quantum memory multiplexing have been studied in the past,
including time bin Usmani  _et al._ (2010), orbital angular momentum Ding  _et
al._ (2015), and spatial Langenfeld  _et al._ (2020); Li  _et al._ (2021)
multiplexing. Among these approaches, Ref. Li  _et al._ (2021) shows a clear
foreseeable path to achieving the required number of 1000 randomly accessible
modes. However, the technological overhead of a cold atom setup complicates
operating these outside of a laboratory. In this work we demonstrate a memory
that combines the advantages of using warm vapor with a path towards scaleable
multi-rail operation.

##  II Experiment

Figure 1: Memory scheme. a) Scheme of the Cs D1 energy levels’ hyperfine
structure that forms the $\Lambda$-system used. Signal and control fields are
red detuned from resonance by $\Delta$ and have angular frequencies
$\omega_{\textrm{s}}$ and $\omega_{\textrm{c}}$ respectively. The transition
$F=4\rightarrow F^{\prime}=4$ is resonantly driven by the pump field with
angular frequency $\omega_{\textrm{p}}$. b) Time traces from an experiment for
writing a signal pulse onto an atomic spin-wave at time $t_{0}=0$ and
retrieving it at $t_{0}+0.4~{}\textrm{\textmu s}$. The bottom panel shows the
operation performed on the memory (W: write, R: read).

The multi-rail memory presented here uses an EIT memory scheme Fleischhauer,
Imamoglu, and Marangos (2005b) on the hyperfine ground state transitions of
the Cs D1 line, as shown in Fig. 1(a). The control and signal lasers (14-pin
butterfly external cavity diode laser (ECDL) modules by Sacher Lasertechnik)
are set on the $F{=}4\rightarrow F^{\prime}{=}3$ and the $F{=}3\rightarrow
F^{\prime}{=}3$ transitions respectively. To stabilize the frequency
difference between signal and control laser to the Cs ground state hyperfine
splitting, light from both lasers is superimposed on a fast photodiode
(Electro Optics Technology, ET-3500FEXR) and their beat frequency is offset
locked Schünemann  _et al._ (1999) using a RedPitaya FPGA-board running the
Linien Wiegand  _et al._ (2022) locking software. We generate Gaussian signal
and control pulses with a full width at half maximum (FWHM) of 25 ns and 43.75
ns respectively using an arbitrary function generator (AFG, Tek AFG31152).
These pulses are modulated onto cw laser beams with electro-optic amplitude
modulators (EOMs, Jenoptik AM905). The experiment is designed such that the
signal and control pulses have linear and orthogonal polarization to each
other to reduce the control light leaking into the detection path.

The atomic storage medium is confined to a cylindrical, 25x75 mm anti-
reflection coated cesium vapor cell filled with 5 torr N2 of buffer gas. It is
kept at 60°C and shielded from ambient magnetic fields by a double-layered mu-
metal housing. Spatial addressing of different rails within the cell is
performed by one acousto-optic deflector (AOD) in front and one behind the
vapor cell. The AODs (AA MT200-B100A0,5-800) have an aperture of 0.5x2
$\textrm{mm}^{2}$ and a measured deflection of 0.2 mrad/MHz. Each of them is
driven by the frequency sum of an arbitrary function generator (AFG, Tek
AFG31152) and a local oscillator (Mini-Circuits, ZOS-300+) resulting in
200$\pm$50 MHz of carrier frequency. We refer to the position of memory rails
by the AOD driving frequency used to deflect the beam to that position; the
distance between rails is thus expressed as the difference in driving
frequency. Changing the AOD driving frequency by 8 MHz changes the lateral
position of the deflected beam by 270 µm, equaling one signal beam radius.

Figure 2: Sketch of the experiment with A) laser sources, spectroscopy and
optical pulse shaping, B) TA based pulse amplification, C) multi-rail storage
system and D) CCD image of the four used rails, with the camera at the place
of the Cs cell. HWP: half-wave plate, QWP: quarter-wave plate, DET: detector,
(P)BS: (polarizing) beam splitter, L1;L2/L3: aspheric/cylindrical lens, AOD:
acousto-optic deflector, EOM: electro-optic modulator, AFG: arbitrary function
generator, IF: interference filter, OL: offset lock.

While the signal pulses enter the memory unmodified after their generation,
the control laser pulses are amplified by a self-made tapered amplifier (TA,
see Schkolnik (2017)) and then spectrally filtered by a dielectric bandpass
interference filter (IF) with a 1 nm FWHM. This results in 200 mW of coupled
cw power. To increase the control laser’s on-off ratio, the TA diode’s driving
current is only switched on for 120 ns, centered on the optical pulse, using a
4 A dc-coupled input follower driver with 2 ns rise/fall time. This reduces
the unwanted interaction between control laser and atoms in times when no
control pulse is generated.

The beam paths of the cross-polarized signal and control lasers are overlapped
at a polarizing beam splitter (PBS) on one side of the memory and then
propagate collinearly through the cesium cell, and both AODs. At the position
of the cell, control and signal beam have a $1/e^{2}\textrm{-level}$ radius of
350 µm and 270 µm respectively. This yields an atomic transit time of $\Delta
t=3.7~{}\textrm{\textmu s}$ for one signal beam radius when using a 2D
diffusion model of $\Delta x=\sqrt{4D\Delta t}$ for the diffusion length and
an assumed diffusion constant of $D_{0}=0.24~{}\textrm{cm}^{2}\textrm{s}^{-1}$
Thomas  _et al._ (2017) at $T_{0}=0~{}\textrm{K}$ and
$P_{0}=760~{}\textrm{torr}$. After traversing the second AOD, the signal and
control beams are split by a second PBS and are then individually coupled to
fibers and detected by either a Si photodiode (Thorlabs DET10A2) or a Si
avalanche photodiode (Menlo Systems APD210).

Optical pumping of the Cs atoms into the $6^{2}S_{1/2}F{=}3$ state is
performed by a third ECDL laser locked to the $6^{2}S_{1/2}F{=}4\rightarrow
6^{2}P_{1/2}F{=}4$ transition by saturated absorption spectroscopy. The pump
light power is controlled via transmission through an electrically pulsed
semiconductor optical amplifier (SOA) and illuminates each memory rail with 20
mW of optical power for 900 ns prior to the memory experiment sequence.

Figure 1(b) shows a typical time trace for a single-rail storage experiment
and a sketch of the experimental setup can be seen in Fig. 2. Several features
of storage within an EIT medium can be observed in the time trace. At
$t=0~{}\textrm{\textmu s}$ a signal pulse enters the atomic medium and is
partly mapped to an atomic spin wave by the control laser field. The portion
of that signal pulse that is transmitted through the atomic vapor is detected
by the photodiode as leakage. After $0.4~{}\textrm{\textmu s}$ the control
laser field is switched on again and retrieves the spin-wave excitation back
into the signal beams optical mode. A third pulse of the control laser at
$t=0.8~{}\textrm{\textmu s}$ serves to determine if all the excitation has
been retrieved and also allows to estimate the signal noise induced by the
control laser field. Not having a significant detection event during this last
pulse, we conclude that nearly all the spin-wave excitation is mapped backed
to optical and signal to noise ratio is not a limiting factor for this
experiment with aforementioned laser pulses.

##  III Results

Prior to performing multi-rail storage, we first identify optimal operating
conditions for the multi-rail memory by assessing the influence of rail
separation on the interactions between two memory rails, and subsequently
minimizing the cross-talk. For comparison of the single and multi-rail
operation, we measure the 1/e lifetime and memory efficiency per rail.

To assess the influence of rail separation on their interaction, multiple
storage experiments at different rail separations are conducted. For effective
operation of a memory, we require that operations on a given memory rail do
not affect its neighbors. To determine the minimal separation that shows no
cross-talk, we write into a rail fixed at 190 MHz, read from a neighboring
rail, and then read from the 190 MHz rail again.

Figure 3: Cross-talk estimation. Intensities detected in the first (Peak 1,
orange rail) and second (Peak 2, green rail) read peak depending on the rail
separation for the experiment sequence depicted in the inset. For a difference
of 20 MHz in AOD driving frequency (rail separation), the influence between
neighboring rails vanishes. The inset shows the used experiment sequence
consisting of a write on the green rail at $t=0$, a read on a neighboring
orange rail at $t=0.4~{}\textrm{\textmu s}$ and finally a read on the green
rail at $t=0.8~{}\textrm{\textmu s}$.

This write/read/read sequence is depicted in the inset of Fig. 3. The rail
separation is varied from 0 to 25 MHz at steps of 1 MHz, and the retrieval
peak intensities after the first and second read are measured. The results are
depicted in Fig. 3. Below 5 to 8 MHz of separation no excitation is left for
the second retrieval pulse and both read pulses address the same ensemble of
atoms. At a separation of 20 MHz the influence of the read operation on the
neighboring rail is no longer visible.

The AOD device used has a 100 MHz bandwidth and a 25% reduced diffraction
efficiency at the edges of the frequency range; consequently we chose to limit
this experiment to four memory rails spaced by 20 MHz. A CCD image of the four
rails, taken at the position of the Cs cell, is shown in Fig. 2(D). A
straightforward method to increase the number of rails, is to use AODs with a
higher number of resolvable spots.

The 1/e storage lifetime per rail is determined by performing storage
experiments with increasing time delay between the memory write and read
operation, for each rail. The delay was varied between 0.4 µs and 11.2 µs in
steps of 400 ns, and for each delay, we measure the retrieved peak
intensities, averaged over 500 repetitions. Uncertainties are given by the
standard deviation of the intensities. The intensities were fitted with an
exponential function to extract the 1/e lifetime. Measured retrieval peak
intensities and fit function are displayed in Fig. 4.

Figure 4: Measured retrieval amplitudes for storage times between 0.4 and 11.4 µs together with an exponential fit to the values. The inset shows the per rail 1/e storage lifetime deduced from the fit. Rail (MHz) | 170 | 190 | 210 | 230 | Mean
---|---|---|---|---|---
Lifetime (µs) | 4.3(5) | 5.4(7) | 3.3(3) | 2.6(3) | 3.2(2)
Efficiency (%) | 32 | 35 | 39 | 36 | 36
Table 1: Measured 1/e-lifetime and retrieval efficiency for each rail and
weighted mean.

The resulting lifetime values per rail are shown in Table 1 together with the
achieved internal memory efficiencies $\eta_{\textrm{mem}}$ at $t=0$.

Since the measured lifetimes are consistent with the estimate using the simple
diffusion model presented earlier, it is reasonable to assume that diffusion
is the most important lifetime-limiting process for the beam diameters chosen
in this work.

Independent investigation on a single rail setup also showed that spin
polarization lifetimes at least on the order of several hundred microseconds
are possible with larger beam diameters.

The memory efficiencies are calculated by extrapolating the pulse energy of a
retrieved pulse after $t=0~{}\textrm{\textmu s}$ of storage from a retrieved
pulse after $t=0.4~{}\textrm{\textmu s}$ of storage using the memory lifetime.
This is then divided by the energy of a normalization pulse to yield the
efficiency. To obtain the normalization pulse, we set the signal laser
frequency 2 GHz below the $F{=}3\rightarrow F^{\prime}{=}3$ transition
frequency, block the control beam and record the transmitted signal pulse.
Under these conditions, we assume the pulses not to be absorbed by the atoms.

Using the insights and results from the measurements on lifetime, efficiency
and rail separation, we now explore the possibility of random-access operation
in the memory setup. For this purpose an experimental sequence was designed
that highlights important criteria for use as a random-access quantum memory.
Figure 5 illustrates this experiment.

Figure 5: Storage experiment in the random-access memory using four rails with
detected intensity in the signal path in the top and performed operations
(read/write) in the bottom panel. A total of 12 operations are performed over
a span of 5 µs.

The bottom panel depicts the operation performed on each specific rail and the
top panel shows the intensity detected by the APD over a time span of about 5
µs. The experimental sequence contains 12 operations, either read (r) or write
(w). We define three features which are necessary for use as a memory: a) that
reading or writing to a rail should not affect its neighbors (interaction-
free), b) rails which have not been written to should not return a retrieved
pulse (empty state) and c) a read should leave the memory empty; a subsequent
read pulse should yield no excitation (full retrieval).

Interaction-free operation is ensured by choosing an adequate rail separation
and then confirmed by looking at the storage performance of a specific rail
while there are operations performed on the neighboring rails. The rails at
230 MHz (blue) and 190 MHz (green) can be used to show that operations are
interaction free. Between the write ($t=1.6~{}\textrm{\textmu s}$) and read
($t=3.6~{}\textrm{\textmu s}$) operation on the 190 MHz rail, four operations
are performed on the neighboring rails and there is no visible impact on the
read peak shape or height. On the 230 MHz rail a pulse is written at $t=0$ and
then retrieved during the last operation on the memory at
$t=4.4~{}\textrm{\textmu s}$. Taking into account the 2.6 µs lifetime of this
rail, the high remaining intensity of the retrieval peak clearly shows that
there is no significant detrimental influence from multi-rail operation.

Reading an empty rail should not result in a significant amount of intensity.
We verify this by reading the 210 MHz and 170 MHz rail in a state that should
not have excitation. In the 210 MHz rail a pulse is written to the memory at
$t=0.4~{}\textrm{\textmu s}$ and then this rail is immediately read twice. The
second read operation at $t=0.8~{}\textrm{\textmu s}$ yields negligible
intensity compared to the first read operation at 0.6 µs. Additionally the
same rail is read again at 3.2 µs to observe the amount of noise, which is
found to be comparable to the read at 1.2 µs. The first operation on the 190
MHz rail at $t=2~{}\textrm{\textmu s}$ is a read of a rail that has not been
used before. This allows us to determine how well the memory was initialized
by the pumping that is performed prior to the experimental sequence. Observing
a larger intensity peak would point to insufficient polarization of the
medium. As the observed peak is similar to the other reads of an empty rail
mentioned above, we conclude that pumping is sufficient and reading an empty
rail, regardless of its history, does not lead to the detection of a
significant peak. In combination with the measurements on lifetime and rail
interaction it follows that this setup allows random-access storage and
retrieval of optical pulses for times comparable to the mean rail lifetime of
3.2 µs.

##  IV Conclusion

We have presented a multiplexed optical random-access memory, realised within
a single vapor cell at a temperature of 60°C. Using an EIT based storage
scheme in a $\Lambda$-system on the cesium hyperfine transitions, we achieved
a mean storage lifetime and internal efficiency of 3.2(2) µs and 36%
respectively in multi-rail operation. According to the chosen rail separation
of 20 MHz, we performed random-access storage and retrieval in four parallel
rails without observing reciprocal influence between the different rails.

The time between successive operations was chosen to be 400 ns for the sake of
simplifying experiment control. This time could be reduced considerably with
the lower bound determined by the AODs switching time of 48 ns. Increasing the
storage lifetime and number of addressable rails is possible by increasing the
beam diameters and using AODs that have a higher time-bandwidth product
respectively. This step will be important for applications in quantum
communication and repeater networks. Reaching beyond the threshold number of
1000 individually addressable modes is possible by using 2-axis AODs and
multiplexing into a two dimensional grid of parallel storage modes.

## Funding

This work was funded by the Deutsche Forschungsgemeinschaft (DFG, German
Research Foundation) – Project number 445183921. E.R. acknowledges funding
through the Helmholtz Einstein International Berlin Research School in Data
Science (HEIBRiDS).

## Disclosures

The authors declare no conflicts of interest.

## Data availability

The data presented in this paper is available from the authors upon reasonable
request.

## References

## References

  * Heshami  _et al._ (2016) K. Heshami, D. G. England, P. C. Humphreys, P. J. Bustard, V. M. Acosta, J. Nunn, and B. J. Sussman, “Quantum memories: emerging applications and recent advances,” Journal of Modern Optics 63, 2005–2028 (2016), arXiv:1511.04018 .
  * Jaurigue  _et al._ (2021) L. Jaurigue, E. Robertson, J. Wolters, and K. Lüdge, “Reservoir computing with delayed input for fast and easy optimisation,” Entropy (Basel, Switzerland) 23 (2021), 10.3390/e23121560.
  * Finkelstein  _et al._ (2018) R. Finkelstein, E. Poem, O. Michel, O. Lahad, and O. Firstenberg, “Fast, noise-free memory for photon synchronization at room temperature,” Science Advances 4, eaap8598 (2018), https://www.science.org/doi/pdf/10.1126/sciadv.aap8598 .
  * Bhaskar  _et al._ (2020) M. K. Bhaskar, R. Riedinger, B. Machielse, D. S. Levonian, C. T. Nguyen, E. N. Knall, H. Park, D. Englund, M. Lončar, D. D. Sukachev, and M. D. Lukin, “Experimental demonstration of memory-enhanced quantum communication,” Nature 580, 60–64 (2020).
  * Briegel  _et al._ (1998) H.-J. Briegel, W. Dür, J. I. Cirac, and P. Zoller, “Quantum repeaters: The role of imperfect local operations in quantum communication,” Physical Review Letters 81, 5932–5935 (1998).
  * Gündoğan  _et al._ (2021) M. Gündoğan, J. S. Sidhu, V. Henderson, L. Mazzarella, J. Wolters, D. K. L. Oi, and M. Krutzik, “Proposal for space-borne quantum memories for global quantum networking,” npj Quantum Information 7 (2021), 10.1038/s41534-021-00460-9.
  * Wallnöfer  _et al._ (2022) J. Wallnöfer, F. Hahn, M. Gündoğan, J. S. Sidhu, F. Wiesner, N. Walk, J. Eisert, and J. Wolters, “Simulating quantum repeater strategies for multiple satellites,” Communications Physics 5, 169 (2022), arXiv:2110.15806 .
  * Aveline  _et al._ (2020) D. C. Aveline, J. R. Williams, E. R. Elliott, C. Dutenhoffer, J. R. Kellogg, J. M. Kohel, N. E. Lay, K. Oudrhiri, R. F. Shotwell, N. Yu, and R. J. Thompson, “Observation of Bose–Einstein condensates in an Earth-orbiting research lab,” Nature 582, 193–197 (2020).
  * Frye  _et al._ (2021) K. Frye, S. Abend, W. Bartosch, A. Bawamia, D. Becker, H. Blume, C. Braxmaier, S.-W. Chiow, M. A. Efremov, W. Ertmer, P. Fierlinger, T. Franz, N. Gaaloul, J. Grosse, C. Grzeschik, O. Hellmig, V. A. Henderson, W. Herr, U. Israelsson, J. Kohel, M. Krutzik, C. Kürbis, C. Lämmerzahl, M. List, D. Lüdtke, N. Lundblad, J. P. Marburger, M. Meister, M. Mihm, H. Müller, H. Müntinga, A. M. Nepal, T. Oberschulte, A. Papakonstantinou, J. Perovšek, A. Peters, A. Prat, E. M. Rasel, A. Roura, M. Sbroscia, W. P. Schleich, C. Schubert, S. T. Seidel, J. Sommer, C. Spindeldreier, D. Stamper-Kurn, B. K. Stuhl, M. Warner, T. Wendrich, A. Wenzlawski, A. Wicht, P. Windpassinger, N. Yu, and L. Wörner, “The Bose-Einstein Condensate and Cold Atom Laboratory,” EPJ Quantum Technology 8, 1 (2021).
  * Fleischhauer, Imamoglu, and Marangos (2005a) M. Fleischhauer, A. Imamoglu, and J. P. Marangos, “Electromagnetically induced transparency: Optics in coherent media,” Reviews of Modern Physics 77, 633–673 (2005a).
  * Gorshkov  _et al._ (2007) A. V. Gorshkov, A. André, M. Fleischhauer, A. S. Sørensen, and M. D. Lukin, “Universal approach to optimal photon storage in atomic media,” Physical Review Letters 98, 1–4 (2007).
  * Katz and Firstenberg (2018) O. Katz and O. Firstenberg, “Light storage for one second in room-temperature alkali vapor,” Nature Communications 9, 2074 (2018).
  * Esguerra  _et al._ (2022) L. Esguerra, L. Meßner, E. Robertson, N. V. Ewald, M. Gündoğan, and J. Wolters, “Optimization and readout-noise analysis of a hot vapor EIT memory on the Cs D1 line,” arXiv:2203.06151v1 (2022), 10.48550/ARXIV.2203.06151.
  * Buser  _et al._ (2022) G. Buser, R. Mottola, B. Cotting, J. Wolters, and P. Treutlein, “Single-Photon Storage in a Ground-State Vapor Cell Quantum Memory,” PRX Quantum 3, 020349 (2022), arXiv:2204.12389 .
  * Usmani  _et al._ (2010) I. Usmani, M. Afzelius, H. de Riedmatten, and N. Gisin, “Mapping multiple photonic qubits into and out of one solid-state atomic ensemble,” Nature Communications 1, 12 (2010), arXiv:1002.3782 .
  * Ding  _et al._ (2015) D.-S. Ding, W. Zhang, Z.-Y. Zhou, S. Shi, G.-Y. Xiang, X.-S. Wang, Y.-K. Jiang, B.-S. Shi, and G.-C. Guo, “Quantum Storage of Orbital Angular Momentum Entanglement in an Atomic Ensemble,” Physical Review Letters 114, 050502 (2015), arXiv:1404.0439 .
  * Langenfeld  _et al._ (2020) S. Langenfeld, O. Morin, M. Körber, and G. Rempe, “A network-ready random-access qubits memory,” npj Quantum Information 6, 86 (2020), arXiv:2011.00811 .
  * Li  _et al._ (2021) C. Li, S. Zhang, Y.-K. Wu, N. Jiang, Y.-F. Pu, and L.-M. Duan, “Multicell Atomic Quantum Memory as a Hardware-Efficient Quantum Repeater Node,” PRX Quantum 2, 040307 (2021).
  * Fleischhauer, Imamoglu, and Marangos (2005b) M. Fleischhauer, A. Imamoglu, and J. P. Marangos, “Electromagnetically induced transparency: Optics in coherent media,” Reviews of Modern Physics 77, 633–673 (2005b).
  * Schünemann  _et al._ (1999) U. Schünemann, H. Engler, R. Grimm, M. Weidemüller, and M. Zielonkowski, “Simple scheme for tunable frequency offset locking of two lasers,” Review of Scientific Instruments 70, 242–243 (1999).
  * Wiegand  _et al._ (2022) B. Wiegand, B. Leykauf, R. Jördens, and M. Krutzik, “Linien: A versatile, user-friendly, open-source fpga-based tool for frequency stabilization and spectroscopy parameter optimization,” Review of Scientific Instruments 93, 063001 (2022), https://doi.org/10.1063/5.0090384 .
  * Schkolnik (2017) V. Schkolnik,  _Probing gravity with quantum sensors_ , Ph.D. thesis, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät (2017).
  * Thomas  _et al._ (2017) S. E. Thomas, J. H. D. Munns, K. T. Kaczmarek, C. Qiu, B. Brecht, A. Feizpour, P. M. Ledingham, I. A. Walmsley, J. Nunn, and D. J. Saunders, “High efficiency Raman memory by suppressing radiation trapping,” New Journal of Physics 19, 063034 (2017), arXiv:1610.03743 .


# On the $\delta$-chromatic numbers of the Cartesian products of graphs

Wipawee Tangjai  Department of Mathematics, Faculty of Science, Mahasarakham
University, Maha Sarakham 44150, Thailand<EMAIL_ADDRESS>,  Witsarut
Pho-on  Department of Mathematics, Faculty of Science, Srinakharinwirot
University, Sukhumvit 23, 10110 Bangkok, Thailand<EMAIL_ADDRESS>and
Panupong Vichitkunakorn  Division of Computational Science, Faculty of
Science, Prince of Songkla University, Songkla 90110, Thailand
<EMAIL_ADDRESS>
###### Abstract.

In this work, we study the $\delta$-chromatic number of a graph which is the
chromatic number of the $\delta$-complement of a graph. We give a structure of
the $\delta$-complements and sharp bounds on the $\delta$-chromatic numbers of
the Cartesian products of graphs. Furthermore, we compute the
$\delta$-chromatic numbers of various classes of Cartesian product graphs,
including the Cartesian products between cycles, paths, and stars.

Keyword: delta-complement graph, chromatic number, Cartesian product, coloring
MSC: 05C07, 05C15, 05C35, 05C38, 05C69

##  1\. Introduction

The concept of $\delta$-complement was introduced in 2022 [5]. Their research
focused on exploring various intriguing characteristics of these graphs,
including properties like $\delta$-self-complementary, adjacency, and
hamiltonicity. In 2023, Vichitkunakorn et al. [7] introduced the term
$\delta$-chromatic number of a graph $G$ which refers to the chromatic number
of the $\delta$-complement of $G$. They established a Nordhaus-Gaddum bound
type relation between the chromatic number and the $\delta$-chromatic number
across various parameters: the clique number, the number of vertices and the
degrees of vertices. The given bounds are sharp and the classes of graphs
satisfying those bounds are given [7]. In this study, we present a more
detailed outcome concerning the $\delta$-chromatic number of the Cartesian
product of graphs.

In 1957, Sabidussi [6] showed that the chromatic number of the Cartesian
product graphs is equal to the maximum chromatic number between such two
graphs. A lot of subsequent research has been exploring different types of
chromatic numbers of the Cartesian product graphs such as list chromatic
number [2], packing chromatic number [3] and $b$-chromatic number [1, 4].

We first recall some basic notations and definitions needed in this article.
Let $G$ be a graph. For a subset $U$ of $V(G)$, $G[U]$ denotes the subgraph
induced by $U$. A vertex coloring $c$ of $G$ is a proper coloring if each pair
of adjacent vertices has distinct colors. The chromatic number of $G$, denoted
by $\chi(G)$, is the minimum number of colors needed so that $(G,c)$ is
properly colored. For each vertex $u\in V(G)$, we use notation $d_{G}(u)$ for
the degree of $u$ in $G$. Throughout this article, we let $P_{n}$ be a path
with $n$ vertices, $K_{n}$ be a complete graph with $n$ vertices and $C_{n}$
be a cycle with $n$ vertices. We let $S_{1,n}$ be a star with $n$ pendants.
For graphs $G$ and $H$, the Cartesian product of $G$ and $H$, denoted by
$G\square H$, is a graph where $V(G\square H)=V(G)\times V(H)$ and $uv\in
E(G\square H)$ if either $x=x^{\prime}$ and $yy^{\prime}\in E(H)$ or
$y=y^{\prime}$ and $xx^{\prime}\in E(G)$ for $u=(x,y)$ and
$v=(x^{\prime},y^{\prime})$.

In this work, we give a structure of the $\delta$-complement of the finite
Cartesian products of graphs. Sharp bounds on the $\delta$-chromatic number
(the chromatic number of $\delta$-complement) of the finite Cartesian products
of graphs are also given. In addition, we determine the specific value of the
$\delta$-chromatic numbers of various classes of the Cartesian product of
well-known graphs such as cycle, path, and star.

##  2\. Preliminary results

In this section, we review some basic definitions and previous results.

######  Definition 1 ([5]).

The $\delta$-complement of a graph $G$, denoted $G_{\delta}$, is a graph
obtained from $G$ by using the same vertex set and the following edge
conditions: $uv\in E(G_{\delta})$ if

  1. (1)

$d(u)=d(v)$ in $G$ and $uv\notin E(G)$, or

  2. (2)

$d(u)\neq d(v)$ in $G$ and $uv\in E(G)$.

######  Definition 2 ([7]).

A $\delta$-chromatic number $\chi_{\delta}(G)$ of a graph $G$ is the chromatic
number of $G_{\delta}$.

Results on the $\delta$-chromatic numbers of some important graphs are
$\chi_{\delta}(P_{n})=\left\lceil\frac{n-2}{2}\right\rceil$ for $n\geq 5$ [7],
$\chi_{\delta}(C_{n})=\left\lceil\frac{n}{2}\right\rceil$ [7], and
$\chi_{\delta}(W_{n})=1+\chi_{\delta}(C_{n})=1+\left\lceil\frac{n}{2}\right\rceil$.

######  Theorem 3 ([6]).

Let $G$ and $H$ be graphs. We have $\chi(G\square
H)=\max\\{\chi(G),\chi(H)\\}$.

######  Theorem 4 ([7]).

For $n\geq 4$, let $G$ be a graph with $n$ vertices. Let $d_{1},\dots,d_{m}$
be all distinct values of the degrees of the vertices in $G$. Partition $V(G)$
into non-empty sets $V_{d_{1}},V_{d_{2}},\dots,V_{d_{m}}$. We have

$\max_{1\leq i\leq
m}\\{|V_{d_{i}}|\\}\leq\chi(G)\cdot\chi_{\delta}(G)\leq\left(\frac{m+n}{2}\right)^{2}$

and

$2\cdot\sqrt{\max_{1\leq i\leq
m}\\{|V_{d_{i}}|\\}}\leq\chi(G)+\chi_{\delta}(G)\leq m+n.$

##  3\. Structure of the $\delta$-complements of Cartesian products

This section contains the structure of the $\delta$-complement of the
Cartesian product of graphs.

The following theorem shows that the edge set of the $\delta$-complements of
the Cartesian product contains the edge set of the Cartesian product of the
$\delta$-complements of graphs. It is a fundamental result that will be used
throughout what follows.

######  Theorem 5.

For graphs $G$ and $H$, we have $(G\square H)_{\delta}=(V,E)$ where
$V=V(G\square H)$ and $E=E(G_{\delta}\square H_{\delta})\cup S$ where
$S=\\{uv:u=(u_{1},u_{2})\in V(G\square H)\text{ and }v=(v_{1},v_{2})\in
V(G\square H)\text{ where }u_{1}\neq v_{1},u_{2}\neq v_{2}\text{ and
}d_{G\square H}(u)=d_{G\square H}(v)\\}$.

###### Proof.

$(\Longrightarrow)$ Let $u=(u_{1},u_{2})$ and $v=(v_{1},v_{2})$ be distinct
vertices in $(G\square H)_{\delta}$ where $uv\in E((G\square H)_{\delta})$. It
follows that either

  * •

$uv\in E(G\square H)$ and $d_{G\square H}(u)\neq d_{G\square H}(v)$, or

  * •

$uv\not\in E(G\square H)$ and $d_{G\square H}(u)=d_{G\square H}(v)$.

In case $uv\in E(G\square H)$ and $d_{G\square H}(u)\neq d_{G\square H}(v)$,
without loss of generality, we suppose that $u_{1}=v_{1}$, $u_{2}\neq v_{2}$
and $u_{2}v_{2}\in E(H)$. Since $d_{G}(u_{1})=d_{G}(v_{1})$, it follows that
$d_{H}(u_{2})\neq d_{H}(v_{2})$. Thus $u_{2}v_{2}\in E(H_{\delta})$. Hence
$uv\in E(G_{\delta}\square H_{\delta})$. In case $uv\not\in E(G\square H)$ and
$d_{G\square H}(u)=d_{G\square H}(v)$, we have $u_{1}\neq v_{1}$ and
$u_{2}\neq v_{2}$. Thus $uv\in S$.

$(\Longleftarrow)$ Let $uv\in E(G_{\delta}\square H_{\delta})\cup S$. Consider
$uv\in E(G_{\delta}\square H_{\delta})$. Without loss of generality, we
suppose that $u_{1}=v_{1}$, $u_{2}\neq v_{2}$ and $u_{2}v_{2}\in
E(H_{\delta})$. If $d_{G\square H}(u)=d_{G\square H}(v)$, then
$d_{H}(u_{2})=d_{H}(v_{2})$. Thus $u_{2}v_{2}\not\in E(H)$. Hence $uv\not\in
E(G\square H)$. Since $d_{G\square H}(u)=d_{G\square H}(v)$, we have $uv\in
E((G\square H)_{\delta})$. If $d_{G\square H}(u)\neq d_{G\square H}(v)$, then
$d_{H}(u_{2})\neq d_{H}(v_{2})$. Thus $u_{2}v_{2}\in E(H)$ and $uv\in
E(G\square H)$. Since $d_{G\square H}(u)\neq d_{G\square H}(v)$, we have
$uv\in E((G\square H)_{\delta})$. Now, we consider $uv\in S$. We have that
$u_{1}\neq v_{1}$ and $u_{2}\neq v_{2}$. So $uv\notin E(G\square H)$. Since
$d_{G\square H}(u)=d_{G\square H}(v)$, it follows that $uv\in E((G\square
H)_{\delta})$. ∎

######  Corollary 6.

Let $G$ and $H$ be graphs. We have $(G\square H)_{\delta}=G_{\delta}\square
H_{\delta}$ if and only if for any $u=(u_{1},u_{2})$ and $v=(v_{1},v_{2})$ in
$V(G\square H)$ where $u_{1}\neq v_{1}$ and $u_{2}\neq v_{2}$, we have
$d_{G\square H}(u)\neq d_{G\square H}(v)$.

In general, we have the following theorem for a finite Cartesian product of
graphs.

######  Theorem 7.

For graphs $G_{1},\dots,G_{k}$, we have $(G_{1}\square\cdots\square
G_{k})_{\delta}=(V,E)$ where $V=V(G_{1}\square\cdots\square G_{k})$ and
$E=E((G_{1})_{\delta}\square\cdots\square(G_{k})_{\delta})\cup S$ such that
$S$ is the set of $uv$ where $u=(u_{1},\dots,u_{k})\in V$,
$v=(v_{1},\dots,v_{k})\in V$, there are at least two indices $i$ that
$u_{i}\neq v_{i}$, and $d_{G_{1}\square\cdots\square
G_{k}}(u)=d_{G_{1}\square\cdots\square G_{k}}(v)$.

###### Proof.

It is well-known that two vertices $u=(u_{1},\dots,u_{k})$ and
$(v_{1},\dots,v_{k})$ in $G_{1}\square\dots\square G_{k}$ are adjacent if and
only if there is exactly one $i$ such that $u_{i}\neq v_{i}$ and
$u_{i}v_{i}\in E(G_{i})$. The rest of the proof follows similar arguments as
in Theorem 5. ∎

The following three results are applications of Theorem 7.

######  Theorem 8.

$(G_{1}\square\cdots\square
G_{k})_{\delta}=(G_{1})_{\delta}\square\cdots\square(G_{k})_{\delta}$ if and
only if there are at most one $i$ such that $G_{i}\neq K_{1}$.

###### Proof.

From Theorem 7, we need to show that $S=\emptyset$ if and only if there are at
most one $i$ such that $G_{i}\neq K_{1}$.

Suppose that there are $i\neq j$ such that $G_{i}\neq K_{1}$ and $G_{j}\neq
K_{1}$. Choose $u=(u_{1},\dots,u_{k})$ and $v=(v_{1},\dots,v_{2})$ such that
$u_{i}\neq v_{i}$, $u_{j}\neq v_{j}$, $d_{G_{i}}(u_{i})=d_{G_{i}}(v_{i})$,
$d_{G_{j}}(u_{j})=d_{G_{j}}(v_{j})$ and $u_{\ell}=v_{\ell}$ for all
$\ell\not\in\\{i,j\\}$. So $d_{G_{1}\square\cdots\square
G_{k}}(u)=d_{G_{1}\square\cdots\square G_{k}}(v)$. Then $uv\in S$. Hence
$S\neq\emptyset$.

The converse is obvious. ∎

######  Corollary 9.

$(G\square H)_{\delta}=G_{\delta}\square H_{\delta}$ if and only if $G=K_{1}$
or $H=K_{1}$.

##  4\. Bounds on the $\delta$-chromatic numbers of Cartesian products

In this section, we provide some exact numbers and bounds on the
$\delta$-chromatic numbers of some common graphs.

######  Theorem 10.

Let $G_{1},\dots,G_{k}$ be graphs. We have

$\max\\{\chi_{\delta}(G_{1}),\dots,\chi_{\delta}(G_{k})\\}\leq\chi_{\delta}(G_{1}\square\cdots\square
G_{k}).$

###### Proof.

The proof follows directly from Theorem 3 and 7. ∎

######  Theorem 11.

Let $G$ and $H$ be graphs. If any positive degree difference of vertices in
$G$ is not equal to that of in $H$, then

$\chi_{\delta}(G\square H)\leq n_{\max}(H)\cdot\max(\chi_{\delta}(G),m(H))$

where $n_{\max}(H)$ denotes the maximum number of vertices of the same degree
in $H$ and $m(H)$ is the number of different degrees in $H$. Furthermore, the
bound is sharp.

###### Proof.

By Theorem 5 and the assumption that any positive degree difference of
vertices in $G$ is not equal to that of in $H$, the edges in $S$ are $uv$
where $u=(u_{1},u_{2})$, $v=(v_{1},v_{2})$ such that $u_{1}\neq v_{1}$,
$u_{2}\neq v_{2}$, $d_{G}(u_{1})=d_{G}(v_{1})$ and
$d_{H}(u_{2})=d_{H}(v_{2})$. We partition $V(H)$ according to vertex degree
into $W_{1},W_{2},\dots,W_{m(H)}$. Write
$W_{j}=\\{h_{j,1},h_{j,2},\dots,h_{j,n_{j}}\\}$ for $1\leq j\leq m(H)$.

Define $p=\max(\chi_{\delta}(G),m(H))$. Let
$c_{0}:V(G)\to\\{1,2,\dots,\chi_{\delta}(G)\\}$ be a proper coloring of
$G_{\delta}$. We define a coloring $c:V(G)\times
V(H)\to\\{1,2,\dots,n_{\max}(H)\cdot p\\}$ as

$c(g,h_{j,k})=f(g,j)+(k-1)p,$

for $k=1,\dots,n_{j}$, where $f(g,j)\in\\{1,2,\dots,p\\}$ and $f(g,j)\equiv
c_{0}(g)+j-1\pmod{p}$. The first copy of $G$ in $W_{1}$ gets the original
coloring $c_{0}$, while we keep adding $p$ to the coloring of each other copy
of $G$ in $W_{1}$. In other $W_{j}$, we perform different cyclic permutations
modulo $p$ to $c_{0}$ and assign it to the first copy of $G$ in $W_{j}$. See
Table 1 for an example. We see that the vertices in the same copy of $G$
received a coloring equivalent to $c_{0}$ and a cyclic permutation modulo $p$
up to an additive constant $(k-1)p$ for some $k=1,\dots,n_{j}$. For a fixed
$g\in V(G)$, the vertices in the same copy of $H$, written in the form
$(g,h_{j,k})$ where $1\leq j\leq m(H)$ and $1\leq k\leq n_{j}$, received
distinct colors because $j\leq p$ and $k\leq n_{\max}(H)$.

Lastly, any endpoints of an edge in $S$ are of the form $(g,h_{j,k})$ and
$(g^{\prime},h_{j,k^{\prime}})$ where $g\neq g^{\prime}$ and $k\neq
k^{\prime}$, which received different colors as $k\neq k^{\prime}$. The
sharpness of the bound appears in Theorem 13. ∎

$h_{1,1}$ $h_{1,2}$ $h_{2,1}$ $h_{3,1}$ $h_{3,2}$ $h_{4,1}$ $h_{4,2}$$g_{1}$ 1
5 2 3 7 4 8 $g_{2}$ 3 7 4 1 5 2 6 $g_{3}$ 1 5 2 3 7 4 8 $g_{4}$ 2 6 3 4 8 1 5
$g_{5}$ 3 7 4 1 5 2 6  Table 1. An example of a coloring in the proof of
Theorem 11 where $\chi_{\delta}(G)=3$, $m(H)=4$ and $n_{\max}(H)=2$.

######  Corollary 12.

Let $G$ be a graph with $\chi_{\delta}(G)\geq 2$. If $d_{G}(v)\neq d_{G}(u)+1$
for all $u,v\in V(G)$, then $\chi_{\delta}(G\square P_{3})\leq
2\chi_{\delta}(G)$.

######  Theorem 13.

For $n\geq 5$, we have $\chi_{\delta}(C_{n}\square
P_{3})=2\chi_{\delta}(C_{n})=2\left\lceil\frac{n}{2}\right\rceil$.

###### Proof.

Let $P_{3}=v_{1}v_{2}v_{3}$. It is easy to see that
$\chi_{\delta}(C_{n})=\chi(\overline{C_{n}})=\left\lceil\frac{n}{2}\right\rceil$.
Since $C_{n}$ is regular, it also follows that $d_{C_{n}\square
P_{3}}(u,v_{1})=d_{C_{n}\square P_{3}}(w,v_{3})$ for all $u,w\in V(C_{n})$.
Since $(u,v_{1})$ is not adjacent to $(w,v_{3})$ in $C_{n}\square P_{3}$, it
follows that each vertex in the first copy of $C_{n}$ is adjacent to all the
vertices in the third copy of $C_{n}$ in $(C_{n}\square P_{3})_{\delta}$.
Hence the colors used in the two copies do not coincide. Thus
$\chi_{\delta}(C_{n}\square P_{3})\geq 2\chi_{\delta}(C_{n})$. By Corollary
12, we can conclude that $\chi_{\delta}(C_{n}\square
P_{3})=2\chi_{\delta}(C_{n})$. ∎

######  Example 14.

For $m\geq 3$, we have $\chi_{\delta}(S_{1,m}\square P_{3})\leq 2(m+1)$.

###### Proof.

Let $G=S_{1,m}$ and $H=P_{3}$. Theorem 11 gives the desired upper bound. ∎

The bound in Example 14 is not sharp. When $G=K_{1}\vee H$ is a join of a
singleton and a regular graph $H$, the following theorem gives an improved
upper bound on $\chi_{\delta}(G\square P_{3})$ in terms of $\chi_{\delta}(H)$.
Examples of the graph $G$ include stars $S_{1,m}=K_{1}\vee N_{m}$ (in Theorem
17), wheels $W_{m}=K_{1}\vee C_{m}$, and windmills $K_{1}\vee mK_{n}$.

######  Theorem 15.

Let $H$ be a $k$-regular graph. Let $G=\\{u\\}\vee H$ be the join of a
singleton and $H$. Suppose $|V(H)|\geq 3$ and $\chi_{\delta}(H)\geq 2$. If
$|V(H)|>k+2$, then $\chi_{\delta}(G\square P_{3})\leq 2\chi_{\delta}(H)$.

###### Proof.

Let $r\in V(H)$. Note that $d_{G}(u)=|V(H)|$. Since $d_{G\square
P_{3}}(r,v_{i})=d_{G}(r)+d_{P_{3}}(v_{i})\leq k+3<d_{G}(u)+1\leq d_{G\square
P_{3}}(u,v_{j})$ for $i,j\in\\{1,2,3\\}$, we have $(r,v_{i})$ and $(u,v_{j})$
are adjacent in $(G\square P_{3})_{\delta}$ if and only if $i=j$.

Let $H_{\delta}^{i}$ be the $i$-th copy of $H_{\delta}$ in $G_{\delta}$ for
$i=1,2,3$. Next, we construct a proper coloring $c$ as follows. We trivially
color $H_{\delta}^{1}$, as a copy of $H_{\delta}$, by a
$\chi_{\delta}(H)$-coloring. Since each vertex in $H_{\delta}^{1}$ is adjacent
to any vertices in $H_{\delta}^{3}$, it requires $2\chi_{\delta}(H)$ colors
for $H^{1}_{\delta}$ and $H^{3}_{\delta}$. We color $H^{3}_{\delta}$ using
$c(r,v_{3})=c(r,v_{1})+\chi_{\delta}(H)$. For $i=1,3$, we notice that a vertex
$(r,v_{i})\in V(H^{i}_{\delta})$ and $(s,v_{2})\in V(H^{2}_{\delta})$ are
adjacent if and only if $r=s$. We let $c(r,v_{2})=c(r,v_{1})+1$ if $1\leq
c(r,v_{1})\leq\chi_{\delta}(H)-1$; otherwise, $c(r,v_{2})=1$. Lastly, we color
$(u,v_{1})$, $(u,v_{2})$ and $(u,v_{3})$ by $\chi_{\delta}(H)+1$,
$\chi_{\delta}(H)+2$ and $1$, respectively. This gives a proper coloring of
$(G\square P_{3})_{\delta}$ with $2\chi_{\delta}(H)$ colors. ∎

The sharpness of the bound in Theorem 15 will be shown in Theorem 17.

##  5\. The $\delta$-chromatic numbers of the Cartesian products of some
graphs

In this section, we give the exact values of the $\delta$-chromatic numbers of
the Cartesian products of stars and paths.

######  Theorem 16.

$\chi_{\delta}(S_{1,m}\square S_{1,n})=mn$ for $m,n\geq 3$.

###### Proof.

Let $V(S_{1,n})=\\{0,1,\dots,k\\}$ where $d_{S_{1,k}}(0)=k$ for $k=n,m$. An
$mn$-coloring on $(S_{1,m}\square S_{1,n})_{\delta}$ is

$c(i,j)=\begin{cases}j+1&\text{if }i=0,\\\ (i-1)n+j&\text{if }1\leq i\leq
m\text{ and }1\leq j\leq n,\\\ (i+1)n&\text{if }1\leq i<m\text{ and }j=0,\\\
n+2&\text{if }i=m\text{ and }j=0,\end{cases}$

as shown in Fig. 1. In addition, the set $\\{(i,j):1\leq i\leq m,1\leq j\leq
n\\}$ forms an $mn$-clique in $(S_{1,m}\square S_{1,n})_{\delta}$. ∎

$1$$2$$3$$\ddots$$n+1$$2n$$1$$2$$\ddots$$n$$3n$$n+1$$n+2$$\ddots$$2n$$4n$$2n+1$$2n+2$$\ddots$$3n$$\dots$$n+2$$mn-n+1$$mn-n+2$$\ddots$$mn$
Figure 1. A proper $mn$-coloring of $(S_{1,m}\square S_{1,n})_{\delta}$. The
vertices of the same degree in $S_{1,m}\square S_{1,n}$ are indicated by the
same color and are pairwise adjacent in $(S_{1,m}\square S_{1,n})_{\delta}$.
Each double line denotes the edges connecting the corresponding vertices
between two copies of $S_{1,n}$. Note that the blue and the green will have
the same degree when $m=n$.

######  Theorem 17.

$\chi_{\delta}(S_{1,m}\square P_{n})=m\left\lceil\frac{n-2}{2}\right\rceil$
for $m\geq 3$ and $n\geq 3$.

###### Proof.

Let $V(S_{1,m})=\\{0,1,\dots,m\\}$ where $d_{S_{1,m}}(0)=m$ and Let
$V(P_{n})=\\{1,2,\dots,n\\}$ where $d_{P_{n}}(1)=d_{P_{n}}(n)=1$.

When $n=3$, Theorem 15 gives $\chi_{\delta}(S_{1,m}\square P_{3})\leq 2m$.
Since the set $\\{(i,j)\in V((S_{1,m}\square P_{3})_{\delta}):1\leq i\leq
m,j=1,3\\}$ forms a $2m$-clique in $(S_{1,m}\square P_{3})_{\delta}$, we get
$\chi_{\delta}(S_{1,m}\square P_{3})=2m$.

When $n=4$, Theorem 11 with $G=P_{4}$ and $H=S_{1,m}$ gives
$\chi_{\delta}(S_{1,m}\square P_{4})=\chi_{\delta}(P_{4}\square S_{1,m})\leq
2m$. The set $\\{(i,j)\in V((S_{1,m}\square P_{4})_{\delta}):1\leq i\leq
m,j=1,4\\}$ forms a $2m$-clique in $(S_{1,m}\square P_{4})_{\delta}$. Hence
$\chi_{\delta}(S_{1,m}\square P_{4})=2m$.

When $n\geq 5$, we let $k=\lceil\frac{n-2}{2}\rceil$. A coloring is

$c(i,j)=\begin{cases}i+(k-1)m&0\leq i\leq m\text{ and }j=1,\\\ i&1\leq i\leq
m\text{ and }j=n,\\\ i+(\lfloor j/2\rfloor-1)m&0\leq i\leq m\text{ and }2\leq
j\leq n-1\text{ where }(i,j)\neq(0,2),(0,3),\\\ km&i=0\text{ and }j=2,3,n\\\
\end{cases}$

as shown in Fig. 2. We thus have a proper $km$-coloring of $(S_{1,m}\square
P_{n})_{\delta}$. In addition, the set $\\{(i,j)\in V((S_{1,m}\square
P_{n})_{\delta}):1\leq i\leq m\text{ and }2\leq j\leq n-1\text{ and }j\text{
is even}\\}$ forms a clique of size $m\left\lceil\frac{n-2}{2}\right\rceil$ in
$(S_{1,m}\square P_{n})_{\delta}$. ∎

$(k-1)m$$(k-1)m+1$$(k-1)m+2$$\ddots$$km$$km$$1$$2$$\ddots$$m$$km$$1$$2$$\ddots$$m$$(k-1)m$$(k-1)m+1$$(k-1)m+2$$\ddots$$km$$km$$1$$2$$\ddots$$m$
Figure 2. A proper $km$-coloring of $(S_{1,m}\square P_{n})_{\delta}$ where
$k=\lceil\frac{n-2}{2}\rceil$. The vertices of the same degree in
$S_{1,m}\square P_{n}$ are indicated by the same color and are pairwise
adjacent except for the pairs with a dashed line.

The following lemma is crucial for proving Theorem 19.

######  Lemma 18.

For $n\geq 6$ and $k\geq 8$, we have

$2\left\lceil\frac{n-2}{2}\right\rceil+2\left\lceil\frac{k-2}{2}\right\rceil+1<\left\lceil\frac{(n-2)(k-2)}{2}\right\rceil.$

###### Proof.

Suppose
$2\left\lceil\frac{n-2}{2}\right\rceil+2\left\lceil\frac{k-2}{2}\right\rceil+1\geq\left\lceil\frac{(n-2)(k-2)}{2}\right\rceil$.

######  Case 1.

$n$ and $k$ are even.

We have

$\displaystyle n+k-3$ $\displaystyle\geq\frac{(n-2)(k-2)}{2},$ $\displaystyle
2n+2k-6$ $\displaystyle\geq nk-2n-2k+4.$

Thus $n\leq\frac{4k-10}{k-4}<6$ when $k\geq 8$, which is a contradiction.

######  Case 2.

$n$ is odd and $k$ is even.

We have

$\displaystyle n+k-2$ $\displaystyle\geq\frac{(n-1)(k-2)}{2},$ $\displaystyle
2n+2k-4$ $\displaystyle\geq nk-2n-k+2.$

Thus $n\leq\frac{3k-6}{k-4}\leq\frac{9}{2}$, which is not possible when $k\geq
8$. The same argument can be applied when $n$ is even and $k$ is odd.

######  Case 3.

$n$ and $k$ are odd.

$\displaystyle n+k-1$ $\displaystyle\geq\frac{(n-1)(k-1)}{2},$ $\displaystyle
2n+2k-4$ $\displaystyle\geq nk-n-k+1.$

Thus $n\leq\frac{3k-5}{k-3}\leq\frac{19}{5}$, which is not possible when
$k\geq 8$.

Therefore
$2\left\lceil\frac{n-2}{2}\right\rceil+2\left\lceil\frac{k-2}{2}\right\rceil+1<\left\lceil\frac{(n-2)(k-2)}{2}\right\rceil.$
∎

######  Theorem 19.

For $6\leq n\leq k$, we have

$\chi_{\delta}(P_{n}\square
P_{k})=\left\lceil\frac{(n-2)(k-2)}{2}\right\rceil.$

###### Proof.

Let $V_{d}$ be the set of vertices of degree $d$ in $P_{n}\square P_{k}$. The
vertex set of $P_{n}\square P_{k}$ can be partitioned into $V_{2},V_{3}$ and
$V_{4}$. We note that $V(P_{n}\square P_{k})=V((P_{n}\square
P_{k})_{\delta})=V(P_{n})\times V(P_{k})$. Let $(i,j)\in V(P_{n}\square
P_{k})$ for $i=1,\dots,n$ and $j=1,\dots,k$. We have that
$V_{3}=\\{(i,j):i=1,n\text{ and }2\leq j\leq k-1\\}\cup\\{(i,j):j=1,k\text{
and }2\leq i\leq n-1\\}$ and $V_{4}=\\{(i,j):2\leq i\leq n-1\text{ and }2\leq
j\leq k-1\\}$. Thus $|V_{2}|=4$, $|V_{3}|=2(n+k-4)$ and $|V_{4}|=(n-2)(k-2)$.
The vertices $(i,j)$ and $(i^{\prime},j^{\prime})$ are adjacent in
$P_{n}\square P_{k}$ if and only if $|i-i^{\prime}|+|j-j^{\prime}|=1$. Thus

  * •

if $d_{P_{n}\square P_{k}}(i,j)=d_{P_{n}\square
P_{k}}(i^{\prime},j^{\prime})$, then the vertices $(i,j)$ and
$(i^{\prime},j^{\prime})$ are adjacent in $(P_{n}\square P_{k})_{\delta}$ if
and only if $|i-i^{\prime}|+|j-j^{\prime}|\geq 2$,

  * •

if $d_{P_{n}\square P_{k}}(i,j)\neq d_{P_{n}\square
P_{k}}(i^{\prime},j^{\prime})$, then the vertices $(i,j)$ and
$(i^{\prime},j^{\prime})$ are adjacent in $(P_{n}\square P_{k})_{\delta}$ if
and only if $|i-i^{\prime}|+|j-j^{\prime}|=1$.

Since each pair of vertices $(i,j),(i^{\prime},j^{\prime})\in V_{4}$ with
$|i-i^{\prime}|+|j-j^{\prime}|\geq 2$ are adjacent, it follows that

$\chi_{\delta}(P_{n}\square P_{k})\geq\omega((P_{n}\square
P_{k})_{\delta})\geq\left\lceil\frac{(n-2)(k-2)}{2}\right\rceil.$

We note that

$\left\lceil\frac{(n-2)(k-2)}{2}\right\rceil=\begin{cases}\frac{(n-2)(k-2)}{2}&\text{
if }n\text{ or }k\text{ is even},\\\
\left\lfloor\frac{k-2}{2}\right\rfloor(n-2)+\left\lceil\frac{n-2}{2}\right\rceil&\text{
if }n\text{ and }k\text{ are odd}.\end{cases}$

We color $V_{4}$ by a coloring $c_{0}$ defined by

$c_{0}(i,j)=\begin{cases}(i-2)\left\lfloor\frac{k-2}{2}\right\rfloor+\left\lfloor\frac{j-2}{2}\right\rfloor&\text{
if }i=2,\dots,n-1\text{ and
}j=2,\dots,2\left\lfloor\frac{k-2}{2}\right\rfloor+1,\\\
(n-2)\left\lfloor\frac{k-2}{2}\right\rfloor+\left\lfloor\frac{i-2}{2}\right\rfloor&\text{
if }k\text{ is odd and }j=k-1,i=1,\dots,n-2.\end{cases}$

The coloring $c_{0}$ uses $\left\lceil\frac{(n-2)(k-2)}{2}\right\rceil$
colors. Since the coloring in $V_{4}$ has at most 2 vertices with the same
color and they are adjacent in $P_{n}\square P_{k}$, which are not adjacent in
$(P_{n}\square P_{k})_{\delta}$, the coloring $c_{0}$ on $(P_{n}\square
P_{k})_{\delta}[V_{4}]$ is proper. The case $6\leq k\leq 7$ can be verified.
Now, we suppose that $k\geq 8$. We color $V_{3}$ using
$2\left\lceil\frac{n-2}{2}\right\rceil+2\left\lceil\frac{k-2}{2}\right\rceil$
colors. We color the vertices $V_{3}$ in pair of consecutive vertices (except
possibly the last one in a block) clockwise starting from location $(1,2)$ to
$(2,1)$. Each color in $V_{3}$ needs to avoid at most
$2\left\lceil\frac{n-2}{2}\right\rceil+2\left\lceil\frac{k-2}{2}\right\rceil-1$
colors of the other vertices in $V_{3}$ and two neighbors per each color in
$V_{4}$, i.e., we have to avoid
$2\left\lceil\frac{n-2}{2}\right\rceil+2\left\lceil\frac{k-2}{2}\right\rceil+1$
colors. By Lemma 18, there is a remaining color in $V_{4}$ that is available
to assign to the considered vertex. Since each vertex in $V_{2}$ has degree 5
in $(P_{n}\square P_{k})_{\delta}$ and
$\left\lceil\frac{(n-2)(k-2)}{2}\right\rceil>5$, we can color $V_{2}$. This
completes the proof. ∎

655330764201764201975318975318699880944228 Figure 3. A proper 10-coloring of
$(P_{6}\square P_{7})_{\delta}$. The vertices in $V_{2}$, $V_{3}$ and $V_{4}$
are shown in red, blue and black, respectively. The vertices in each $V_{i}$
for $i=2,3,4$ are pairwise adjacent in $(P_{6}\square P_{7})_{\delta}$ except
for the pairs with a dashed line.

##  6\. Conclusion

We give a structure of $(G_{1}\square\cdots\square G_{k})_{\delta}$ associated
with $(G_{1})_{\delta}\square\cdots\square(G_{k})_{\delta}$ and the necessary
and sufficient condition that both graphs are equal. We also give sharp bounds
on the $\delta$-chromatic number of $G\square H$ with a class of graphs
achieving such bound. The $\delta$-chromatic number of the Cartesian product
of several classes of well-known graphs are also given.

## Acknowledgement

The authors thank Rasimate Maungchang for his invaluable comments. This
research project was financially supported by Mahasarakham University.

## References

  * [1] R. Balakrishnan, S.F. Raj, and T. Kavaskar.  $b$-chromatic number of cartesian product of some families of graphs.  Graphs and Combinatorics, page 511–520, 2014.
  * [2] M. Borowiecki, S. Jendrol’, D. Král’, and J. Miškuf.  List coloring of cartesian products of graphs.  Discrete Mathematics, 306(16):1955–1958, 2006.
  * [3] B. Brešar, S. Klavžar, and D. F. Rall.  On the packing chromatic number of cartesian products, hexagonal lattice, and trees.  Discrete Applied Mathematics, 155(17):2303–2311, 2007.
  * [4] C. Guo and M. Newman.  On the $b$-chromatic number of cartesian products.  Discrete Applied Mathematics, 239:82–93, 2018.
  * [5] A. Pai, H. A Rao, S. D’Souza, P. G. Bhat, and S. Upadhyay.  $\delta$-complement of a graph.  Mathematics, 10(8):1203, 2022.
  * [6] G. Sabidussi.  Graphs with given group and given graph-theoretical properties.  Canadian Journal of Mathematics, 9:515–525, 1957.
  * [7] P. Vichitkunakorn, R. Maungchang, and W. Tangjai.  On nordhaus-gaddum type relations of $\delta$-complement graphs.  Heliyon, 9(6):e16630, 2023.