# Open-loop multi-channel inversion of room impulse response

###### Abstract

This paper considers methods for audio display in a CAVE-type virtual reality
theater, a 3 m cube with displays covering all six rigid faces. Headphones are
possible since the user's headgear continuously measures ear positions, but
loudspeakers are preferable since they enhance the sense of total immersion.
The proposed solution consists of open-loop acoustic point control. The
transfer function, a matrix of room frequency responses from the loudspeakers
to the ears of the user, is inverted using multi-channel inversion methods, to
create exactly the desired sound field at the user's ears. The inverse
transfer function is constructed from impulse responses simulated by the image
source method. This technique is validated by measuring a $2\times 2$ matrix
transfer function, simulating a transfer function with the same geometry, and
filtering the measured transfer function through the inverse of the
simulation. Since accuracy of the image source method decreases with time,
inversion performance is improved by windowing the simulated response prior to
inversion. Parameters of the simulation and inversion are adjusted to minimize
residual reverberant energy; the best-case dereverberation ratio is 10 dB.

##  1 Introduction

The task of interest in this paper is free-field audio display for a virtual
reality environment [1]. The virtual reality testbed for these experiments is
a 3 m cube called ALICE (A Laboratory for Interactive Cognitive Experiments),
located at the University of Illinois. Images are projected from outside onto
all faces of the cube. Users are untethered: no wires connect equipment they
wear to the outside world. In order to accurately convey images to the user,
the positions of up to 20 user points (e.g., head, ears, hands, and feet) are
precisely tracked using a magnetic tracking system (calibrated mean accuracy
of 8 cm and 1 degree, 120 samples updated per second). The goal of virtual
reality in ALICE is total immersion: users must be able to ``suspend
disbelief'' and convince themselves that they are physically present in the
virtual environment portrayed to them.

The goal of most previous virtual reality audio experiments is to correctly
portray the position of a sound source. Position accuracy is usually achieved
by filtering the audio signal through head-related transfer functions and then
playing it over headphones. The disadvantage of headphone audio is that it
sounds like it is coming from the headphones. The impression of total
immersion is lost if the audio display is part of the user's headgear rather
than part of the environment.

A measure of headphone-free realism is possible by simply playing the desired
audio from the most appropriate speaker in a large speaker array. For the
ALICE environment, an array of eight transparent loudspeakers has been
prototyped. These loudspeakers consist of millimeter-thick sheet glass
suspended into the cube, connected to compression drivers located outside the
walls of the cube. The transparent speakers provide reasonable audio display
with good localization for distant objects (outside the cube wall), and most
important, the transparent loudspeakers do not obstruct or distort the video
display.

Moving the virtual audio source inside the room is much more difficult. The
positions of the user's ears are known precisely. If the room impulse response
were known, then the known room impulse response could be inverted using well-
studied multi-channel inversion methods [2, 3], thus creating exactly the
desired sound field at the two ears of the user. Unfortunately the room
impulse response is not known. The user is free to put his or her head
anywhere in the room; it is impossible to measure the room impulse response
from every speaker location to every possible location of the user's ears.

Two solutions to this problem are possible. First, an estimate of the room
impulse response can be adaptively updated using microphones placed on the
user's headgear, by means of a number of adaptive signal processing methods.
This paper analyzes a second solution to the problem of headphone-free virtual
reality audio display. The proposed solution consists of open-loop acoustic
point control, using a simulation of room impulse response based only on
knowledge of the room geometry, architectural materials, and user location.

The image source method of room response simulation was originally proposed
for open-loop dereverberation experiments similar to the one proposed here
[4]. Its performance was never quantitatively reported in the literature,
since multi-channel inversion methods for non-minimum phase impulse responses
were not well understood at that time [5]. Other methods of simulating room
impulse response are almost always evaluated by purely qualitative means like
acoustic perceptual studies and visual comparisons of impulse responses [6].

This paper proposes instead to evaluate simulated room impulse responses based
on their performance in a regularized dereverberation task. Dereverberation
performance is measured in terms of the decibel ratio of the energy of the
room impulse response to that of the dereverberated response. It is
demonstrated that this method can be used to optimize parameters of the model
including absorptivity and window taper.

This paper is organized as follows. Section 2 describes previous published
research in the fields of room impulse response measurement, room impulse
response simulation, and room impulse response inversion. Section 3 describes
the methods of these tasks in a simulated virtual reality environment, a 2 m
plywood cube. Room impulse responses are measured with a starter pistol. An
evaluation metric is proposed to quantitatively measure the dereverberation
ratio. Section 4 discusses the results, demonstrating how the proposed
evaluation metric optimizes methods for simulating and inverting the room
impulse reponse. Section 5 reviews conclusions.

##  2 Background

###  2.1 Measurement of room impulse response

An excitation signal is required in order to measure a room impulse response.
A perfect impulse (a Dirac delta function) simplifies the measurement task
(measured response equals the impulse response), but it is not possible to
physically generate a Dirac delta function. In practice, impulse-like signals
or signals with characteristics similar to a perfect impulse such as flat
frequency response are used.

ISO Standard 3382 specifies the following requirements for an excitation
signal for measuring room impulse response [7]. First, it should be nearly
omnidirectional. Second, its sound pressure level should provide sufficient
dynamic range to avoid contamination by background noise. Third, the signal
should be repeatable.

Impulse-like signals such as the starter pistol, balloon pop, and electric
spark have been traditionally chosen as excitation signals [7, 8]. These
impulses are easily generated and have been used to determine rough
characteristics of a room, such as reverberation time. However, measurement by
these impulse methods has not been widely discussed in the scientific
literature for three reasons. First, the frequency response of these impulses
is not flat (Fig. 1). Second, some authors report that it is difficult to get
an adequate SNR because all the impulse's energy is packed into a very short
duration [8]. Third, the signal is not precisely repeatable because it depends
significantly on small variations in charge distribution, balloon shape, etc
(Fig. 2).

Fig. 1:  Magnitude responses of starter pistol and ambient noise.

Fig. 2:  Waveforms of individual pistol shots.

In 1979 Schroeder suggested an alternative method to measure room impulse
response using Maximum Length Sequences (MLS) [8]. The autocorrelation
function of an MLS of order $m$ with length $N=2^{m}-1$ samples is two-valued,
$1$ at time zero and $-1/N$ at times other than zero (modulo $N$). If $N$ is
sufficiently large, then $-1/N$ becomes negligible and we can assume that the
resulting MLS has the same autocorrelation as pseudo-random noise. Because MLS
signal energy grows with $N$, its SNR can be made arbitrarily high without
needing high amplitude, which is not the case with impulses. Since the MLS is
stored in a computer, it can be generated repeatedly. Therefore MLS meets the
last two requirements of ISO 3382 better than impulse-like signals such as
starter pistols and electric sparks.

Computer-generated pseudo-random sequences have discrete values such as $+1$
and $-1$. Since it is impossible to make perfectly abrupt transitions between
these two values, distortion occurs and the frequency response of the system
must therefore be compensated to acquire accurate impulse responses. The
technique of MLS measurement has also been proven to be vulnerable to the
nonlinearity of measuring equipment, particularly loudspeakers [9].
Nonlinearities produce repeated distortion peaks in the time domain, which
prevent the integrated energy of the impulse response from falling below $-30$
dB [10, 11]. A modification of MLS, the inverse repeated sequence (IRS),
reduces the distortion caused by nonlinearities [12, 13, 14]. Other papers
discuss the accuracy of the MLS method [15, 16], its computational complexity
[17, 18, 19, 20, 21], and its application to a variety of system response
measurements [22, 23, 24].

Aoshima proposed the time-stretched pulses technique, based on the time
expansion and compression of an impulsive signal [25]. The purpose of the
time-stretched pulse signal is to increase the total energy of the excitation
signal while keeping the frequency response flat.

Berkhous proposed a sine sweep as an excitation signal [26]. Farina and
Ugolotti introduced a logarithmic sine sweep method using a different
deconvolution method [27]. Farina's detailed method accurately derives an
impulse response from the raw measurement by separating the linear and
nonlinear components of the measured impulse response, where the strength of
nonlinear distortion is measured by observing the harmonic distortion caused
by nonlinearity of the system.

Stan et al. compare four different room impulse response measurement
techniques: pseudo-random noise (MLS and IRS), time-stretched pulses, and
logarithmic sine sweep [11]. Since the randomized phase of psuedo-random
sequences makes them immune to background noise, MLS and IRS techniques are
preferred in noisy environments. However, parameter optimization is required
for high SNR because of nonlinear distortion. Nevertheless, the achieved SNR
is only 60.5 dB with an MLS order of 16 and single measurement.

Time-stretched pulses and sine sweep methods produce a higher SNR than the
pseudo-random noise techniques, but they require a quiet environment. The SNR
of the time-stretched pulses technique is 77 dB after precise calibration. The
logarithmic sine sweep method has 80.1 dB SNR. The benefit of the sine sweep
is that unlike the previous methods, it produces a high SNR without any
calibration [11].

###  2.2 Simulation of room impulse response

Simulations of room impulse responses fall into two categories: spatial mesh
methods and ray acoustic methods.

Spatial mesh methods numerically solve the constituents of the acoustic wave
equation, namely the equations of motion and continuity [28, 29]. In this
method, sound pressure and velocity are computed at a finite number of points,
usually mesh points in a cavity. The differential equations in the continuous
domain are computed as difference equations in the discrete domain. This
method can simulate diffraction effects, which ray acoustic methods cannot.
Unfortunately, to compute an impulse response at a specific location of
interest, the values of sound pressure and velocity must be computed over the
entire mesh, because the solution at a specific point depends on those of the
adjacent points. Spatial mesh methods are thus far more computationally
expensive than ray acoustic methods.

Ray acoustic methods assume that sound rays are emitted from the sound source,
usually as a spherical wave. Ray paths are then traced using either image
source or ray-tracing methods [4, 30]. The ray-tracing method considers a
finite number of rays to be emitted from the sound source. These ray paths are
traced and their trajectories summed at points of interest. Although it
requires little computation, ray tracing is appropriate only for a rough
estimate, e.g., to compute the first few reflections of the room impulse
response.

In 1979 Allen and Berkley showed that the impulse response of a small
rectangular room can be computed using a geometric ``image source'' method
[4]. Their model creates an ``image space'' without walls, in which each echo
is modeled as the direct sound from an image source outside the actual walls
of the room. The first six image sources are reflections of the original
source in the six walls of the room. The next few image sources are created by
reflecting the first six, and so on (Fig. 3). At each reflection, the
amplitude of the source is scaled by the wall's reflection coefficient.

Fig. 3:  Two-dimensional illustration of the image source method.;
`x'=receiver, solid `o'=source, dashed `o'=image sources. Solid line=an echo
path, dashed line=corresponding image source path.

The image source method requires more computation than ray tracing because it
considers all possible reflected wavefronts. It can be extended from
rectangular cavities to arbitrary polyhedra [31]. In this case, some image
sources may not contribute to the total impulse response. Such image sources
are called hidden images. An algorithm is therefore needed to decide whether a
given image source is hidden or not. Lee and Lee proposed a relatively
efficient algorithm for the image source computation of impulse responses of
arbitrarily shaped rooms [32], but this method is still computationally
expensive relative to the image source method for rectangular rooms. The image
source method is efficient for a rectangular room because every image source
contributes to the total impulse response (unless there are obstacles in the
room), and also, because the locations of all image sources are analytically
pre-computed due to symmetry.

In a rectangular room, the image sources can be indexed by integer coordinates
$l$, $m$, and $n$, where $(l,\ m,\ n)=(0,\ 0,\ 0)$ corresponds to the direct
source, $(1,\ 0,\ 0)$ corresponds to the first reflection in the positive $x$
direction, and so on.

Given a room of size $(L_{x},\ L_{y},\ L_{z})$ with origin at the center and a
source location $(S_{x},\ S_{y},\ S_{z})$, the image source location with
indices $(l,\ m,\ n)$ is:

$(I_{x},\ I_{y},\ I_{z})=(lL_{x}+(-1)^{l}S_{x},\ mL_{y}+(-1)^{m}S_{y},\
nL_{z}+(-1)^{n}S_{z})$

Then the distance $d_{lmn}$ from the image source to the receiver at
$(R_{x},R_{y},R_{z})$ is:

$d_{lmn}=\sqrt{(R_{x}-I_{x})^{2}+(R_{y}-I_{y})^{2}+(R_{z}-I_{z})^{2}}$

The impulse response predicted by the image source method is

$g(t)=\sum_{l,m,n=-\infty}^{\infty}\frac{r^{|l|+|m|+|n|}}{d_{lmn}}\delta(t-\tau_{lmn})$
(1)

where $\tau_{lmn}=d_{lmn}/c$ is the wave propagation time from the image
source at $(l,m,n)$ to the receiver, $c$ is the speed of sound, and $r$ is the
reflection coefficient of the walls. Eq. (1) assumes that all surfaces have
the same reflection coefficient, but relaxing this assumption is
straightforward and computationally inexpensive.

Three-dimensional audio applications are usually considered in a rectagular
cavity, a room; this paper considers only this special but common case, to
justify use of the otherwise computationally expensive image source method for
simulating the room impulse response.

###  2.3 Inversion of room impulse response

Given the room impulse response, a desired signal can be reproduced at points
of interest if a valid inverse filter is first created from the impulse
response. The dereverberation problem thus reduces to constructing such an
inverse filter.

Since the purpose of inverting the room impulse response is to cancel
reverberation at multiple points in a room, human ears for example, the
frequency responses and inverse filters are formulated as a matrix of
sequences. Let the term transfer function denote this matrix of frequency
responses.

Let $G_{ji}(z)$ be the frequency response from the $i^{th}$ loudspeaker to the
$j^{th}$ control point, for $1\leq i\leq L$ and $1\leq j\leq M$: a total of
$M\times L$ individual room impulse responses. The inverse of this transfer
fuction is therefore an $L\times M$ matrix. The image source method computes
the simulated frequency response $\hat{G}_{ji}(z)$ which approximates
$G_{ji}(z)$.

Let $X_{j}(z)$ and $\hat{X}_{j}(z)$ denote the Z-transforms of the desired and
actual control point signals respectively. The inverse transfer function
$H(z)$ has as element $H_{ij}(z)$, the impulse response from the $j^{th}$
desired control point signal $X_{j}(z)$ to the $i^{th}$ loudspeaker signal
$V_{i}(z)$. $\hat{X}_{j}(z)$ is therefore expressed as

$\hat{X}_{j}(z)=\sum_{i}\hat{G}_{ji}(z)V_{i}(z)=\sum_{i,k}\hat{G}_{ji}(z)H_{ik}(z)X_{k}(z)$

We want to find $H_{ij}(z)$ so that $\hat{X}_{j}(z)$ is as similar as possible
to $X_{j}(z)$. Figure 4 shows the diagram of the room impulse response
inversion process. If $L=M$ and the matrix $\hat{G}(z)$ is minimum phase, then
an exact inverse transfer function is given by
$H(e^{j\omega})=\hat{G}(e^{j\omega})^{-1}$.

Fig. 4:  System diagram.

If the impulse responses are non-minimum phase, the inverse filter has poles
outside the unit circle. In this case, we can make the inverse filter either
stable but noncausal (the region of convergence includes the unit circle) or
causal but unstable (the region of convergence does not include the unit
circle), but not both stable and causal. Therefore, the exact inverse filter
of a square transfer function matrix is only realizable for minimum phase
transfer functions.

Neely and Allen found that the impulse response of a small room is minimum
phase only for reflection coefficients below approximately 0.37 [5]. The
impulse response of a small room is rarely minimum phase, and therefore the
stable inverse filter $\hat{G}(e^{j\omega})^{-1}$ of a square matrix
$\hat{G}(e^{j\omega})$ is usually noncausal in practice.

Miyoshi and Kaneda showed that the transfer function of a room can be exactly
inverted for the case $L=2,M=1$ [2]. Nelson et al. generalized their result by
showing that, in most circumstances without any extreme symmetry, when $L>M$,
the transfer function can be exactly inverted [33]. Thus a stable, causal
inverse transfer function exists if $G_{ji}(z)$ has more columns than rows.
Unfortunately no tractable method for finding the causal, stable inverse of a
non-square transfer function in the frequency domain has yet been proposed. An
equivalent method can be computed in the time domain, but is computationally
expensive.

Recall that a non-minimum phase square transfer function has a stable but
noncausal inverse $H(e^{j\omega})$. A causal, stable semi-inverse may be
constructed by applying a time shift $D$:

$\tilde{H}(e^{j\omega})=e^{-j\omega D}H(e^{j\omega})$ (2)

and then truncating $\tilde{h}[n]$ by zeroing the tail at $n<0$:

$\hat{h}[n]=\left\\{\begin{array}[]{ll}\tilde{h}[n],&n\geq 0\\\
0,&n<0\end{array}\right.$ (3)

This creates a stable and causal approximation $\hat{h}[n]$ of the exact
inverse filter. The time shift $D$ is called modeling delay.

The inverse transfer function $H$ can be computed by sampling the spectrum of
$\hat{G}$ using an FFT, and inverting the matrix at each frequency bin.
Sampling the frequency-domain transfer function causes aliasing in the time
domain. This ``wrap-around effect'' is eliminated by time-shifting $h[n]$ by
$e^{-j\omega D}$, which is the same as the modeling delay described
previously.

Merely inverting the sampled FFT matrix $\hat{G}$ yields a poor estimate of
$H$ because of singularities related to the non-minimum phase character of
$\hat{G}$ (zeros of $\hat{G}$ tend to be very close to the unit circle). A
better estimate can be computed by using a regularized inversion formula [3],
in which a small constant $\beta$ is added to each eigenvalue of $G$ before
inversion:

$H=({\hat{G}^{T}}\hat{G}+{\beta}I)^{-1}\hat{G}^{T}$ (4)

where $\hat{G}^{T}$ is the Hermitian transpose of $\hat{G}$.

After computing $H(e^{j\omega})$ using Eq. (4), Eqs. (2) and (3) yield a
stable and causal approximate inverse $\hat{h}[n]$. The resulting control
point signal vector is

$\hat{X}=G\hat{H}X$

Signals produced during regularized inversion are depicted in Fig. 5. For
illustration, a one-dimensional inverse transfer function is computed from the
simulation $\hat{G}$ and filtered through the simulated transfer function
itself ($\hat{X}=\hat{G}\hat{H}X$). Regularized inversion gives more than $50$
dB of SNR with $D=750$ ms and $\beta=0.05$ (Fig. 5).

Fig. 5:  Inversion process. (a), simulated impulse response $\hat{g}(t)$; (b),
noncausal inverse filter $h(t)$ using regularized inversion; (c), shifted and
truncated inverse filter $\hat{h}(t)$; and (d), dereverberated output
$\hat{x}(t)$ ($x(t)=\delta(t)$.

##  3 Methods

This section describes the design and validation of an open-loop room response
inversion algorithm. Section 3.1 describes methods for acquiring validation
data (measured room responses) using impulse-like excitation signals. Sections
3.2 and 3.3 describe methods for simulating and inverting the room response.

###  3.1 Room response measurement

Because of the deficiencies described in Section 2.1, few papers in recent
decades describe impulse response measurement techniques using impulse-like
excitation signals. For the application considered in this paper, impulse-like
signals have important advantages. Measurement techniques were therefore
developed to minimize their disadvantages.

####  3.1.1 Motivation for the use of starter pistol as an impulse

Using a starter pistol for room response measurement has three advantages over
non-impulse signals using loudspeakers. First, measured response need not be
deconvolved into an impulse response because it is already qualitatively
similar to the room impulse response. Second, the SNR is very high because the
starter pistol exceeds 140 dB SPL at 2 m [34]. For a typical background noise
level of 50 dB SPL, the SNR is 90 dB. In comparison, the MLS method with order
16 and no repetition has only 60.5 dB SNR after parameter optimization and
compensation for nonlinearities [11]. Therefore, inadequate signal energy is
not an issue for a starter pistol. Third, a starter pistol blast approximates
a point source more closely than any other excitation method considered. This
is good for comparing the measured impulse response with the simulation from
the image source method because the latter assumes a point source.

Figure 1 compares the frequency response of a starter pistol, estimated as the
average of ten pistol shots in an anechoic chamber, to the frequency response
of the ambient noise in a room response test chamber (a 2 m plywood cube). The
ambient noise is 70 dB SPL with linear weighting, as measured with a Type 2260
B&K Modular Precision Sound Analyzer.

ISO 3382 specifies a peak SPL at least 45 dB above the background noise in the
frequency range of interest [7]. Even for a noisy 70 dB SPL environment, the
SNR of a starter pistol shot exceeds 45 dB for the frequency range 280 Hz to
11 kHz, and 30 dB for 110 Hz to 20.5 kHz (Fig. 1).

According to the excitation signal requirements described in Sec. 2.1, the
starter pistol still lacks repeatability and omnidirectionality. To use it for
room response measurement, experimental methods must be developed to control
these two deficiencies.

####  3.1.2 Transfer function measurement methods

Our experiment measures the room impulse response of a 2 m plywood-walled
cube. The cube contains only a microphone and starter pistol; all other
measuring equipment is located outside to avoid any disturbance caused by
obstacles inside the cube. The starter pistol is mounted on the end of a
sturdy pipe and triggered from outside the cube by pulling a cable.

There are two different starter pistol and microphone positions, resulting in
a $2\times 2$ matrix transfer function. The exact dimensions of the plywood
cube are $(L_{x},\ L_{y},\ L_{z})$ = (1.84 m, 1.79 m, 1.83 m); table 1 lists
the positions of the starter pistol and microphone. Note that the center of
the cube is (0 m, 0 m, 0 m).

Since waveforms of individual pistol shots are not identical (Fig. 2), we
average multiple measurements at the same location. This repetition has two
benefits. First, we can assume that the averaged impulse response is due to
the averaged excitation. This reduces measurement irregularity, improving
repeatability. Second, SNR improves because the background noise can be
assumed to be independent of room impulse response.

Like any excitation signal, a starter pistol blast is directional. This
variation of signal with respect to angle we label Gun-Related Transfer
Fuction (GRTF). Figure 6 shows the first 1.5 ms of each GRTF.

Fig. 6:  Gun-Related Transfer Functions (GRTFs).

Figure 7 shows the directional pattern computed from the energy at each angle.

Fig. 7:  Directional pattern of the starter pistol blast in normalized linear
scale.

To measure the response of the room to an omnidirectional source, the position
of the starter pistol is fixed and the barrel is rotated to positions
$30^{\circ}$ apart, where $0^{\circ}$ is directly toward the microphone,
averaging five impulse responses at each angle. The experiment uses 12
rotation angles, so a total of 60 shots determine the room impulse response
from one point to another point.

###  3.2 Room response simulation

It is impractical to directly measure all the room impulse responses from
every loudspeaker position to every mesh point: only eight loudspeakers and a
$10\times 10\times 10$ mesh demand 8000 experiments. Instead, inverse transfer
functions are derived from approximate room responses simulated with the image
source method. This then demands verification of the simulation, using error
metrics to compare corresponding pairs of measured and simulated responses.

Parameters of the image source simulation include the room dimensions, the
position of the sound source and receivers, the speed of sound (dependent on
temperature and relative humidity[35]), and the reflection coefficient $r$ of
the wall material (Eq. (1)). Although $r$ varies with frequency, modeling the
frequency dependence greatly increases the computational cost of the
simulation. All simulations reported in this paper therefore assume a
frequency-independent $r$, related to the average Sabine absorptivity
$\bar{a}$: [4]

$\bar{a}=1-r^{2}$

The value of $\bar{a}$ is optimized experimentally.

The simulation uses a sampling frequency of 44.1 kHz. The length of the
simulated impulse response is 65536 samples, about 1.5 seconds. The speed of
sound is taken to be 346.58 m/s, based on Cramer's equation evaluated at the
temperature and relative humidity measured in the plywood cube
($24.4^{\circ}$C$,37.5\%$) [35].

Room response simulations were evaluated using three metrics: local mean-
squared error (described here), global and local dereverberation ratios
(described in the next section), and remainder reverberation time (described
in the next section). Mean-squared error measures time-domain similarity,
i.e., how alike the amplitude-versus-time graphs of the two responses look.
For an $M$ sample interval starting at the $k^{th}$ sample, this error is
expressed as

$E_{ms}[k]=\frac{1}{M}\sum_{n=k}^{k+M-1}\left(\frac{\hat{g}[n]}{\hat{g}_{rms}}-\frac{g[n]}{g_{rms}}\right)^{2}$
(5)

where $\hat{g}[n]$ and $g[n]$ are the simulation and measurement of the room
impulse responses, and $\hat{g}_{rms}$ and $g_{rms}$ are their RMS values in
the interval $[k,k+M-1]$.

For an actual room response $G_{orig}(z)$ and an excitation signal spectrum
$S(z)$, the measured room response is $G(z)=S(z)G_{orig}(z)$. When the
excitation signal is a starter pistol, $S(z)$ may be measured by recording the
pistol impulse response $s(t)$ in an anechoic chamber; when the excitation
signal is pseudo-noise or a sine sweep, $S(z)$ must be computed by multiplying
the theoretical pseudo-noise spectrum with the loudspeaker frequency response.
Pseudo-noise room response measurement techniques may then compare
$G(z)S(z)^{-1}$, the source-corrected room response, with $\hat{G}(z)$, the
simulated room response. When $S(z)$ is the spectrum of a starter pistol,
however, $S(z)^{-1}$ has undesirable properties (it is high-pass, noncausal,
and nearly singular), so the ``source-corrected'' room response $g(t)\ast
s(t)^{-1}$ is difficult to evaluate visually. Conversely, because $s(t)$ is
impulse-like, visual comparison of the measured response $g(t)$ with
$\hat{g}(t)\ast s(t)$ (the measured excitation filtered by simulated response)
is natural and meaningful.

Fig. 8:  Experiment setup.

Figure 9 compares the first 20 ms of two impulse responses from starter pistol
position 2 to microphone position 1 (see Fig. 8 and table 1). The upper plot
shows $g(t)$, the average of the 60 measured impulse responses. The lower plot
is $\hat{g}(t)\ast s(t)$, where $\hat{g}(t)$ is computed using the image
source method. The very close match between these two impulse responses
validates both the image source method and the angle-averaged pistol
measurement.

Fig. 9:  First 20 ms of measured and simulated impulse responses.

The simulation preserves the peak locations closely even after 100 ms (Fig.
10), but the visual similarity of the signals is not as great as during the
first 20 ms (Fig. 9).

Fig. 10:  Measured and simulated impulse responses after 100 ms.

The increasing dissimilarity between $g(t)$ and $\hat{g}(t)\ast s(t)$ as $t$
increases is quantified by a gradual increase in the local mean-squared error
of the simulation, computed using Eq. (5) with intervals of $20$ and $100$ ms
(Fig. 11). This time-dependent dissimilarity may be explained by considering
the accumulated effect on $g(t)$ of frequency-dependent wall reflections and
air propagation filtering. $\hat{g}(t)$ is computed using the time-domain
image source method, which does not model frequency-dependent wall reflections
and air propagation.

Fig. 11:  Mean-squared error between simulation and measurement.

Figure 12 shows the filtering effect of wall reflections on the spectrum of a
single acoustic ray. After only one reflection, frequencies below 10 Hz are
attenuated 20 dB relative to frequencies above 100 Hz [36]. After ten
reflections (70 to 100 ms), frequencies below 100 Hz are effectively zeroed.
Figure 13 shows the filtering effect of propagation through air at
$20^{\circ}$ C and 30% relative humidity [37]. After 34.3 m (100 ms), spectral
components at 10 kHz are attenuated about 8 dB. The attenuation due to wall
reflections and air propagation is enormous even after 100 ms.

Fig. 12:  Frequency response after one, two, and ten wall reflections.
(Circled data points are adapted from [36].)

Fig. 13:  Frequency response of propagation through air at $20\deg$ C, 30%
relative humidity after 1 m, 34.3 m, and 343 m. (Circled data points are
adapted from [37].)

###  3.3 Room response inversion

Room responses simulated using the image source method are next inverted using
the method of regularized inversion with modeling delay [3]. Experiments
indicate that effective inversion requires $\beta>0$, but that the exact value
of $\beta$ in the range $10^{-4}\leq\beta\leq 1$ has little effect on
inversion performance. The value of the modeling delay $D$ is more important.
Inversion results improve almost monotonically as $D$ increases, suggesting
that $D$ be the longest modeling delay imperceptible to users. Results in this
paper use $\beta=10^{-2}$ and $D=500$ ms. Finally, Eq. (4) may be used for
either scalar inversion (one speaker, one control point) or matrix room
response inversion ($L$ speakers, $M$ control points). This paper reports
results of both scalar and matrix inversion experiments, where matrix
inversion is performed with $L=2$, $M=2$ using the geometry shown in Fig. 8
and table 1.

####  3.3.1 Evaluation of room impulse response inversion

Room response inversion can eliminate the perceptual ``signature'' of a room
by attenuating early echoes; it can also reduce long-term reverberant energy.

The early echoes should be well suppressed because they characterize the
perceived geometry of the room. The later portion of the room response is
related more to wall material and room size than to specific room geometry.

Assuming that the desired signal $x(t)$ at a certain location is an impulse,
the output $\hat{x}(t)$ at that location needs to be as close to an impulse as
possible: it should contain as little energy as possible at time $t\neq 0$.
The output is expressed as $\hat{X}=G\hat{H}X$ where $G$ is a measured impulse
response and $\hat{H}$ is the approximate inverse filter created from the
simulation $\hat{G}$ using Eqs. (2), (3), and (4). The time-domain expression
of the output is

$\hat{x}(t)=g(t)\ast\hat{h}(t)\ast x(t)$

or, for matrix inversion experiments,

$\hat{x}_{k}(t)=\sum_{j=1}^{L}\sum_{i=1}^{M}g_{kj}(t)\ast\hat{h}_{ji}(t)\ast
x_{i}(t)$

To claim that the inverse filter dereverberates the room impulse response, for
an input $x(t)=\delta(t)$, the filtered output $\hat{x}(t)=\hat{h}(t)\ast
g(t)$ should be similar to a delayed impulse, $\hat{x}(t)\approx\delta(t-D)$.
The success of dereverberation may be measured by computing the residual
energy in the signal $\hat{x}(t)$ at times $|t-D|>T_{min}$, for some small
value of $T_{min}$. The residual energy in $\hat{x}(t)$ is computed as

$E_{resid}(\infty)=\int_{T_{min}<|t-D|}\hat{x}^{2}(t)dt$

``Early echoes'' may be defined to be causal or noncausal echoes within a time
window $|t-D|<T$. The residual energy within $T$ seconds is computed as

$E_{resid}(T)=\int_{T_{min}<|t-D|<T}\hat{x}^{2}(t)dt$

The efficacy of the dereverberation is described by the ``dereverberation
ratio'' (DR): the ratio of the original room response energy
$\int_{T_{min}}^{T}g^{2}(t)$ to the residual energy, thus,

$DR(\infty)=10\log_{10}\frac{\int_{T_{min}}^{\infty}g^{2}(t)dt}{\int_{T_{min}<|t-D|}\hat{x}^{2}(t)dt}$
$DR(T)=10\log_{10}\frac{\int_{T_{min}}^{T}g^{2}(t)dt}{\int_{T_{min}<|t-D|<T}\hat{x}^{2}(t)dt}$

For the output $\hat{x}(t)$ to have less energy than the measured impulse
response $g(t)$, both decibel ratios should be positive. They can therefore be
used to evaluate and optimize the simulation and inversion of the room impulse
responses.

Simulation and inversion can also be evaluated using the remainder
reverberation time $T_{L}$, defined implicitly as

$L=10\log_{10}\frac{\int_{0}^{\infty}g^{2}(t)dt}{\int_{T_{L}}^{\infty}\hat{x}^{2}(t)dt}$

The remainder reverberation times $T_{10}$, $T_{20}$, and $T_{60}$ of both
measured and dereverberated outputs will be compared. The reference for the
remainder reverberation time is the integrated energy of the measured room
impulse response $g(t)$.

####  3.3.2 Optimization of the window for for impulse response inversion

An inverse filter created using a complete 1.5 second simulation of the room
response fails: the energy of the dereverberated output exceeds the energy of
the measured impulse response.

The mean-squared error with respect to time ($E_{ms}$) indicates that the
accuracy of the image source simulation decreases with time (Fig. 11). This
suggests that the dereverberation ratio may improve by applying a tapering
window, such as an exponential with time constant $\tau$:

$\tilde{g}(t)=e^{-t/\tau}\hat{g}(t)$

Figure 14 shows the dereverberation ratios $DR(\infty)$ and $DR(100$ ms) for
both scalar and matrix inversion, using $\tilde{g}(t)$ instead of $\hat{g}(t)$
in order to create the inverse filter, with values of $\tau$ = 0.01, 0.02,
0.04, 0.08, 0.16, 0.32, and 0.64 s.

Fig. 14:  Dereverberation ratios with respect to the time constant. Upper
graphs, scalar inversion; lower graphs, matrix inversion.

According to the dereverberation ratios depicted above, $\tau=0.06$ s is close
to optimal.

##  4 Results

Two measures are used to discuss the inversion results. First, the total and
the early dereverberation ratios $DR(\infty)$ and $DR(T)$ are compared.
Second, the remainder reverberation times $T_{10}$, $T_{20}$, and $T_{60}$ of
measured and dereverberated responses are compared.

Results of scalar inversion for four different impulse responses and of matrix
inversion of a $2\times 2$ matrix transfer function are presented here. The
four different room response geometries used for both scalar and matrix
inversion may be numbered as follows, with reference to Fig. 8 and table 1:
Impulse response number I, pistol 1 to microphone 1; II, pistol 1 to
microphone 2; III, pistol 2 to microphone 1; and IV, pistol 2 to microphone 2.
For $2\times 2$ matrix inversion, room responses at microphone location 1 and
2 are called microphone 1 and microphone 2 respectively.

Table 1: Positions (in meters) of pistol and microphone in plywood cube. | Position 1 | Position 2
---|---|---
Pistol | $(0.26,\ 0.30,\ -0.15)$ | $(-0.26,\ -0.30,\ -0.15)$
Microphone | $(-0.57,\ 0.58,\ 0.31)$ | $(-0.39,\ 0.58,\ 0.31)$
|  |

Section 4.1 describes experiments designed to optimize and validate the image
source method. Section 4.2 describes scalar inversion results with and without
windowing the simulated room response. Section 4.3 describes $2\times 2$
matrix inversion results with windowing.

###  4.1 Optimization of absorption coefficient

When all interior surfaces of the room are covered with the same material and
the reverberation time is known, average Sabine absorptivity $\bar{a}$ is
given directly by Sabine's formula

$\bar{a}=\frac{0.161V}{ST_{60}}$

where $V$ and $S$ are the volume and the surface area of the room respectively
[36].

The measured $T_{60}$ of the 2 m plywood cube using Schroeder's integration
formula [38] is 1.32 s, yielding $\bar{a}=0.0407$. Since this is merely an
estimation from Sabine's formula, it was bracketed with values 0.01, 0.02,
0.04, 0.08, and 0.16.

Figure 15 shows that dereverberation ratios are not affected by the modeled
absorption coefficient $\bar{a}$. This indicates that the phase information of
the room impulse response is more important than the magnitude information,
i.e., for inversion the exact timing of the reflections is more important than
their magnitudes.

Fig. 15:  Dereverberation ratios with respect to absorption coefficient
$\bar{a}$.

###  4.2 Scalar inversion with and without windowing

Scalar inversion was performed both without and with exponential windowing of
the simulated response. Figure 16 depicts the measured impulse response and
the response ``dereverberated'' without windowing from starter pistol location
1 to microphone location 2 (impulse response number II). Table 2 shows that
the supposedly dereverberated impulse responses have approximately 10 dB more
energy than the measured impulse responses; so dereverberation fails when no
tapering window is applied to the simulated impulse reponses.

Fig. 16:  Linear plots of measured and dereverberated impulse responses
(scalar inversion; impulse response number III). No windowing is applied to
the simulated impulse response $\hat{g}(t)$.

Figure 17 depicts the results of dereverberation, where simulated impulse
responses are windowed by an exponential window with time constant $\tau=0.06$
s. Table 2 shows that the dereverberated impulse responses have from $8.11$ to
$10.98$ dB less energy than the measured impulse responses; dereverberation
works.

Fig. 17:  Measured and dereverberated impulse responses (scalar inversion; impulse response number III). An exponential window with time constant $\tau=0.06$ s is applied to the simulated impulse response $\hat{g}(t)$. Table 2: Dereverberation ratios in dB of dereverberated impulse responses. | Non-windowed | Windowed
---|---|---
| $DR(\infty)$ |  $DR(100$ ms$)$ | $DR(\infty)$ |  $DR(100$ ms$)$
I | $-8.95$ | $-9.03$ | $10.98$ | $11.45$
II | $-10.54$ | $-9.85$ | $10.56$ | $10.84$
III | $-10.11$ | $-10.04$ | $8.11$ | $8.30$
IV | $-8.88$ | $-8.60$ | $10.56$ | $10.84$
|  |  |  |

Figure 18 shows integrated energy decay curves of four different
dereverberated impulse responses with respect to the measured impulse
resposes; table 3 lists the dereverberation times of scalar inversion
according to these decay curves.

Fig. 18:  Integrated energy decay curves for scalar inversion. Solid line is measured response; dashed line is dereverberated response. Table 3: Remainder reverberation times $T_{10}$, $T_{20}$, and $T_{60}$, in seconds, of measured and dereverberated impulse responses; scalar inversion. | Measured responses | Dereverberated responses
---|---|---
| $T_{10}$ | $T_{20}$ | $T_{60}$ | $T_{10}$ | $T_{20}$ | $T_{60}$
I | $0.20$ | $0.39$ | $1.39$ | $0.02$ | $0.20$ | $1.21$
II | $0.18$ | $0.38$ | $1.31$ | $0.02$ | $0.18$ | $1.12$
III | $0.19$ | $0.39$ | $1.35$ | $0.04$ | $0.24$ | $1.19$
IV | $0.18$ | $0.36$ | $1.23$ | $0.02$ | $0.19$ | $1.26$
|  |  |  |  |  |

###  4.3 Matrix inversion with windowed simulation

Figures 19 and 20 depict $2\times 2$ matrix inversion results; dereverberation
ratios are in table 4. Remainder reverberation energy decay curve and
corresponding remainder reverberation times ($T_{10}$, $T_{20}$, and $T_{60}$)
are shown in Fig. 21 and table 5.

Fig. 19:  Linear plots of measured and dereverberated impulse responses
($2\times 2$ matrix inversion). An exponential window with time constant
$\tau=0.06$ s is applied to the simulated impulse response $\hat{g}(t)$.

Fig. 20:  Decibel plots of measured and dereverberated impulse responses ($2\times 2$ matrix inversion). An exponential window with time constant $\tau=0.06$ s is applied to the simulated impulse response $\hat{g}(t)$. Table 4: Dereverberation ratios in dB of dereverberated impulse responses; matrix inversion. | Microphone 1 | Microphone 2
---|---|---
$DR(\infty)$ | $8.64$ | $12.04$
$DR(100$ ms$)$ | $8.83$ | $12.19$
|  |

Fig. 21:  Integrated energy decay curves for $2\times 2$ matrix inversion. Solid line is measured response; dashed line is dereverberated response. Table 5: Remainder reverberation times $T_{10}$, $T_{20}$, and $T_{60}$, in seconds, of measured and dereverberated impulse responses; matrix inversion. | Measured responses | Dereverberated responses
---|---|---
| Microphone 1 | Microphone 2 | Microphone 1 | Microphone 2
$T_{10}$ | $0.19$ | $0.16$ | $0.02$ | $0.02$
$T_{20}$ | $0.39$ | $0.36$ | $0.26$ | $0.20$
$T_{60}$ | $1.37$ | $1.22$ | $1.26$ | $1.27$
|  |  |  |

##  5 Conclusion

This paper describes experiments in open-loop room response inversion for the
purpose of headphone-free virtual reality audio display. Room responses were
simulated using the image source method and inverted using a regularized
Fourier transform inversion with a modeling delay of 500 ms. Scalar room
response inversion provided an average of 10.1 dB of short-term
dereverberation (early echoes within 100 ms of the direct sound), and 10.4 dB
of long-term dereverberation. Matrix room response inversion (two inputs, two
outputs) provided an average of 10.5 dB short-term and 10.3 dB long-term
dereverberation.

##  6 Acknowledgments

This work was supported in part by a grant from the University of Illinois
Research Board, and in part by funding from the University of Illinois Beckman
Institute. We thank Hank Kaczmarski for hardware assistance.

## References

  * [1] C. Cruz-Neira, D. J. Sandin, and T. A. DeFanti, ``Surround-screen projection-based virtual reality: the design and implementation of the CAVE,'' Proc. ACM Special Interest Group on Computer Graphics and Interactive Techniques (SIGGRAPH),135–142 (1993).
  * [2] M. Miyoshi and Y. Kaneda, ``Inverse filtering of room acoustics,'' IEEE Trans. Acoustics, Speech and Signal Proc. 36(2), 145–152 (1988).
  * [3] O. Kirkeby, P. A. Nelson, H. Hamada, and F. Orduna-Bustamente, ``Fast deconvolution of multichannel systems using regularization,'' IEEE Trans. Speech and Audio Processing 6(2), 189–194 (1998).
  * [4] J. B. Allen and D. A. Berkley, ``Image method for efficiently simulating small-room acoustics,'' J. Acoust. Soc. Am. 65(4), 912–915 (1979).
  * [5] S. T. Neely and J. B. Allen, ``Invertibility of a room impulse response,'' J. Acoust. Soc. Am. 66(1), 165–169 (1979).
  * [6] A. Omoto, C. Hiratsuka, H. Fujita, T. Fukushima, M. Nakahara, and K. Fujiwara, ``Similarity evaluation of room acoustic impulse responses: Visual and auditory impressions,'' J. Audio. Eng. Soc. 50(6), 451–457 (2002).
  * [7] ISO 3382, Acoustics - Measurement of the reverberation time of rooms with reference to other acoustical parameters, ISO, 1997.
  * [8] M. R. Schroeder, ``Integrated-impulse method measuring sound decay without using impulses,'' J. Acoust. Soc. Am. 66(2), 497–500 (1979).
  * [9] D. D. Rife and J. Vanderkooy, ``Transfer-function measurement with maximum-length sequences,'' J. Audio. Eng. Soc. 37(6), 419–444 (1989).
  * [10] J. Vanderkooy, ``Aspects of MLS measuring systems,'' J. Audio. Eng. Soc. 42(4), 219–231 (1994).
  * [11] G.-B. Stan, J.-J. Embrechts, and D. Archambeau, ``Comparison of different impulse response measurement techniques,'' J. Audio. Eng. Soc. 50(4), 249–262 (2002).
  * [12] C. Dunn and M. O. Hawksford, ``Distortion immunity of MLS-derived impulse response measurements,'' J. Audio. Eng. Soc. 41(5), 314–335 (1993).
  * [13] N. Ream, ``Nonlinear identification using inverse-repeat m sequences,'' Proc. IEE (London) 117(1), 213–218 (1970).
  * [14] P. A. N. Briggs and K. R. Godfrey, ``Pseudorandom signals for the dynamic analysis of multivariable systems,'' Proc. IEE 113, 1259–1267 (1966).
  * [15] H. R. Simpson, ``Statistical properties of a class of pseudorandom sequence,'' Proc. IEE (London) 113, 2075–2080 (1966).
  * [16] C. Bleakley and R. Scaife, ``New formulas for predicting the accuracy of acoustical measurements made in noisy environments using the averaged m-sequence correlation technique,'' J. Acoust. Soc. Am. 97(2), 1329–1332 (1995).
  * [17] H. Alrutz and M. R. Schroeder, ``A fast Hadamard transform method for the evaluation of measurements using pseudorandom test signals,'' Proc. 11th Int. Congress on Acoustics (Paris) 6, 235–238 (1983).
  * [18] M. Cohn and A. Lempel, ``On fast M-sequence transforms,'' IEEE Trans. Inform. Theory 23(1), 135–137 (1977).
  * [19] W. D. T. Davies, ``Generation and properties of maximum-length sequences, part 1,'' Control 10(96), 302–304 (1966).
  * [20] W. D. T. Davies, ``Generation and properties of maximum-length sequences, part 2,'' Control 10(97), 364–365 (1966).
  * [21] W. D. T. Davies, ``Generation and properties of maximum-length sequences, part 3,'' Control 10(98), 431–433 (1966).
  * [22] D. D. Rife, ``Modulation transfer function measurement with maximum-length sequences,'' J. Audio. Eng. Soc. 40(10), 779–790 (1992).
  * [23] M. Vorländer and M. Kob, ``Practical aspects of MLS measurements in building acoustics,'' Appl. Acoustics 52(3-4), 239–258 (1997).
  * [24] R. Burkard, Y. Shi, and K. E. Hecox, ``A comparison of maximum length and Legendre sequences for the derivation of brain-stem auditory-evoked responses at rapid rates of stimulation,'' J. Acoust. Soc. Am. 87(4), 1656–1664 (1990).
  * [25] N. Aoshima, ``Computer-generated pulse signal applied for sound measurement,'' J. Acoust. Soc. Am. 69(5), 1484–1488 (1981).
  * [26] A. J. Berkhout, D. de Vries, and M. M. Boone, ``A new method to acquire impulse responses in concert halls,'' J. Acoust. Soc. Am. 68(1), 179–183 (1980).
  * [27] A. Farina, ``Simultaneous measurement of impulse response and distortion with a swept-sine technique,'' J. Audio. Eng. Soc. 48, 350 (2000).
  * [28] R. Rabenstein and A. Zayati, ``A direct method to computational acoustics,'' IEEE Proc. Int. Conf. Acoustics, Speech and Signal Processing (ICASSP 99) 2, 957–960 (1999).
  * [29] T. Schetelig and R. Rabenstein, ``Simulation of three-dimensional sound propagation with multidimensional wave digital filters,'' IEEE Proc. Int. Conf. Acoustics, Speech and Signal Processing (ICASSP 98) 6, 3537–3540 (1998).
  * [30] A. Krokstad, S. Strøm, and S. Sørsdal, ``Calculating the acoustical room response by the use of a ray tracing technique,'' J. Sound Vib. 8(1), 118–125 (1968).
  * [31] J. Borish, ``Extension of the image model to arbitrary polyhedra,'' J. Acoust. Soc. Am. 75(6), 1827–1836 (1984).
  * [32] H. Lee and B.-H. Lee, ``An efficient algoritm for the image model technique,'' Applied Acoustics 24, 87–115 (1988).
  * [33] P. A. Nelson, H. Hamada, and S. J. Elliott, ``Adaptive inverse filters for stereophonic sound reproduction,'' IEEE Trans. Signal Processing 40(7), 1621–1632 (1992).
  * [34] Database for assessing the annoyance of the noise of small arms, United States Army Environmental Hygiene Agency, 1983.
  * [35] O. Cramer, ``The variation of the specific heat ratio and the speed of sound in air with temperature, pressure, humidity, and CO2 concentration,'' J. Acoust. Soc. Am. 93(5), 2510–2514 (1993).
  * [36] L. E. Kinsler, A. R. Frey, A. B. Coppens, and J. V. Sanders, Fundamentals of Acoustics, 4th ed. (Wiley and Sons, Inc., New York, 2000).
  * [37] CRC Handbook of Chemistry and Physics, 79th ed., edited by D. R. Lide (CRC Press, Boca Raton, 1998).
  * [38] M. R. Schroeder, ``New method of measuring reveberation time,'' J. Acoust. Soc. Am. 37(3), 409–412 (1965).


# Bounds of the Radio Number of Stacked-Book Graph with Odd Paths

Tayo Charles Adefokun1 1Department of Computer and Mathematical Sciences,
Crawford University,
Nigeria<EMAIL_ADDRESS>and  Deborah Olayide Ajayi2
2Department of Mathematics,
University of Ibadan,
Ibadan,
Nigeria<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

A Stacked-book graph $G_{m,n}$ is obtained from the Cartesian product of a
star graph $S_{m}$ and a path $P_{n}$, where $m$ and $s$ are the orders of the
star graph and the path respectively. Obtaining the radio number of a graph is
a rigorous process, which is dependent on diameter of $G$ and positive
difference of non-negative integer labels $f(u)$ and $f(v)$ assigned to any
two $u,v$ in the vertex set $V(G)$ of $G$. This paper obtains tight upper and
lower bounds of the radio number of $G_{m,n}$ where the path $P_{n}$ has an
odd order. The case where $P_{n}$ has an even order has been investigated.

###### Key words and phrases:

L(1,1)-labeling, D-2 Coloring, Direct Product of Graphs, Cross Product of
Graphs
2010 Mathematics Subject Classification. Primary: 05C35

##  1\. Introduction

All graphs mentioned in this work are simple and undirected. The vertex and
edge sets of a graph $G$ are designated as $V(G)$ and $E(G)$ respectively and
$e=uv\in E(G)$ connects $u,v\in V(G)$ while $d(u,v)$ denotes the shortest
distance between $u,v\in V(G)$. We represent the diameter of $G$ as
$\rm{diam}(G)$.

Radio labeling, which often aims to solve signal interference problems in a
wireless network, was first suggested in 1980 by Hale [7] and it is described
as follows: Suppose that $f$ is a non negative integer function on $V(G)$ and
that $f$ satisfies the radio labeling condition,
$|f(u)-f(v)|\geq\rm{diam}(G)+1-d(u,v)$, for every pair $u,v\in V(G)$. The
span$f$ of $f$ is $f_{max}(G)-f_{min}(G)$, where $f_{max}$ and $f_{min}$ are
largest and lowest labels, respectively, assigned on $V(G)$ and the lowest
value of span$f$ is the radio number, $rn(G)$, of $G$. It is established that
to obtain the radio numbers of graphs is hard. However, for certain graphs,
the radio numbers have been obtained. Recent results on radio number include
those on middle graph of path [3], trees, [4] and edge-joint graphs [12]. Liu
and Zhu [11] showed that for path, $P_{n}$, $n\geq 3$,

$rn(P_{n})=\left\\{\begin{array}[]{ll}2k(k-1)+1&\mbox{if}\;\;n=2k;\\\
2k^{2}+2&\mbox{if}\;\;n=2k+1.\par\end{array}\right.$

Liu and Zhu’s results compliment those obtained by Chatrand et. al. in [5] and
[6] about the same graph. Liu and Xie worked on square graphs. In [9], they
obtained $rn(P_{n}^{2})$ of square of path as follows:

$rn(P^{2}_{n})=\left\\{\begin{array}[]{ll}k^{2}+2&\mbox{if}\;\;n\equiv
1(\rm{mod}\;4),n\geq 9;\\\
k^{2}+1&\mbox{if}\;\;\rm{otherwise}.\par\end{array}\right.$

Other results on squares of graphs include those obtained for $C_{n}^{2}$ in
[10], where $C_{n}$ is a cycle of order $n$. On Cartesian products graphs,
Jiang [8] solved the radio number problem for $(P_{m}\Box P_{n})$, where for
$m,n>2$, and obtains $rn(P_{m}\Box P_{n})=\frac{mn^{2}+nm^{2}-n}{2}-mn-m+2$,
for $m$ odd and $n$ even. Saha and Panigrahi [13] worked on Cartesian products
of Cycles while Ajayi and Adefokun in [1] and [2] probe on the radio number of
the Cartesian product of path and star graph called the stacked-book graph
$G=S_{m}\Box P_{n}$. They observed in [1] that $rn(S_{m}\Box P_{n})\leq
n^{2}m+1$, a result the authors noted, citing a existing result in [8], is not
a tight bound.)In [1], they obtained improve the results in [1], for path
$P_{n}$, where $n$ is even.

In this paper, we investigate further on the radio number of stacked-book
graphs, $S_{m}\Box P_{n}$, in the case where $n$ is odd and combined with [2],
we improve the weak bounds obtained in [1].

##  2\. Preliminaries

Let $S_{m}$ be a star of order $m\geq 3$ and let $v_{1}$ be the center vertex
of $S_{m}$ and $v_{2},v_{3},\cdots,v_{m}$ are adjacent to $v_{1}$ and let
$P_{n}$ be a path containing $n$ vertices starting from $u_{1}$ to $u_{n}$.
Furthermore, $P=u\stackrel{{\scriptstyle
a}}{{\longrightarrow}}v\stackrel{{\scriptstyle b}}{{\longrightarrow}}w$
represents a path of length $a+b$, for which $d(u,v)=a$ and $d(u,w)=b$. If a
stacked-book graph is obtained from the Cartesian product $G_{m,n}=S_{m}\Box
P_{n}$ of $S_{m}$ and $P_{n}$, then $V(G_{m,n})$ is the Cartesian product of
$V(S_{m})$ and $V(P_{n})$, for which if $u_{i}v_{j}\in V(G_{m,n})$, then
$u_{i}\in V(S_{m})$, $v_{j}\in E(P_{n})$, while, if $u_{i}v_{j}u_{k}v_{i}$
forms an edge in $E(G_{m,n})$, then $u_{i}=u_{k}$ and $v_{j}v_{l}\in E(P_{n})$
or $v_{j}=v_{l}$ and $u_{i}u_{k}\in E(S_{m})$.

Some of the following are adopted from [2].

######  Definition 2.1.

Where it is convenient, we write $u_{i}v_{j}$ as $u_{ij}$ and therefore the
edge $u_{i}v_{j}u_{k}v_{l}$ as $u_{ij}u_{kl}$.

######  Remark 2.1.

Stacked-book graph $G_{m,n}$ contains $n$ number of $S_{m}$ stars as contained
in the set $\left\\{S_{m(i)}:i\leq 0\leq n\right\\}$.

######  Definition 2.2.

For $G_{m,n}=S_{m}\Box P_{n}$, $V_{(i)}\subset V(G_{m,n})$ is the set of
vertices on $S_{m(i)}$ stated as
$V_{(i)}={u_{1}v_{i},u_{2}v_{i},\cdots,u_{m}v_{i}}$.

######  Remark 2.2.

We must mention that $u_{1}v_{i}$ in the set in the last definition is the
center vertex of $S_{m}(i)$.

######  Definition 2.3.

Let $G_{m,n}=S_{m}\Box P_{n}$, $n$ odd, the pair
${S_{m(i)}},S_{m(i+\frac{n-1}{2})}$ is a subgraph
$G^{\prime\prime}(i)\subseteq G_{m,n}$, which is induced by $V_{i}$ and
$V_{i+\frac{n-1}{2}}$, where $i\notin\\{1,\frac{n+1}{2},n\\}$.

######  Remark 2.3.

It can be seen that with $n$ odd, every $G_{m,n}$ contains $\frac{n-2}{3}$
number of $G^{\prime\prime}(i)$ subgraphs and the diameter
$diam(G^{\prime\prime}(i))$ of $G^{\prime\prime}(i)$ is $\frac{n+3}{3}$.

Next, we introduce the following definitions:

######  Definition 2.4.

Let $G_{m,n}=S_{m}\Box P_{n}$. Then, $\bar{G}_{m,n}\subseteq G_{m,n}$ is a
subgraph of $G_{m,n}$ induced by the stars
${S_{m(1)},S_{m(\frac{n+1}{2})},S_{n}}$.

We now define a class of paths $P^{\prime}(i)$.

######  Definition 2.5.

Let $\left\\{P^{\prime}(t)\right\\}^{m}_{t=1}$ be a class of paths in
$G_{m,n}$, where
$P^{\prime}(t):=v_{j(1)}\stackrel{{\scriptstyle\alpha}}{{\longrightarrow}}v_{k(\frac{n+1}{2})}\stackrel{{\scriptstyle\beta}}{{\longrightarrow}}v_{l(n)}$,
such that $j\neq k\neq l$, $v_{j(1)}\in V_{(i)},v_{k(\frac{n+1}{2})}\in
V_{(\frac{n+1}{2})}$ and $v_{l(n)}\in V_{(n)}$ and $1\leq j,k,l\leq m$.

It can be verified that $\left\\{P^{\prime}(t)\right\\}^{m}_{t=1}$ contains
two other sub-classes defined without loss of generality as follows:

$P^{\prime}_{1}(t)=\\{v_{1(1)}\stackrel{{\scriptstyle\frac{n+1}{2}}}{{\longrightarrow}}v_{3(\frac{n+1}{2})}\stackrel{{\scriptstyle\frac{n+3}{2}}}{{\longrightarrow}}v_{2(n)},v_{2(1)}\stackrel{{\scriptstyle\frac{n+1}{2}}}{{\longrightarrow}}v_{1(\frac{n+1}{2})}\stackrel{{\scriptstyle\frac{n+1}{2}}}{{\longrightarrow}}v_{3(n)},v_{3(1)}\stackrel{{\scriptstyle\frac{n+3}{2}}}{{\longrightarrow}}v_{2(\frac{n+1}{2})}\stackrel{{\scriptstyle\frac{n+1}{2}}}{{\longrightarrow}}v_{1(n)}\\}$

$P^{\prime}_{2}(t)=v_{a(1)}\stackrel{{\scriptstyle\frac{n+3}{2}}}{{\longrightarrow}}v_{b(\frac{n+1}{2})}\stackrel{{\scriptstyle\frac{n+3}{2}}}{{\longrightarrow}}v_{c(n)}$,
$a\neq b\neq c$, $4\leq a,b,c\leq m$. Clearly, $|P^{\prime}_{1}(t)|=3$ and
$|P^{\prime}_{2}(t)|=m-2$.

##  3\. Results

In the next results, we establish a lower bound of the radio number
$rn(G_{m,n})$ of a stacked-book graph $G_{m,n}$.

######  Lemma 3.1.

Let $f$ the radio labeling function on $G_{m,n}$, $n$ odd, and let
$V_{(\frac{n+1}{2})}=\left\\{v_{1(\frac{n+1}{2})},v_{2(\frac{n+1}{2})},v_{3(\frac{n+1}{2})},\left\\{v_{d(\frac{n+1}{2}):4\leq
d\leq m)}\right\\}\right\\}$ be the vertex set of the mid vertices in
$P(t)\subseteq\left\\{P^{\prime}(t)\right\\}^{m}_{t=1}$. Now, let $v\in
V_{\frac{n+1}{2}}$ be some vertex in $V_{\frac{n+1}{2}}$. If $f(v)$ is
$f_{max}$ on $V(P(t))$, then

$f(v)=\left\\{\begin{array}[]{ll}\frac{n+5}{2}&\mbox{if}\;\;v\in\left\\{v_{1(\frac{n+1}{2})},v_{2(\frac{n+1}{2})},v_{3(\frac{n+1}{2})}\right\\};\\\
\frac{n+3}{2}&\rm{otherwise}.\par\end{array}\right.$

###### Proof.

Since $P(t)\subset G_{m,n}$, then, radio labeling of any vertex on $V(P(t))$
is based on $diam(G_{m,n})$ and for $u,v\in V(P(t))$, $d(u,v)=k$, where $k$ is
the distance between $u$ and $v$ in $G_{m,n}$. We consider the three paths in
$P^{\prime}_{1}(t)$ next.

Case 1(a). For
$P^{\prime}_{1}(1):=v_{1(1)}\stackrel{{\scriptstyle\frac{n+1}{2}}}{{\longrightarrow}}v_{3(\frac{n+1}{2})}\stackrel{{\scriptstyle\frac{n+3}{2}}}{{\longrightarrow}}v_{2(n)}$,
let $f(v_{1(1)})=0$. Now $d(v_{1(1)},v_{2(n)})=n$. Therefore $f(v_{2(n)})\geq
f(v_{1(1)})+diam(G_{m,n})+1-n$=2. Also,
$d(v_{2(n)},v_{3(\frac{n+1}{2})})=\frac{n+3}{2}$ and thus,
$f(v_{3(\frac{n+1}{2})})\geq
f(v_{2(n)})+dim(G_{m,n})+1-\frac{n+3}{2}\geq\frac{n+5}{2}$. (It should be note
that if we set $f(v_{2(n)})=0,$ then,
$f(v_{3(\frac{n+1}{2})})\geq\frac{n+7}{2}$.)

Case 1(b). For
$P^{\prime}_{1}(2):=v_{2(1)}\stackrel{{\scriptstyle\frac{n+1}{2}}}{{\longrightarrow}}v_{1(\frac{n+1}{2})}\stackrel{{\scriptstyle\frac{n+1}{2}}}{{\longrightarrow}}v_{3(n)}$,
let $f(v_{2(1)})=0$, then $d(v_{2(1)},v_{3(n)})=n+1$ and thus,
$f(v_{3}(n))\geq n+2-(n+1)=1$. Likewise,
$d(v_{3(n)},v_{1(\frac{n+1}{2})})=\frac{n+2}{2}$ and therefore,
$f(v_{3(n)})\geq n+3-(\frac{n+1}{2})=\frac{n+5}{2}$.

105025Figure 1. Illustration of Case 1(a) and (b) in a $G_{5,5}$ Stacked-book
Graph

Case 1(c). Now for
$P^{\prime}_{1}(3):=v_{3(1)}\stackrel{{\scriptstyle\frac{n+3}{2}}}{{\longrightarrow}}v_{2(\frac{n+1}{2})}\stackrel{{\scriptstyle\frac{n+1}{2}}}{{\longrightarrow}}v_{1(n)}$,
we assume $f(v_{1(n)})=0$. Also, $d(v_{3(1)},v_{1}(n))=n+1$ in $G_{m,n}$.
Thus, $f(v_{3(1)})\geq 2$ and since
$d(v_{3(1)},v_{2{\frac{n+1}{2}}})\geq\frac{n+3}{2}$, then,
$f(v_{2(\frac{n+1}{2})})\geq 2+n+2-(\frac{n+3}{2})\geq\frac{n+5}{2}$.

Next we consider the paths in $P^{\prime}_{2}(t)$.

Case 2. Every path in $P^{\prime}_{2}(t)$ are geometrically similar and are of
the form
$P^{\prime}_{2}(4)=v_{a(1)}\stackrel{{\scriptstyle\frac{n+3}{2}}}{{\longrightarrow}}v_{b(\frac{n+1}{2})}\stackrel{{\scriptstyle\frac{n+3}{2}}}{{\longrightarrow}}v_{n(n)}$,
such that $d(v_{a(1)},v_{c(n)})=n+1$ and
$d(v_{c(n)},v_{b}(\frac{n+1}{2}))=\frac{n+3}{2}$, in $G_{m,n}$ and for all
$a\neq b\neq c\neq m$, without loss of generality. Thus, suppose that
$f(v_{a(1)})=0$, then $f(v_{c}(n))\geq 1$ and
$f(v_{b(\frac{n+1}{2})})\geq\frac{n+3}{2}$.

∎

105025Figure 1. Illustration of Case 1(a) and (b) in a $G_{5,5}$ Stacked-book
Graph 001541Figure 1. Illustration of Case 1(c) and Case 2 in a $G_{5,5}$
Stacked-book Graph

######  Remark 3.1.

In (a) and (c) of Case 1, if the respective center vertices $v_{1(1)}$ and
$v_{1(n)}$ of stars $S_{(1)}$ and $S_{(n)}$ are labeled
$f(v_{1(1)})=f(v_{1(n)})=0$, the radio labels on the mid vertices of their
paths would be at least $\frac{n+7}{2}$.

######  Remark 3.2.

For the $m$ paths in $\left\\{P^{\prime}{t}\right\\}^{m}_{t=1}$, the sum of
all the radio labels on the center vertices ($span(f)$ of $f$ on
$P^{\prime}(t)$ is
$3(\frac{n+5}{2})+(m-3)(\frac{n+3}{2})=\frac{1}{2}(mn+3m+6)$.

Next, we obtained a lower bound for $\left\\{P(t)\right\\}^{m}_{t=1}$.

######  Remark 3.3.

From Remark 3.2, we notice that for optimum labeling of the three vertices on
each of the paths in $\left\\{P(t)\right\\}^{m}_{t=1}$, the end vertex, which
closest to the mid vertex is most suitable to be labeled first. These are
$v_{1(1)}\in P^{\prime}_{1}(1),v_{1}(n)\in P^{\prime}_{1}(3)$ and any end
vertex in the remaining paths. We refer to each of these ends vertices as
initial label vertex.

######  Lemma 3.2.

Let $G(*)$ be a subgraph of $G_{m,n}$, induced by all the end point vertices
and the midpoint vertices of $\left\\{P^{\prime}_{1}(t)\right\\}^{m}_{t=1}$
i.e $S_{m(1)},S_{m(\frac{n+1}{2})},S_{m(n)}$. Then
$rn(G(*))\geq\frac{1}{2}(2mn+4m-n+5)$ in $G_{m,n}$.

###### Proof.

Let $v_{1}$ and $v_{2}$ be center vertices on $S_{m(1)}$ and $S_{m(n)}$
respectively. There exist vertices $u_{\alpha},u_{\beta}\in
S_{m(\frac{n+1}{2})}$, $\alpha\neq\beta$, $u_{\alpha},u_{\beta}$ not center
vertices of $S_{m(\frac{n+1}{2})}$ such that
$d(v_{1},u_{\alpha})=d(v_{2},u_{\beta})=\frac{n+1}{2}$. Also, there exists a
subset $A=\left\\{\omega_{r}\right\\}$ in $S_{m(1)}$, (or $S_{m(n)}$) such
that $|A|=m-3$, and $B=\left\\{x_{s}\right\\}$ in $S_{m(\frac{n+1}{2})}$,
$|B|=m-1$, such that for $r\neq s$, $d(\omega_{r},x_{s})=\frac{n+3}{2}$. Now,
the sum of $span(f)$ of $f$ for all the pair ($\omega_{r},x_{s}$) will be
$(m-1)(\frac{n+1}{2})=\frac{1}{2}(mn+m-n-1)$ and thus,

$\displaystyle rn(G(*))$ $\displaystyle\geq$
$\displaystyle\frac{1}{2}(mn+m-n-1)+\frac{1}{2}mn+3m+6]$ $\displaystyle\geq$
$\displaystyle\frac{1}{2}(2mn+4m-n+5).$

∎

We extend the result in Lemma 3.2 in other to obtain a lower bound for the
radio number of stacked book graph $G_{m,n}$, with off $n\geq 5$

######  Definition 3.1.

Let $G_{m,n}$ be a stacked-book graph with odd $n$, $n\geq 5$, and $m\geq 4$.
Also, let $G(*)$ as defined earlier. We define subgraph $(G(**))$ of $G_{m,n}$
as $G(**)=G_{m,n}\backslash G(*)$.

######  Remark 3.4.

We can see that $G(**)$ is a subgraph of $G_{m,n}$, induced by
$\left\\{S_{m(i)}\right\\}^{n-1}_{i=2}$, $i\neq\frac{n+1}{2}$.

######  Definition 3.2.

Let $G^{\prime\prime}(t)\subseteq G(**)$ be a subgraph of $G_{m,n}$, such that
$G^{\prime\prime}(t)$ is induced by $S_{m(t)}$ and $S_{m(t+\frac{n-1}{2})}$.

######  Remark 3.5.

It should be noted that $G(**)\subset G_{m,n}$ contains exactly
$\frac{n-3}{2}$ $G^{\prime\prime}(t)$ subgraphs.

######  Remark 3.6.

Let $G^{\prime\prime}(t)$ induced by $S_{m(t)}$ and $S_{m(t+\frac{n-1}{2})}$
and let $V(S_{m(t)})=\\{u_{1},u_{2},\cdots,u_{m}\\}$ and
$V(S_{m(t+\frac{n-1}{2})})$ $=\left\\{v_{1},v_{2},\cdots,v_{m}\right\\}$ be
the vertex sets of $S_{m(t)}$ and $S_{m(t+\frac{n-1}{2})}$ where $u_{1}$ and
$v_{1}$ are the respective center vertices. It can be seen that,
$d(u_{i},v_{j})\in\left\\{\frac{n+1}{2},\frac{n+3}{2}\right\\}$, where $i\neq
j$.

######  Remark 3.7.

For $i\neq j$, $d(u_{1},v_{j})=d(u_{j},v_{1})=\frac{n+1}{2}$ and for $i\neq
j$, $i,j\neq 1$, $d(u_{i},v_{j})=\frac{n+3}{2}$.

Now we obtain a lower bound value for the radio number labeling of
$G^{\prime\prime}(t)$ in $G_{m,n}$.

######  Lemma 3.3.

Let $G^{\prime\prime}(t)\subset G_{m,n}$, with $m\geq 4$ and $n\geq 5$, $n$
odd, be a subgraph of $G_{m,n}$. Then $rn(G^{\prime\prime}(t))\geq
mn+m-\frac{1}{2}(n-3)$.

###### Proof.

Let $u_{1}$ and $v_{1}$ be center vertices of $S_{m(t)}$ and
$S_{m(t+\frac{n-1}{2})}$. By Remark 3.7 above,
$d(u_{1},v_{i})=d(u_{i},v_{1})=\frac{n+1}{2}$, is the shortest distance
between the center vertex of a star in $G^{\prime\prime}(t)$ and a non-center
vertex in the other star in $G^{\prime\prime}(t)$. It is optimal, therefore to
label the center vertices as $f_{min}$ and $f_{max}$. Now, without loss of
generality, set $f_{min}=f(v_{1})=0$. Since $d(v_{1},u_{i})=\frac{n+1}{2}$,
$i\in\left\\{2,3,\cdots,m\right\\}$. Therefore $f(u_{i})\geq
f(v_{1})+diam(G_{m,n})+1-d(u_{i},v_{1})$. Let $i=2$. Thus,

$\displaystyle f(u_{2})$ $\displaystyle\geq$ $\displaystyle
0+n+2-\frac{n+1}{2}$ $\displaystyle\geq$ $\displaystyle\frac{n+3}{2}.$

Now $d(u_{2},v_{3})=\frac{n+3}{2}$ and therefore,

$\displaystyle f(v_{3})$ $\displaystyle\geq$
$\displaystyle\frac{n+3}{2}+n+2-\frac{n+3}{2}$ $\displaystyle\geq$
$\displaystyle\frac{n+3}{2}+\frac{n+1}{2}.$

Also, for $d(v_{3},u_{4})=\frac{n+3}{2}$,
$f(v_{4})\geq\frac{n+3}{2}+2(\frac{n+1}{2})$. By continuing the iteration, we
have $f(v_{m})\geq\frac{n+3}{2}+2m-3(\frac{n+1}{2})$. Lastly,
$f_{max}=f(u_{1})\geq 2(\frac{n+3}{2})+(2m-3)(\frac{n+1}{2})$
$=mn+m-\frac{1}{2}(n-3)$. ∎

Next we extend the last result to obtain a lower bound for $G(**)$.

######  Lemma 3.4.

For $G(**)\subset G_{m,n}$, $rn(G(**))\geq\frac{1}{2}(mn^{2}-2mn-3m+2n-12)$.

###### Proof.

From 3.3, the $span(f)$ of $f$ on $G^{\prime\prime}(t)=mn+m-\frac{1}{2}(n-3)$.
For $G^{\prime\prime}(t)$, $f_{max}=mn+m-\frac{1}{2}(n-3)$. Let $t=2$ and let
$u_{1}=v_{m(2)}\in S_{m(2)}$ and $v^{\prime}_{1}=v_{m(2+\frac{n+1}{2})}\in
S_{m(2+\frac{n+1}{2})}$, be center vertices of $S_{m(2)}$ and
$S_{m(2+\frac{n+1}{2})}$. Now, $d(u_{i},v^{\prime}_{1})=\frac{n+1}{2}$. Thus,
$f(v^{\prime}_{1})\geq f(u_{1})+n+2-\frac{n+1}{2}=f(u_{1})+\frac{n+3}{2}$.
This implies that for $G^{\prime\prime}(3)$, induced by $S_{m(3)}$ and
$S_{m(2+\frac{n+1}{2})}$, $f_{min}=f(u_{1})+\frac{n+3}{2}$, and
$f_{max}=f(v^{\prime\prime}_{1})$, where $v^{\prime\prime}$ is the center
vertex of $S_{m(3)}$. From the precedure in Lemma 3.3, there are
$\frac{n-3}{2}$ $G^{\prime\prime}(t)$ subgraphs in $G_{m,n}$. Therefore,
$f_{max}$ of $G(**)$ is $f(v^{(k)}_{1})\in S_{(m(\frac{n-1}{2}))}$, where
$f(v_{1}^{(k)})$ is the center vertex of $S_{m(\frac{n-1}{2})}$. Following the
iteration,

$\displaystyle f(v^{(k)}_{1})$ $\displaystyle\geq$
$\displaystyle\frac{n-3}{2}[mn+m-\frac{1}{2}(n-3)]+\frac{n-5}{2}\left(\frac{n+3}{2}\right)$
$\displaystyle\geq$ $\displaystyle\frac{1}{2}(mn^{2}-2mn-3m+2n-12).$

∎

Now we establish a lower bound for the radio number of $G_{m,n}$.

######  Lemma 3.5.

Let $G_{m,n}$ be a stacked-book graph with $m\geq 4$ and $n\geq 5$. Then,
$rn(G_{m,n})\geq\frac{mn^{2}+m+2n-4}{2}$.

###### Proof.

From Lemmas 3.3 and 3.4, $rn(G(*))\geq m(n+2)-\frac{1}{2}(n-5)$ and
$rn(G(**))\geq\frac{1}{2}(mn^{2}-2mn-3n+2n-12)$. Now, since $G_{m,n}=G(*)\cup
G(**)$, suppose that $u_{1}$ is the center vertex of $S_{m(\frac{n-1}{2})}$
and $v_{1}\in S_{m(n)}$ is the center vertex of $S_{m(n)}$. Clearly
$d(u_{1},v_{i})=\frac{n+1}{2}$. Now, $f(u_{1})=f_{max}$ of $G(**)$ and
$f(u_{1})\geq\frac{1}{2}(mn^{2}-2mn-3m+2n-12)$. Therefore,

$\displaystyle f(v_{1})$ $\displaystyle\geq$ $\displaystyle
f(u_{i})+n+2-\frac{(n+1)}{2}$ $\displaystyle\geq$
$\displaystyle\frac{1}{2}(mn^{2}-2mn-3m+2n-12)+n+2-\frac{(n+1)}{2}$
$\displaystyle\geq$ $\displaystyle\frac{1}{2}(mn^{2}-2mn-3m+n-13)+n+2.$

For $G(*)$, set $f(v_{1})=f_{min}$. Thus, $rn(G_{m,n})\geq f(v_{1})+rn(G(*))$
and hence,

$\displaystyle rn(G_{m,n})$ $\displaystyle\geq$
$\displaystyle\frac{1}{2}(mn^{2}-2mn-3m+n-13)+n+2+m(n+2)-\frac{1}{2}(n-5)$
$\displaystyle\geq$ $\displaystyle\frac{mn^{2}+m+2n-4}{2}.$

∎

Next, we investigate the upper bound of a stacked-book graph. The technique
involves manual radio labeling of subgraphs $G(*)$ and $G(**)$ and merging the
results.

######  Lemma 3.6.

Let $G(**)\subset G_{m,n}$, with $n$-odd. Then,
$rn(G(**))\leq\frac{1}{2}(mn^{2}-2mn+2n-3m-12)$.

###### Proof.

From earlier definition, if $n$ is odd, then, $G_{m,n}=G(*)\cup G(**)$, where
$G(**)$ contains $\frac{n-3}{2}$ $G^{\prime\prime}(t)$ graphs. Let
$G^{\prime\prime}(\frac{n-1}{2})$ be induced by $S_{m(\frac{n-1}{2})}$ and
$S_{m(n-1)}$, $n$-odd. Let
$V(S_{m(\frac{n+1}{2})})=\left\\{v_{\frac{n-1}{1}(i)}\right\\}^{m}_{i=1}$,
$V(S_{m(n-1)})=\left\\{v_{n-1}\right\\}^{m}_{i=1}$, where
$v_{\frac{n-1}{2}(1)}$, $v_{n-1(1)}$ are center vertices and
$d(v_{\frac{n-1}{2}(j)},v_{n-1(j)})=\frac{n-1}{2}$, for all $1\leq j\leq m$,
$d(v_{\frac{n-1}{2}(1)}),v_{n-1(j)}=d(v_{n-1(1)},v_{\frac{n-1}{2}(j)})=\frac{n+1}{2}$
and $d(v_{\frac{n-1}{2}(j)},v_{n-1(k)})=\frac{n+3}{2}$. Now, let
$f(v_{\frac{n-1}{2}(1)})=0$. Since
$d(v_{\frac{n-1}{2}(1)},v_{n-1(2)})=\frac{n+1}{2}$, then set
$f(v_{n-1(k)})=\frac{n+3}{2}$. Let $f(v_{\frac{n-1}{2}(1)})=0$. Since
$d(v_{\frac{n-1}{2}(1),v_{n-1(2)}})=\frac{n+1}{2}$, then set
$f(v_{n-1(2)})=\frac{n+3}{2}$,
$d(v_{n-1(2)},v_{\frac{n-1}{2}(3)})=\frac{n+3}{2}$ and thus,
$f(v_{n-1}(4))=\frac{n+3}{2}+2\frac{n+1}{2}$. Thus, by continuously
alternating the process, it gets to the case where
$d(v_{\frac{n-1}{2}(m)},d(v_{n-1(m-1)}))=\frac{n+3}{2}$. Thus,
$f(\frac{n-1}{2}(m))=\frac{n+3}{2}+m-2(\frac{n+1}{2})$, and since
$d(v_{\frac{n-1}{2}(m)},v_{n-1(3)})=\frac{n+3}{2}$,
$f(v_{n-1(3)})=\frac{n+3}{2}+(m-1)(\frac{n+1}{2})$,
$f(v_{\frac{n-1}{2}(2)})=\frac{n+3}{2}+m(\frac{n+1}{2})$. Depending on the
size of $m$, the labeling continues until
$f(v_{\frac{n-1}{2}})=\frac{n+3}{2}+2m-3\frac{(n+3)}{2}+2(2m-3)(\frac{n+1}{2})$
is attained and finally, $d(v_{\frac{n-1}{2}(m-1)},v_{n-1(1)})=\frac{n+1}{2}$
and thus, $f(v_{n-1(1)})=\frac{2(n+3)}{2}+2m-3+\frac{n+1}{2}$. (By following
the same argument, it is easy to obtain similar result for $m$-even.) Now,
$d(v_{n-1(1)},v_{\frac{n-3}{2}(1)})=\frac{n+1}{2}$, where
$v_{\frac{n-3}{2}(1)}$ is the center vertex of
$G^{\prime\prime}_{m(\frac{n-3}{2})}$. Therefore,
$f_{min}(G^{\prime\prime}(\frac{n-3}{2}))=f(v_{\frac{n-3}{2}(1)})=f(v_{n-1(1)})+n+2-\frac{n+2}{2}=$$f(v_{n-1(1)})+\frac{n+3}{2}=\frac{3(n+3)}{2}+2m-3(\frac{n+1}{2})$,
and
$f_{max}(G^{\prime\prime}(\frac{n-3}{2})=f(v_{n-2(1)})=f(v_{\frac{n-3}{2}(1)})+\frac{2(n+3)}{2}+\frac{(2m-3)(n+1)}{2}=$$\frac{5(n+3)}{2}+2(2m-3)\frac{(n+1)}{2}$,
which is $f_{max}(G^{\prime\prime}(\frac{n-3}{2}))$. Now, the process is
extended to $G^{\prime\prime}(2)$, for which
$f(\frac{n+3}{2})=\frac{(n-5)(n+3)}{4}+\frac{(n-3)(n+3)}{2}+\frac{(n-2)(2m-3)(n+1)}{4}$=$\frac{1}{2}(mn^{2}-2mn+2n-3m-12)$.
∎

######  Remark 3.8.

It can be observed that for the optimal radio labeling of $G(*)$,
$f_{max}(G(*))$ is $f(v_{\frac{n+1}{2}(1)})$, the label on the center vertex
of $S_{m(\frac{n+1}{2})}$. Since for $v_{\alpha},v_{\beta}$ in $S_{m(1)}$ and
$S_{m(n)}$ respectively, $\alpha,\beta\neq 1$,
$d(v_{\frac{n+1}{2}(1)},v_{\alpha})=d(v_{\frac{n+1}{2}(1)},v_{\beta})=\frac{n+1}{2}$,
which is less than $\frac{n+3}{2}$, the value of
$d(v_{\frac{n+1}{2}(k)},v_{\alpha})$, where $k\neq\alpha$, $k,\alpha\neq 1$,
and $v_{\alpha}$ either belongs to $S_{m(1)}$ or $S_{m(n)}$. Thus, we manually
label $G(*)$, such that $v_{\frac{n+1}{2}(1)}$ gets the last label and thus,
$f(v_{\frac{n+1}{2}(1)})=f_{max}(G(*))$.

Next, we consider some necessary conditions for establishing the upper bound
of $G(*)$.

######  Lemma 3.7.

Let $G(*)\subset G_{m,n}$ be a subset of $G_{m,n}$, induced by
$S_{m(1)},S_{m(\frac{n+1}{2})}$ and $S_{m(n)}$. If $v_{1(1)}$ (or $v_{n(1)}$)
and $v_{\frac{n+2}{2}(1)}$ are the center vertices of $S_{m(1)}$ (or
$S_{m(n)}$) and $S_{m(\frac{n+1}{2})}$ respectively, and $f_{min}(G(*))\neq
f(v_{1(1)})$ (or $f(v_{n(1)})$), and $f_{max}(G(*))\neq f(v_{\frac{n+1}{2}})$
(or vice versa), then, $|f_{min}(G(*))-f_{max}(G(*))|\neq rn(G(*))$.

###### Proof.

Without loss of generality, select $v_{1(1)}$ over $v_{n(1)}$. Suppose that
$f(v_{1,1})$ and $f(v_{\frac{n+1}{2}(1)})$ are not $f_{min}(G(*))$ and
$f_{max}(G(*))$ respectively. Let $v_{\alpha}\in V(S_{m(1)})$, $v_{\beta}\in
V(S_{m(\frac{n+1}{2})})$, and $v_{\gamma}\in V(S_{m(n)})$ be non-center
vertices, and let the set of the following vertices,
$\\{v_{\alpha},v_{\beta},v_{\gamma},v_{1(1)},v_{\frac{n+1}{2}(1)}\\}$ be $X$,
and let $H=V(G(*))\backslash X$ be the subgraph of $G(*)$ induced by
$V(G(*))-X$, and such that the radio number of $H$ is positive integer $p$.
Without loss of generality, let there be some $v_{k}\in V(H)$, where
$v_{k}=v_{n(i)}\in S_{m(n)},\gamma\neq i$ and
$d(v_{k},v_{\beta})=\frac{n+3}{2}$, there exist a radio numbering sequence
$v_{k}\rightarrow v_{\beta},\rightarrow v_{1(1)}\rightarrow
v_{\gamma}\rightarrow v_{\frac{n+1}{2}(1)}\rightarrow v_{\alpha}$. Suppose
that $f(v_{k})$ is the $f_{m}ax(H)$, that is, $f(v_{k})=p$. Since
$d(v_{k},v_{\beta})=\frac{n+3}{2}$, then $f(v_{\beta})=p+\frac{n+1}{2}$ and
likewise, it is observed that the radio labeling sequence yields
$f_{max}(G(*))=p+2n+7$. Now, suppose on the contrary, that $f(v_{1(1)})$ and
$f(v_{\frac{n+1}{2}(1)})$ are $f_{min}(G(*))$ and $f_{max}(G(*))$
respectively. Let $v_{k(0)}$ be the vertex in $H$, which holds the least radio
label. Obviously $v_{k(0)}\neq v_{k}$ and since $|V(G(*))|-|V(H)|\equiv 3\mod
1$, then $v_{k(0)}$ is a is also a vertex on the same star as $v_{k}$, this
time, $S_{m(n)}$. Thus,if $v_{k(0)}$ is also not a center vertex, then,
$d(v_{1(1)},v_{k(0)})=n$. Let $f(v_{1(1)})=0$. Now, we have the radio labeling
sequence : $v_{1(1)}\rightarrow(v_{k(0)}\rightarrow\cdots\rightarrow
v_{k})\rightarrow v_{\beta}\rightarrow v_{\alpha}\rightarrow
v_{\gamma}\rightarrow v_{\frac{n+1}{2}(1)}$. Since $d(v_{k(0)},v_{1(1)})=n$,
then, $f(v_{k(0)})=2$ and since $|f_{min}(H)-f_{max}(H)|=p$, then
$f(v_{k})=2+p$. Labeling the sequence, afterwards, we have
$f_{max}(G(*))=f(v_{\frac{n+1}{2}(1)})=p+\frac{3n+11}{2}$, which is less than
$p+2n+7$. ∎

######  Remark 3.9.

It is noted that $v_{1(1)}$ (or $v_{n(1)(1)}$) and $v_{\frac{n+1}{2}}$ can be
$f_{min}(G(*))$ and $f_{max}G(*)$ interchangeably. However, they both will
have to be used for these roles. It is trivial to show that optimal radio
labeling will not be attained if just one of them is used.

Next we obtain an upper bound for $G(*)$, based on Lemma 3.7.

######  Lemma 3.8.

For $G(*)\subset G_{m,n}$, $m\geq 5$, $rn(G(*))\leq\frac{1}{2}(2mn+4m-n+7)$.

###### Proof.

From Lemma 3.7 For $v_{1(1)}\in S_{m(1)}$, let $f(v_{1(1)})=0$. There exist
$m-1$ vertices of $S_{m(n)}$, such that for each $v_{n(i)}\in V(S_{m(n)})$,
$i\neq 1$, $d(v_{1(1)},v_{n(i)})=n$. Thus, without loss of generality, let the
first vertex be $v_{n(2)}$. Then, $f(v_{n(2)})=2$. Likewise, there exists
$m-1$, non-center vertex on $S_{m(\frac{n+1}{2})}$, and for each
$v_{\frac{n+1}{2}(j)}$, $j\neq 1$,
$d(v_{n(2)},v_{\frac{n+1}{2}(j)})=\frac{n+3}{2}$, where $j\neq 2$. So, now,
let $j=3$, then,
$f(v_{\frac{n+1}{2}(3)})=2+n+2-\frac{n+3}{2}=2+\frac{n+1}{2}$. In similar way,
$f(v_{1(4)})=2+\frac{n+1}{2}+\frac{n+1}{2}$. Now, we label $v_{n(1)}$, which
is at distance $n$ from $v_{1(4)}$ as
$f(v_{n(1)})=4+\frac{n+1}{2}+\frac{n+1}{2}$. Now, two of the center vertices
are labeled. For, say, $v_{\frac{n+1}{2}(5)}$,
$f(v_{\frac{n+1}{2}(5)})=4+\frac{n+1}{2}+\frac{n+1}{2}+\frac{n+3}{2}$. It can
be seen that for each of $S_{m(1)}$, $S_{m(\frac{n+1}{2})}$ and $S_{m(n)}$,
there are $m-2$ vertices left to be labeled. This is now done by adding
$\frac{(n+1)}{2}$ and $1$ in alternating manner to the cumulative label
values, such that we have $f(v_{1(6)})=4+3(\frac{n+1}{2})+\frac{n+3}{2}$ and
$f(v_{n(7)})=5+3(\frac{n+1}{2})+\frac{n+3}{2}$. Thus by continuing the
iteration until it gets to
$f(v_{\frac{n+1}{2}(1)})=(m+2)+(2m-3)(\frac{n+1}{2})+2(\frac{n+3}{2})=\frac{1}{2}(2mn+4m-n+7)$.
∎

Next, we merged the last results to obtain an upper bound for the radio number
of a stacked-book graph $G_{m,n}$, where $m\geq 5$.

######  Theorem 3.1.

Let $m\geq 5$. Then, $rn(G_{m,n})\leq\frac{1}{2}(mn^{2}+2n+m-2)$.

###### Proof.

Recall that $G=G(*)\cup G(**)$. From Lemma 3.6, where $G(**)$ is labeled, we
see that for $G(**)$, $f_{max}(G(**))=f(v_{\frac{n+3}{2}(1)})$. For $G(*)\in
G_{m,n}$, we see in Lemma 3.8 that $f(v_{1(1)})=f_{min}$. Clearly,
$d(v_{\frac{n+3}{2}(1)},v_{1(1)})=\frac{n+1}{2}$. Thus, for $v_{1(1)}\in
G_{m,n}$,
$f(v_{1(1)})=f(v_{\frac{n+3}{2}(1)})+\frac{n+3}{2}=\frac{1}{2}(mn^{2}-2mn+2n-3m-12)+\frac{n+3}{2}=\frac{1}{2}(mn^{2}-2mn+3n-3m-9)$.
Thus by Lemma 3.8,
$f_{max}(G_{m,n})=f(v_{1(1)})+f_{max}(G(**))=\frac{1}{2}(mn^{2}+2n+m-2)$.

∎

######  Remark 3.10.

We observe that the result in 3.1 that the there is just a difference of of
$1$ between this upper bound and the lower bound established earlier in the
work. It is believed that the lower bound can be improved to coincide with the
upper bound.

The next figure show the radio labeling of $G_{5,5}$, where it is demonstrated
that $rn(G_{5,5})\leq 69$.

105025Figure 1. Illustration of Case 1(a) and (b) in a $G_{5,5}$ Stacked-book
Graph 001541Figure 1. Illustration of Case 1(c) and Case 2 in a $G_{5,5}$
Stacked-book Graph 64135422354119611051330692943577471665502538458Figure 2. A
$G_{5,5}$ Stacked-book Graph

##  4\. Conclusion

This work has greatly improved results obtained in [1] and extended the
outcomes of [1] to the odd-path factor of the stacked-book graph class. It is
safe now to say that this work and [2] have provided a tight bounds for the
radio number of the general stacked-book graph. Further work to obtain the
exact value of the radio number for stacked-book graph should be considered.

## References

  * [1] D.O.A. Ajayi and T.C. Adefokun On Bounds of Radio Number of Certain Product Graphs, Jour Nigeria Math Soc. 37(2) (2018) 71-78.
  * [2] T.C. Adefokun and D.O.A. Ajayi On Radio Number of Stacked-Book Graph, arXiv:1901.00355. Jan 2019.
  * [3] D. Bantva, S Vaidya and S. Zhou Radio Numbers of trees, Electron. Notes in Discrete Math. 48 (2015) 135-141.
  * [4] D. Bantva Radio Numbers of Middle graph of paths, Electron. Notes in Discrete Math. 66 (2017) 93-100.
  * [5] G. Chartrand, D. Erwin, F Harary and P. Zhang, Radio Labelings of Graphs, Bull. Inst. Combin. Appl. 33 (2001) 77-85.
  * [6] G. chartrand, D. Erwin and P. Zhang, A Graph Labeling Problem Suggested by FM Channel Restrictions, Bull. Inst. Combin. Appl. 43 (2005) 43-57.
  * [7] W. K. Hale, Frequency Assignment Theory and Applications, Proc. IEEE, 68 (1980) 1497 - 1514
  * [8] T-S Jiang, The Radio Number of Grid Graphs, arXiv:1401.658v1. 2014.
  * [9] D.D.-F. Liu and M. Xie Radio Number for Square Paths, Ars Combin. 90 (2009) 307-319.
  * [10] D.D.-F. Liu and M. Xie Radio Number for Square Cycles, Congr. Numer. 169 (2004) 105-125.
  * [11] D. Liu and X. Zhu, Multilevel Distance Labelings for Paths and Cycles, SIAM J. Discrete Math. 19 (2005) 610-621.
  * [12] A. Naseem, K. Shabbir and H. Shaker The radio Number of Edge-Joint Graphs, ARS Comb 139 (2018) 337-351.
  * [13] L. Saha and P. Panigrahi, On the Radio Numbers of Toroidal Grid, Aust. Jour. Combin. 55 (2013) 273-288.