# Transient glitch mitigation in Advanced LIGO data with glitschen

J.D. Merritt  Institute for Fundamental Science, Department of Physics,
University of Oregon, Eugene, OR 97403, USA  Ben Farr  Institute for
Fundamental Science, Department of Physics, University of Oregon, Eugene, OR
97403, USA  Rachel Hur  Institute for Fundamental Science, Department of
Physics, University of Oregon, Eugene, OR 97403, USA  Bruce Edelman  Institute
for Fundamental Science, Department of Physics, University of Oregon, Eugene,
OR 97403, USA  Zoheyr Doctor  Institute for Fundamental Science, Department of
Physics, University of Oregon, Eugene, OR 97403, USA  Center for
Interdisciplinary Exploration and Research in Astrophysics (CIERA), Department
of Physics and Astronomy, Northwestern University, Evanston, IL 60201, USA

###### Abstract

“Glitches” – transient noise artifacts in the data collected by gravitational
wave interferometers like LIGO and Virgo – are an ever-present obstacle for
the search and characterization of gravitational wave signals. With some
having morphology similar to high mass, high mass-ratio, and extreme-spin
binary black hole events, they limit sensitivity to such sources. They can
also act as a contaminant for all sources, requiring targeted mitigation
before astrophysical inferences can be made. We propose a data driven,
parametric model for frequently encountered glitch types using probabilistic
principal component analysis. As a noise analog of parameterized gravitational
wave signal models, it can be easily incorporated into existing search and
detector characterization techniques. We have implemented our approach with
the open source glitschen package. Using LIGO’s currently most problematic
glitch types, the ‘blip’ and ‘tomte’, we demonstrate that parametric models of
modest dimension can be constructed and used for effective mitigation in both
frequentist and Bayesian analyses.

##  I Introduction

Detecting gravitational waves (GWs) is an immense challenge, requiring the
construction and monitoring of the most sensitive interferometers ever built
Abbott  _et al._ (2016). The strain signal from a loud binary black hole (BBH)
inspiral typically perturbs the detectors’ arm lengths to one part in
$10^{21}$. Managing the noise background is an overwhelming portion of that
challenge: an earthquake in another hemisphere, a passing vehicle, a cosmic
ray hit, a thirsty raven Schofield  _et al._ (2017), or scattered light from a
blinking LED can all bring the data well short of the level necessary for
detection et. al. (2021). In spite of a myriad of obstacles, the LIGO-Virgo
Collaboration (LVC) has detected 58 confident compact binary coalescence (CBC)
events as of the end of the first half of the third observing run (O3a) et.al.
(2021); Collaboration  _et al._ (2021). Into O4 these observatories may see
confident CBC signals upwards of once-a-day Abbott  _et al._ (2020a). Upgrades
to the detectors will improve sensitivity and the addition of KAGRA to the
LIGO-Virgo-KAGRA network (LVK) will improve astrophysical parameter estimation
(PE) and sky localization. The LVK still expects serious challenges overcoming
the noise background, carefully examining more near-threshold triggers, and
keeping all the pipelines going with the rapid acquisition of a larger volume
of data.

In Advanced LIGO data there are some transient noise sources for which no
physical cause has been identified Cabero  _et al._ (2019). These noise
sources have the potential to impact astrophysical searches significantly
Müller and Anabel (2018). In particular, high-mass and high-mass-ratio BBH
searches are affected, in which the astrophysical hypothesis predicts a short
duration signal sweeping up into the sensitive frequency bands of the
detectors near merger. “Blip” glitches and the lower frequency, longer
duration “tomte” glitches are glitch types that are capable of masquerading as
these high mass CBCs. These occur on the order of 1/hour Cabero  _et al._
(2019) but sometimes much more frequently, so the probability of coincidence
in multiple detectors is non-negligible. Coincident or nearly coincident
glitches can confuse search pipelines that strongly rely on coherence between
detectors to determine if a trigger is astrophysical. Worse, the effect on the
ranking statistic, established by time-sliding data streams from multiple
detectors to establish false alarm rates (FARs) Abbott  _et al._ (2020b) is
affected significantly by the presence of these glitches in the background,
effectively down-ranking many events. There is evidence that these glitches
grow louder and more prevalent with increasing sensitivity Soni  _et al._
(2021). Blips and tomtes all but eliminate our ability to evaluate high-mass,
extreme-mass-ratio, and extreme-spin single-detector triggers Davis  _et al._
(2020) from a confident astrophysical perspective because the data is
contaminated with $\mathcal{O}(10^{4})$ loud glitches.

GravitySpy Zevin  _et al._ (2017) is a pipeline developed to classify glitch
types. It leverages citizen science with an image recognition neural network,
specifically trained on q-transforms, which display power in time-frequency
pixels Chatterji  _et al._ (2004). Thanks to these efforts, there are now over
$10^{6}$ glitches classified, each with an associated confidence metric and
SNR Zevin  _et al._ (2017). GravitySpy itself can be used to effectively
distinguish different types of glitches from each other, but it can’t be used
to distinguish signal from glitch, or to subtract glitches from data. For this
we seek a parametric, _generative_ model for common glitch types. Barring the
discovery and mitigation of possible environmental, electronic, or
instrumental causes Braginsky  _et al._ (2006); Yamamoto  _et al._ (2008);
Helmling-Cornell  for these problematic classes of glitch, distinction between
glitch-like astrophysical events and BBH signals that resemble common and
problematic glitch types may be our only tractable method for opening up the
high-mass and high-mass-ratio region of CBC search parameter space.

With the glitschen package, we propose a data-driven, easy to use, and
computationally cheap framework for the modeling of short duration transient
glitches. Our model uses an analytical maximum likelihood estimation (MLE)
approach to fit a probabilistic principal component analysis (PPCA) model to
all of the training data, operating under the hypothesis of a transient glitch
superimposed on Gaussian noise Tipping and Bishop (1999). While PCA’s have
previously been used in the context of glitch categorization Powell  _et al._
(2015, 2017), we focus on the construction of glitch-class-specific
parameterized models for glitch _mitigation_. Relative to other glitch
mitigation techniques Mukherjee  _et al._ (2010); Cornish and Littenberg
(2015); Torres-Forné  _et al._ (2020); Cornish  _et al._ (2021); Cornish
(2021), these targeted parameterized models have minimal flexibility and are
in many ways analogous to the parameterized CBC models used to search for and
characterize signals, making them straightforward to incorporate in existing
LVK analyses. In comparison to current glitch mitigation techniques such as
BayesWave (BW) Cornish and Littenberg (2015), our approach naturally allows
for informed priors, allowing us to leverage the extensive glitch population.
Our approach can be naturally used in existing analysis libraries such as
Bilby, whereas BW’s use of reverse-jump sampling means that only a point
estimate from BW can be used to remove a glitch during astrophysical parameter
inference. While powerful, our methods require large training sets for each
glitch type and will likely be unable to model glitches that are extensive in
time-frequency, such as scattered-light.

##  II Method

###  II.1 Modeling the Advanced LIGO Noise Background

The noise in the detector is a superposition of many noise sources, and is
modeled as a stochastic process, drawing randomly from a stationary background
spectrum at each frequency cre . The detector produces a time series, $n(t)$,
which we can represent as a vector, $\bm{n}$. Transforming to the frequency
domain we obtain $\bm{\tilde{n}}$, with $n_{i}$ indicating the noise in the
i-th frequency bin. Assuming Gaussianity the probability distribution becomes:

$p(\bm{\tilde{n}})=\frac{1}{det(2\pi\bm{C})^{1/2}}exp\bigg{[}-\frac{1}{2}\sum_{ij}(\tilde{n_{i}}-\mu)(\tilde{n_{j}}-\mu)C_{ij}^{-1}\bigg{]}$
(1)

where $\bm{C}_{ij}=\frac{1}{M-1}(n_{i}-\mu)(n_{j}-\mu)$ is the covariance
matrix of the observations and $\mu$ is the mean of the dataAbbott  _et al._
(2020b). Stationarity means that the noise spectrum is not changing over time,
so in the frequency domain the covariance matrix is diagonal:
$C_{ij}=\delta_{ij}S_{n}(f_{i})$, giving the power spectral density (PSD),
$S_{n}(f)$ which is equal to the square of the amplitude spectral density
(ASD). The noise is typically stationary on the timescales (minutes) relevant
for PSD computation, but on the hour timescale may need to be updated Abbott
_et al._ (2020b).

We “whiten” the data by dividing the frequency domain data by an estimate of
the ASD, resulting in noise with an equal (unitary) noise in all frequencies.
We train and test our model using whitened data.

This treatment is highly effective for ‘well-behaved’ noise sources which
remain stationary over the duration of ASD calculation, however the motivation
for building our model is to mitigate transient glitches, which can occur at
any time and pose the greatest challenge for searches that look for transient
astrophysical events.

Figure 1: Typical loud blip (above) and tomte (below) glitches from the test
set for Livingston in O3a, to demonstrate morphology. Q-scans indicate power
as color in time-frequency pixels, and the timeseries (below in blue) shows
additional morphology. Note that timescales and frequency ranges plotted vary.
Blips are sometimes shorter than 5ms, where tomtes can last over 100ms.

###  II.2 The Transient Glitch Background

The characteristics of the noise background are well covered in et. al.
(2021); Zevin  _et al._ (2017); Soni  _et al._ (2021); Abbott  _et al._
(2020b). The morphologies of a typical ‘blip’ and ‘tomte’ glitch are explored
in Figure 1. Blip glitches are short, at around 5-10ms, while Tomtes are
typically 100ms long. To properly mitigate these glitches we examine their
morphology as they appear to searches, after any whitening and postprocessing.
Physically, it is possible that the glitches are a very brief DC offset that
appears in the strain channel, the result of either a single physical
perturbation to some component of the detector or the result of a digital
error. We will have to consider the additional morphology of finite impulse
response whitening filters as being part of the glitch, since the searches
must also contend with these features.

While GravitySpy examines q-transforms Chatterji  _et al._ (2004) of glitches,
we train on the frequency series of glitches. There is a loss of phase
information and direction of amplitude in q-transforms, which record only
power for each time-frequency pixel. This may be important for future efforts
in distinguishing auxiliary witnesses for these glitches, since a preferential
directional perturbation to a part of the detector could show up as a bias in
amplitude (positive or negative) in the strain channel for a certain detector
and glitch type. We have yet to determine if this is a bias introduced in
GravitySpy’s curation of the highest confidence and loudest glitches, or if
this extends to the large number of lower confidence glitches as well, but we
see a vast majority of confident, loud L1 O3a tomtes with negative amplitudes.
Other detectors and glitch types exhibit a certain “glitch-signature” in
amplitude bias, sometimes across multiple observing runs.

###  II.3 The glitschen Model

In the glitschen parametric glitch mitigation model, we employ probabilistic
principal component analysis (PPCA). This is a simple and effective way for us
to decompose a frequency domain signal into a set of Gaussian distributed
latent variables. It is frequently used as a dimensionality reduction tool,
making problems in many areas of data science more tractable. There are many
ready-made principal component analysis (PCA) implementations available. We
found it most transparent and effective to write our own PPCA implementation,
closely following the original PPCA model Tipping and Bishop (1999). This
enabled us to find a fast and computationally cheap way to analytically
maximize our likelihood. PPCA differs from PCA in that it includes a Gaussian
noise term.

We employ an isotropic Gaussian noise model:

$\mathcal{N}(\bm{0},\sigma^{2}\bm{I})$ (2)

with a d-dimensional observation vector, $\bm{\tilde{d}}$:

$\bm{\tilde{d}}|\bm{Z_{train}}\sim\mathcal{N}(\bm{WZ_{train}}+\bm{\mu},\sigma^{2}\bm{I})$
(3)

We assume the marginal distribution
$\bm{Z_{train}}\sim\mathcal{N}(\bm{0},\bm{I})$ over q latent variables of the
training set, and $\bm{W}$ has size $d\times q$, containing q training
eigenvectors. We recover normal PCA in the limit of $\sigma\xrightarrow{}0$.
We can marginalize over the latent variables to obtain a distribution for
$\bm{\tilde{d}}$:

$\bm{\tilde{d}}\sim\mathcal{N}(\bm{\mu,C})$ (4)

where $\bm{C}=\bm{WW}^{T}+\sigma^{2}\bm{I}$ is the covariance model for the
observed data, with dimension $d\times d$. In our case this data is frequency-
series data. With $N$ training glitches, our log-likelihood for the entire
model and all our observed (training) data is then:

$\ln\mathcal{L}_{training}=-\frac{N}{2}\bigg{[}d\ln(2\pi)+\ln|\bm{C}|+tr(\bm{C}^{-1}\bm{S})\bigg{]}$
(5)

with the sample covariance matrix of the observations, $\bm{S}$:

$\bm{S}=\frac{1}{N}\sum_{n=1}^{N}(\bm{\tilde{d}}_{n}-\bm{\mu})(\bm{\tilde{d}}_{n}-\bm{\mu})^{T}$
(6)

This likelihood is often maximized iteratively, and many packaged
implementations of PPCA find $W$ in this way Dillon  _et al._ (2017). However
we find the global maximum of the likelihood using an analytical method
detailed in Tipping and Bishop (1999).

Later, we use this likelihood, with an Occam’s penalty accounting for the
effective degrees of freedom in the model, to find the optimal number of
components, q, to use. Performing an eigenvalue decomposition on $\bm{S}$, the
sample covariance matrix of the observations, we obtain the $d\times q$ matrix
$\bm{U}_{q}$ containing q principal eigenvectors (or “eigenglitches”) of
$\bm{S}$, and the $q\times q$ diagonal matrix $\bm{\Lambda}_{q}$ with
cooresponding eigenvalues. All eigenvalue decompositions and matrix inversions
are conveniently handled by an open-source computer algebra library with
numpyvan der Walt  _et al._ (2011). The likelihood is maximized when:

$\bm{W}=\bm{W}_{ML}=\bm{U}_{q}(\bm{\Lambda}_{q}-\sigma^{2}\bm{I})^{1/2}$ (7)

Going forward, we can consider $\bm{W}=\bm{W}_{ML}$ to always contain the
maximum likelihood (ML) eigenvectors. See an example time-domain
representation in Figure 2.

In order to obtain a projection of a new observation vector,
$\bm{\tilde{d}}_{obs}$, onto the latent variables we use Bayes rule to get
from $\bm{\tilde{d}}|\bm{Z_{train}}$ to

$\bm{Z_{train}}|\bm{\tilde{d}_{obs}}\sim\mathcal{N}(\bm{M}^{-1}\bm{W}^{T}(\bm{\tilde{d}_{obs}}-\bm{\mu}),\sigma^{2}\bm{M}^{-1})$
(8)

where $\bm{M}=\bm{W}^{T}\bm{W}+\sigma^{2}\bm{I}$, with dimensions $q\times q$.
This allows us to perform reconstructions of suspected glitches using a
trained model. We define

$\bm{Z_{rec}}\equiv\bm{M}^{-1}\bm{W}^{T}(\bm{\tilde{d}_{obs}}-\bm{\mu})$ (9)

as the set of $q$ latent optimal (i.e., maximum likelihood) reconstruction
weights up to an arbitrary rotation matrix.

Figure 2: L1 O3a tomte glitch model eigenvectors. Increasing weight from top
to bottom.

We can obtain a reconstruction with:

$\bm{\tilde{g}}_{rec}=\bm{WZ_{rec}}+\mu$ (10)

To evaluate the quality of our reconstruction given the data, we employ the
standard Gaussian noise likelihood, identical to that used by CBC searches and
PE, and specifically Bilby Ashton  _et al._ (2019). We define the standard
noise weighted inner product of any two frequency-series vectors, $\bm{a}$ and
$\bm{b}$:

$(\bm{\tilde{a}}|\bm{\tilde{b}})=2\int^{\infty}_{0}\frac{\tilde{a}(f)\tilde{b}^{*}(f)+\tilde{a}^{*}(f)\tilde{b}(f)}{S_{n}(f)}df$
(11)

$S_{n}=\sigma^{2}$ is the noise power spectral density (PSD), and $\sigma$ is
the amplitude spectral density (ASD)Abbott  _et al._ (2020b). In practice, the
noise term can be taken to be 1, because the model is trained on whitened
data. When we assume stationary, Gaussian noise that is uncorrelated between
detectors, our reconstruction log-likelihood becomes:

$\ln\mathcal{L}_{rec}=-\frac{1}{2}\sum_{k}\bigg{\\{}\frac{|\bm{\tilde{d}}_{obs,k}-\bm{\tilde{g}}(\theta)_{rec,k}|^{2}}{S_{k}}+\ln(2\pi
S_{k})\bigg{\\}}$ (12)

where k is the frequency bin index $\bm{\tilde{g}}(\theta)_{rec,k}$ is the
frequency domain reconstruction with PPCA parameters $\theta$. With this inner
product and likelihood we can compare our model’s reconstruction of an event,
after training on a certain glitch class, with the likelihood of the
astrophysical hypothesis. We can select $q$ based on an Occam’s penalty, or we
can try to replicate the number of effective free parameters in the CBC model
to give equal flexibility.

###  II.4 Implementation and Performance

####  II.4.1 Selection of Training Data

We curate glitches classified by GravitySpy Zevin  _et al._ (2017) with high
‘confidence’, where the score ranges from (0,1). Note that confidence is not a
normalized probability, but instead reflects the certainty of classification
by the convolutional neural network used. We utilize the newest, LVK-internal
version of the GravitySpy model, which has the benefit of training on data
from all of O3. Publicly available glitch and event data can be obtained from
the Gravitational Wave Open Science Center (GWOSC) Abbott  _et al._ (2021).
This analysis was completed using an older version of the calibrated data: the
HOFT_C00 strain data frame within the GDS-CALIB_STRAIN_CLEAN channel. Note
that some ($<$ 1%) of the glitches used in training are outside of “science
mode” times.

All glitches used first must clear our confidence cutoff(0.95-1, depending on
type, detector, and epoch), and are then sorted by SNR. Lower SNR glitches can
contaminate the model with more unrelated noise features. As such, we have
kept a high SNR threshold for inclusion in training(dependent on type,
detecter, and epoch), where we use the 1500-2000 loudest glitches. It is more
productive to limit the set to “golden” examples curated by GravitySpy, even
if the glitch or event in the run segment has low SNR, since we believe quiet
and loud glitches ( 5-50 SNR) exhibit similar morphology, based on our
exploration of the data.

####  II.4.2 Preprocessing and Training

To train our model, we whiten with an ASD calculated from between 16 and 128
seconds of data, depending on the glitch-type in question. Because we are
concerned with the low-frequency content of glitches (in the range of
astrophysical searches) all data is downsampled to 2048 Hz, and then for
certain glitchtypes we further bandpass training data to aid in reconstruction
efficiency. For Tomte glitches, which have a peak frequency around 50-60 Hz, a
10-128 Hz bandpass to the training data ensures we are not overfitting noise
outside the glitch time, but still recover more than 99% of the SNR from more
than 99% of training glitches. We find that 0.5s training window is always
adequate for tomtes, with typical duration 0.1s. For blips, peak frequencies
are typically 500-1000 Hz, so we obtain similar recovered SNR by bandpassing
from 10-1024 Hz. We find that a 0.1s window is almost always adequate for
blips (allowing one full cycle at 10 Hz). Blips are shorter in duration
(almost always shorter than 30ms). For run segments on test glitches and
marginal/glitch-like events we keep data in 10-2048 Hz, retaining higher
frequency noise. All training examples are centered on the peak amplitude time
sample. All preprocessing is performed using open-source libraries including
NumPy van der Walt  _et al._ (2011) and GWPy Macleod  _et al._ (2021).

####  II.4.3 Performance

The model is easily run and bench-marked on a laptop with six cores. The
training process takes less than 1 second for 2000 glitches. Maximum
likelihood reconstruction takes 1ms-1$\mu$s depending on how much leeway in
center time we allow. Sampling proceeds quickly, giving 10,000 independent
samples of the posterior distribution in about 5 minutes, depending on the
glitch.

By weighing the likelihood against an Occam’s penalty, we can ensure our model
has the appropriate number of dimensions ($q$) and is not over fitting. We
employ a Laplace approximation to the marginal likelihood Minka (2000), along
with the Bayesian information criterion, described further in appendix A, to
choose the optimal number of eigenvectors for calculating the residuals of the
test sets, in the next section. To roughly match the degrees-of-freedom (per-
detector) of the CBC model, we employ $q=5$ in all sampled cases.

##  III Results

###  III.1 Testing with Maximum Likelihood Reconstruction

We reserve 10% of glitches for testing (the model has never encountered these
examples), and to evaluate the performance of our model we examine residuals
after maximum likelihood reconstruction and subtraction, as seen in Figure 3
histograms. This demonstrates the efficacy of the model in mitigating an
entire class of glitches. Test sets shown include 100-200 glitches. We will
soon extend this to cleaning entire search backgrounds, and attempt re-ranking
of CBC searches.

We plot residuals after glitch subtraction in the frequency domain. They obey
a Gaussian distribution after perfect glitch cleaning under the hypothesis of
stationary, uncorrelated noise. Cleaning models are trained with the automatic
choice of dimensionality via Laplace approximation (described in Appendix A):
(15, 2, 9, 8), for H1 blips(truncated from 23 to 15), H1 tomtes, L1 blips, L1
tomtes, respectively.

The binning in Figure 3 extends down to single samples from single test
glitches, showing that for all classes and detectors our results are
consistent with Gaussian noise. The performance is somewhat higher for tomte
glitches, mainly due to the greater homogeneity in their morphology compared
to blips. Tomtes in Livingston were 10-20 times more prevalent than in Hanford
Soni  _et al._ (2021). This has been partly attributed to Livingston operating
at greater sensitivity than Hanford during O3a, but may also be to to unknown
environmental factors. It is observed that blips and tomtes are louder at
higher sensitivity. Higher SNR and greater numbers allow for better modelling,
but show the increasing importance of mitigation as sensitivity improves in
future observing runs.

Figure 3: Frequency-domain residuals after subtraction from the test set (10%)
reserved from each glitch type, detector, and epoch. The bins are scaled such
that the lowest visible represent single samples from single glitches. Note
that extremal samples are louder in Livingston. It has been observed that with
greater sensitivity and range transient glitches become louder as well Soni
_et al._ (2021).

Figure 4: H1 O3a test blip: full posterior estimation. Note the repeating
blips afterward. This example shows the tendency of the sampler to converge on
the loudest glitch available. The histogram of center time samples shows high
certainty (just below the timeseries reconstruction). In the corner plot for
the latent space weights (z1-z5), we see that this test set glitch is typical
of the class.

Figure 5: L1 O3a test tomte: full posterior estimation. This is a very typical
tomte glitch, with all walkers converging on the same center time, low
uncertainties in the timeseries reconstruction, and the posterior distribution
aligning well with the distributions on the training set latent weights.

###  III.2 Sampling

We employ two well developed MCMC toolkits, emcee Foreman-Mackey  _et al._
(2013), and kombine Farr and Farr (2015), to perform a full Bayesian posterior
estimation of our reconstruction. By allowing the center time of the
hypothesized glitch to vary, we sample in q+1 dimensions. A priori, we assume
glitches are equally likely at any time, and thus adopt a uniform prior in
center time. The localization of the samples in center time is a good
indicator of how glitchlike the morphology of the test signal is. To aid in
the efficiency of sampling, we initialize walkers in a Gaussian around the
suspected glitch time. In the $q$ PPCA weights, we use a less restrictive wide
Gaussian prior, or alternately a highly-informed KDE (kernel density estimate)
prior based on the entire training set’s maximum likelihood weights. The
latter is generally more restrictive and can limit the flexibility of the
sampler to fit more general morphologies, which in some cases may be ideal,
and in others can to be adjusted. For all MCMC sampled example glitches and
CBC comparisons in the paper, we employ $q=5$.

In Figures 5 and 5 we demonstrate the results of sampling on a test blip in
Hanford, and a test tomte in Livingston. The blip was chosen specifically due
to it’s proximity to further repeating blips. The sampler converges easily on
the loudest glitch-like event in the run-segment.

###  III.3 Signal Safety Testing

To establish the model’s capability of distinguishing glitch from
astrophysical signal, we test if it remains flexible enough to fit different
glitch morphologies while being (appropriately) unable to reconstruct and
subtract an astrophysical signal. We run our model on a selection of high-
mass, short duration BBH signals from GWTC-2 et.al. (2021), acquiring data
from the Gravitational Wave Open Science Center(GWOSC)Abbott  _et al._ (2021).
Specifically, we choose events with high detector frame chirp masses (and by
extension, short template durations), and FAR (False Alarm Rate)$<10^{-3}/yr$.
Being the confirmed astrophysical signals with morphology closest to short
transient glitches such as blips and especially tomtes, these provide a good
opportunity to confuse the model. We quote maximum likelihood single detector
SNR values for the CBC and alternately the glitch hypotheses in Table 2.
Quoted durations are the template duration for the preferred trigger from low
latency detection. Two events had H1 offline at the trigger time but were
included for their glitchlike morphology. We anticipate that an effective
glitch model may be instrumental in vetting single-detector events in the
future.

For a more rigorous comparison between the CBC and glitch models we employ a
full posterior estimation framework and the Deviance Information Criterion
(DIC). This is a variance based approach. The DIC is given by:

$DIC=D(\bar{\theta})+\overline{\mathrm{var}(D(\theta))}$ (13)

Where the deviance, D, is: $D(\theta)=-2\ln(p(d|\theta))$ with posterior
distribution p, data y, and parameters $\theta$. Given the log likelihoods
from samples obtained using both the Glitchen model and a CBC PE run we see
that the glitch hypothesis is heavily disfavored for all events tested. These
comparisons appear in Table II, where a lower DIC value indicates a better
model for the observed data.

Event Information |  | Matched-Filter SNR
---|---|---
Event Name |  $\mathcal{M}_{\mathrm{det}}$, $M_{\odot}$ | duration(s) |  | CBC H1 | Tomte H1 | Blip H1 | CBC L1 | Tomte L1 | Blip L1
GW190521 | $114.8^{+15.2}_{-17.6}$ | 0.15 |  | 7.87 | 4.11 | 3.21 | 12.38 | 5.93 | 4.06
GW190602_175927 | $72.9^{+10.8}_{-13.7}$ | 0.22 |  | 6.56 | 3.60 | 3.55 | 11.02 | 4.43 | 4.88
GW190706_222641 | $75.1^{+11.0}_{-17.5}$ | 0.15 |  | 9.07 | 4.91 | 4.22 | 9.18 | 3.92 | 3.93
GW190519_153544 | $65.1^{+7.7}_{-10.3}$ | 0.17 |  | 9.50 | 4.42 | 4.76 | 11.85 | 5.42 | 4.25
GW190620_030421 | $57.5^{+9.0}_{-11.2}$ | 2.3 |  | (offline) | - | - | 11.70 | 3.78 | 4.63
GW190910_112807 | $43.9^{+4.6}_{-3.6}$ | 1.8 |  | (offline) | - | - | 13.86 | 6.29 | 4.26
GW190521_074359 | $39.8^{+2.2}_{-3.0}$ | 0.24 |  | 12.67 | 5.85 | 6.30 | 22.68 | 8.83 | 7.24

Table 1: Selecting short duration, heavy BBH mergers we provide an important
test for the model, which should give lower SNRs than the CBC model. Events
are in order of detector frame chirp mass ($\mathcal{M}_{\mathrm{det}}$,
$M_{\odot}$). For all of these events we see lower SNRs by a factor of 2-3,
whereas we expect to recover nearly all of the SNR in confirmed glitches. CBC
parameter estimation results from et.al. (2021).

Event Name | Deviance Information Criterion (DIC) |
---|---|---
| CBC H1 | Tomte H1 | Blip H1 |  | CBC L1 | Tomte L1 | Blip L1
GW190521 | -54.6 | -5.4 | 8.7 |  | -130.3 | -26.7 | 9.94
GW190602_175927 | -37.3 | 10.2 | 8.7 |  | -105.6 | -5.6 | 12.0
GW190706_222641 | -71.0 | 13.2 | 9.6 |  | -74.0 | 14.8 | 8.1
GW190519_153544 | -87.7 | 18.4 | -18.6 |  | -145.2 | 25.1 | 13.1
GW190620_030421 | - | - | - |  | -133.9 | 17.5 | 12.5
GW190910_112807 | - | - | - |  | -190.3 | -28.5 | 17.7
GW190521_074359 | -152.8 | 34.0 | 36.4 |  | -494.5 | -67.1 | -45.3

Table 2: Running samplers on these events, we obtain the DIC from our
distributions of log likelihoods. The deviance information criterion (DIC)
favors models with a lower value. The CBC model is highly preferred to the
glitch model in all cases, indicating that pass the signal safety test.

###  III.4 GW190521: testing our model’s limits with the most massive (and
glitch-like) confident O3a event

GW190521 is the highest mass ($142^{+28}_{-16}M_{\odot}$) and shortest
duration ( 0.1s) CBC event for which we have strong evidence Abbott  _et al._
(2020c). Being a loud triple detector event, it is confidently of
astrophysical origin. But for us, it offers a unique opportunity to test our
model, since it exhibits signal morphology which is the most “glitch-like” of
all high significance astrophysical events. It spent only the last 4 cycles of
its inspiral in the sensitive band of the detector, peaking at 60Hz. Tomte
glitches look very similar.

Critically, any model for tomtes, at bare minimum, must not be confused by
such an event. Because the aim of improved glitch mitigation is to open up
this high mass region of parameter space, this is precisely the kind of test
we need to pass. Here we demonstrate our full posterior estimation framework
on GW190521, and by extension, our ability to distinguish glitch-like
astrophysical events from glitches by comparing our glitch hypothesis results
with the astrophysical hypothesis results.

In both L1 and H1 (Figures 6 and 7, respectively), we see that the glitch
model (MaxL glitch reconstruction in green) is unable to fully capture the
signal morphology, with the MaxL CBC reconstruction in black, no matter where
it is placed. It remains multi-modal in center time, and an outlier in most of
the training set weights, indicating that this is a poor fit to the data, as
we expect. High uncertainty is seen in the broadness of the posterior
reconstructions, in orange on the timeseries plots. See Tables I and II for a
more quantitative comparison of the glitch and CBC hypothesis, for this and
other events in O3a.

Figure 6: GW190521 Full Posterior Estimation, L1. The distribution in the
center time is multi-modal, indicating that the glitch model fails to capture
the full morphology of the signal (LALInference maxL in black), no matter
where it is placed. The reconstruction features high uncertainty (samples in
orange), and the posterior distribution in the latent variables lies outside
the training set of glitches. All of this indicates that the model has failed
to reconstruct GW190521 as a glitch, as expected.

Figure 7: GW190521 Full Posterior Estimation, H1

##  IV Conclusion and Future Work

We have introduced a PPCA-based approach to modeling transient noise in
gravitational wave detector data, implemented in the open-sourced glitschen
package, publicly available here:
111https://git.ligo.org/jonathan.merritt/glitschen. We welcome collaborative
development, testing, and feedback.

For both ‘blip’ and ‘tomte’ glitches – some of the most impactful for BBH
searches in O3 – we have demonstrated the effectiveness of the model for
glitch subtraction, as well as for Bayesian model comparisons with
astrophysical signal models.

In future work we will explore the use of clustering algorithms in PPCA space
for glitch classification and sub-classification. We will test the
effectiveness of the model in reducing the background for compact binary
searches. We will also integrate our model into the Bilby Ashton  _et al._
(2019) parameter estimation code, where composite signal and noise models will
allow us to marginalize over glitch morphology when glitches are coincident
with astrophysical signals.

We tested our model on high-mass events from O3a, but in the future we will
extend this testing to simulations in the high-mass and high mass-ratio region
of parameter space, where discoveries are still to be made and distinguishing
astrophysical events from noise is even more difficult.

Because burst searches also trigger on glitches, we plan to test our model in
this regime. Searches for cosmic string cusps, supernova templates, and all
agnosticly un-modeled sources could radically change the field, but only if we
can work on the serious blind-spots in our searches. We have already began an
injection campaign with cosmic string templates in the parameter space
contaminated by blip glitches to determine our ability to differentiate signal
from glitch in this context. We plan to extend the use of our model beyond
Blips and Tomtes, but because these are the most impactful for BBH searches,
they remain the first and most important testing ground.

With more accurate models of glitches, we can improve the detectability and
significance of gravitational wave events of all kinds.

##  V Acknowledgements

Here we thank the GravitySpy team, the detector characterization working
group, and everyone who made this effort possible. We’re grateful to the CBC,
Detchar, and Parameter Estimation groups for their hard work building powerful
software tools and tutorials and organizing workshops that help make LIGO data
analysis work more accessible.

The authors are grateful for computational resources provided by the LIGO Lab
(CIT, LHO, LLO) and supported by National Science Foundation Grants
PHY-0757058 and PHY-0823459. This material is based upon work supported in
part by the National Science Foundation under Grant PHY-2110636. We are
grateful for the following open-source software tools: NumPy (van der Walt
_et al._ , 2011), SciPy (Virtanen  _et al._ , 2020), GWpy (Macleod  _et al._ ,
2021), Matplotlib (Hunter, 2007), bilby (Ashton  _et al._ , 2019).

## References

  * Abbott  _et al._ (2016) B. Abbott, R. Abbott, T. Abbott, M. Abernathy, F. Acernese, K. Ackley, C. Adams, T. Adams, P. Addesso, R. Adhikari, and et al., Physical Review Letters 116 (2016), 10.1103/physrevlett.116.131103.
  * Schofield  _et al._ (2017) R. Schofield, P. Covas, A. Effler, and R. Savage, “Why the gw channel detects thirsty black ravens along with colliding black holes,” (2017), https://alog.ligo-wa.caltech.edu/aLOG/index.php?callRep=37630.
  * et. al. (2021) D. D. et. al., (2021), arXiv:2101.11673 [astro-ph.IM] .
  * et.al. (2021) R. A. et.al., (2021), arXiv:2010.14527 [gr-qc] .
  * Collaboration  _et al._ (2021) T. L. S. Collaboration, the Virgo Collaboration, and R. A. et. al., “Gwtc-2.1: Deep extended catalog of compact binary coalescences observed by ligo and virgo during the first half of the third observing run,” (2021), arXiv:2108.01045 [gr-qc] .
  * Abbott  _et al._ (2020a) B. P. Abbott, R. Abbott, T. D. Abbott, S. Abraham, F. Acernese, K. Ackley, C. Adams, V. B. Adya, C. Affeldt, and et al., Living Reviews in Relativity 23 (2020a), 10.1007/s41114-020-00026-9.
  * Cabero  _et al._ (2019) M. Cabero, A. Lundgren, A. H. Nitz, T. Dent, D. Barker, E. Goetz, J. S. Kissel, L. K. Nuttall, P. Schale, R. Schofield, and et al., Classical and Quantum Gravity 36, 155010 (2019).
  * Müller and Anabel (2018) C. Müller and M. Anabel,  _Gravitational-Wave Astronomy with Compact Binary Coalescences : From Blip Glitches to the Black Hole Area Increase Law_ , Doctoral Thesis, Hannover : Institutionelles Repositorium der Leibniz Universität Hannover (2018).
  * Abbott  _et al._ (2020b) B. P. Abbott, R. Abbott, T. D. Abbott, S. Abraham, F. Acernese, K. Ackley, C. Adams, V. B. Adya, C. Affeldt, M. Agathos, and et al., Classical and Quantum Gravity 37, 055002 (2020b), arXiv:1908.11170 .
  * Soni  _et al._ (2021) S. Soni, C. P. L. Berry, S. B. Coughlin, M. Harandi, C. B. Jackson, K. Crowston, C. Østerlund, O. Patane, A. K. Katsaggelos, L. Trouille, V.-G. Baranowski, W. F. Domainko, K. Kaminski, M. A. L. Rodriguez, U. Marciniak, P. Nauta, G. Niklasch, R. R. Rote, B. Téglás, C. Unsworth, and C. Zhang, “Discovering features in gravitational-wave data through detector characterization, citizen science and machine learning,” (2021), arXiv:2103.12104 [gr-qc] .
  * Davis  _et al._ (2020) D. Davis, L. V. White, and P. R. Saulson, Classical and Quantum Gravity 37, 145001 (2020).
  * Zevin  _et al._ (2017) M. Zevin, S. Coughlin, S. Bahaadini, E. Besler, N. Rohani, S. Allen, M. Cabero, K. Crowston, A. K. Katsaggelos, S. L. Larson, and et al., Classical and Quantum Gravity 34, 064003 (2017).
  * Chatterji  _et al._ (2004) S. Chatterji, L. Blackburn, G. Martin, and E. Katsavounidis, Classical and Quantum Gravity 21, S1809–S1818 (2004).
  * Braginsky  _et al._ (2006) V. Braginsky, O. Ryazhskaya, and S. Vyatchanin, Physics Letters A 350, 1–4 (2006).
  * Yamamoto  _et al._ (2008) K. Yamamoto, H. Hayakawa, A. Okada, T. Uchiyama, S. Miyoki, M. Ohashi, K. Kuroda, N. Kanda, D. Tatsumi, and Y. Tsunesada, Physical Review D 78 (2008), 10.1103/physrevd.78.022004.
  * (16) A. Helmling-Cornell, “Blip glitches in ligo hanford,” Https://dcc.ligo.org/LIGO-G2001007/public.
  * Tipping and Bishop (1999) M. E. Tipping and C. Bishop, Journal of the Royal Statistical Society, Series B 21, 611 (1999), available from http://www.ncrg.aston.ac.uk/Papers/index.html.
  * Powell  _et al._ (2015) J. Powell, D. Trifirò, E. Cuoco, I. S. Heng, and M. Cavaglià, Classical and Quantum Gravity 32, 215012 (2015).
  * Powell  _et al._ (2017) J. Powell, A. Torres-Forné, R. Lynch, D. Trifirò, E. Cuoco, M. Cavaglià, I. S. Heng, and J. A. Font, Classical and Quantum Gravity 34, 034002 (2017).
  * Mukherjee  _et al._ (2010) S. Mukherjee, R. Obaid, and B. Matkarimov, Journal of Physics: Conference Series 243, 012006 (2010).
  * Cornish and Littenberg (2015) N. J. Cornish and T. B. Littenberg, Classical and Quantum Gravity 32, 135012 (2015).
  * Torres-Forné  _et al._ (2020) A. Torres-Forné, E. Cuoco, J. A. Font, and A. Marquina, Physical Review D 102 (2020), 10.1103/physrevd.102.023011.
  * Cornish  _et al._ (2021) N. J. Cornish, T. B. Littenberg, B. Bécsy, K. Chatziioannou, J. A. Clark, S. Ghonge, and M. Millhouse, Phys. Rev. D 103, 044006 (2021), arXiv:2011.09494 [gr-qc] .
  * Cornish (2021) N. J. Cornish, Phys. Rev. D 103, 104057 (2021), arXiv:2101.01188 [gr-qc] .
  * (25) in  _Gravitational‐Wave Physics and Astronomy_ (John Wiley & Sons, Ltd) pp. I–XIV.
  * Dillon  _et al._ (2017) J. V. Dillon, I. Langmore, D. Tran, E. Brevdo, S. Vasudevan, D. Moore, B. Patton, A. Alemi, M. Hoffman, and R. A. Saurous, “Tensorflow distributions,” (2017), arXiv:1711.10604 [cs.LG] .
  * van der Walt  _et al._ (2011) S. van der Walt, S. C. Colbert, and G. Varoquaux, Computing in Science & Engineering 13, 22–30 (2011).
  * Ashton  _et al._ (2019) G. Ashton, M. Hübner, P. D. Lasky, C. Talbot, K. Ackley, S. Biscoveanu, Q. Chu, A. Divakarla, P. J. Easter, B. Goncharov, and et al., The Astrophysical Journal Supplement Series 241 (2019), 10.3847/1538-4365/ab06fc, arXiv:1811.02042 [astro-ph.IM] .
  * Abbott  _et al._ (2021) R. Abbott, T. D. Abbott, S. Abraham, F. Acernese, K. Ackley, C. Adams, R. X. Adhikari, V. B. Adya, C. Affeldt, M. Agathos, and et al., SoftwareX 13, 100658 (2021).
  * Macleod  _et al._ (2021) D. Macleod, A. L. Urban, S. Coughlin, T. Massinger, M. Pitkin, rngeorge, paulaltin, J. Areeda, L. Singer, E. Quintero, K. Leinweber, and T. G. Badger, “gwpy/gwpy: 2.0.4,”  (2021).
  * Minka (2000) T. P. Minka,  _Automatic choice of dimensionality for PCA_ , Tech. Rep. (2000).
  * Foreman-Mackey  _et al._ (2013) D. Foreman-Mackey, D. W. Hogg, D. Lang, and J. Goodman, Publications of the Astronomical Society of the Pacific 125, 306–312 (2013).
  * Farr and Farr (2015) B. Farr and W. M. Farr, (2015), in prep.
  * Abbott  _et al._ (2020c) R. Abbott, T. Abbott, S. Abraham, F. Acernese, K. Ackley, C. Adams, R. Adhikari, V. Adya, C. Affeldt, M. Agathos, and et al., Physical Review Letters 125 (2020c), 10.1103/physrevlett.125.101102.
  * Note (1) Https://git.ligo.org/jonathan.merritt/glitschen.
  * Virtanen  _et al._ (2020) P. Virtanen, e. a. Gommers, and SciPy 1.0 Contributors, Nature Methods 17, 261 (2020).
  * Hunter (2007) J. D. Hunter, Computing in Science & Engineering 9, 90 (2007).

##  Appendix A Optimal Choice of the Model Dimensionality

To avoid over or under fitting we can use various metrics to find the optimal
number of PPCA eigenvectors to employ for each glitch type, detector, and
observing run. We tried a crude method: fraction of recovered SNR in test set
glitches. If we recover .99 of the known glitch SNR then any gains added with
additional dimensions are giving diminishing returns. However this cutoff
point is somewhat arbitrary. Instead, balancing an Occam’s penalty against the
model’s training set likelihood is a much more rigorous approach. We employed
several methods, including the Akaike information criterion (AIC), the
Bayesian information criterion (BIC), and the Laplace approximation to the
marginal model log-likelihood, following the method in Minka (2000). By
maximizing these metrics we can use the optimal level of model complexity. To
arrive at the Laplace approximation, we apply an uninformative conjugate prior
on the model parameters and marginalize over everything but q, the PPCA
dimensionality. The marginal log-likelihood values are estimates of the model
evidence and the ratio of these for different q can be taken as Bayes factors,
so far as the Laplace approximation is accurate, which we show in Figure 8.

Figure 8: The relative Bayes factors as a function of dimensionality, q, for
each detector and glitch type in the analysis. The peak of these curves allow
for an automatic choice of dimensionality that avoids over-fitting.


# Nonlocal metric dimension of graphs

Sandi Klavžar a,b,c Dorota Kuziak d

###### Abstract

Nonlocal metric dimension ${\rm dim}_{\rm n\ell}(G)$ of a graph $G$ is
introduced as the cardinality of a smallest nonlocal resolving set, that is, a
set of vertices which resolves each pair of non-adjacent vertices of $G$.
Graphs $G$ with ${\rm dim}_{\rm n\ell}(G)=1$ or with ${\rm dim}_{\rm
n\ell}(G)=n(G)-2$ are characterized. The nonlocal metric dimension is
determined for block graphs, for corona products, and for wheels. Two upper
bounds on the nonlocal metric dimension are proved. An embedding of an
arbitrary graph into a supergraph with a small nonlocal metric dimension and
small diameter is presented.

a Faculty of Mathematics and Physics, University of Ljubljana, Slovenia

b Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia

c Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia

<EMAIL_ADDRESS>
d Departamento de Estadística e Investigación Operativa, Universidad de Cádiz,
Algeciras, Spain

<EMAIL_ADDRESS>
Keywords: metric dimension; nonlocal metric dimension; block graphs; corona
product of graphs; edge cover number

AMS Subj. Class. (2020): 05C12, 05C76

##  1 Introduction

Let $G=(V(G),E(G))$ be a graph, $X\subseteq V(G)$, and $u,v\in V(G)$. Then $u$
and $v$ are resolved by $X$ if there exists $x\in X$ such that $d_{G}(u,x)\neq
d_{G}(v,x)$, where $d_{G}(y,z)$ denotes the shortest-path distance between
vertices $y$ and $z$ of $G$. A set $X$ such that each pair of vertices of $G$
is resolved by $X$ is a resolving set of $G$. A smallest resolving set is a
metric basis of $G$, its cardinality is the metric dimension of $G$ denoted by
$\dim(G)$. This concept is one of the central ones in the field of metric
graph theory, and its popularity stems, among other things, from the fact that
it has found many applications in fields as diverse as computer science,
chemistry, biology, and social sciences. For a better understanding of the
concept and its applications see the recent survey [18], while for a
comprehensive survey on its variants see the other recent survey [11].

In 2010, Okamoto, Phinezy, and Zhang [12] introduced the local metric
dimension of a graph as a natural version of the metric dimension. In this
version, which was further researched in particular in [1, 2, 3, 6, 10, 13,
14, 17], we need to resolve only pairs of adjacent vertices. The dual concept,
in which all pairs of non-adjacent vertices are to be resolved, has
surprisingly not been considered in the literature. In this paper we fill this
gap.

If $X\subseteq V(G)$ resolves each pair of non-adjacent vertices, then we
speak of a nonlocal resolving set. A smallest nonlocal resolving set is a
nonlocal metric basis of $G$, its cardinality is the nonlocal metric dimension
of $G$ and will be denoted by ${\rm dim}_{\rm n\ell}(G)$. By definition,

${\rm dim}_{\rm n\ell}(G)\leq\dim(G)$ (1)

holds for every graph $G$. The difference can be arbitrary large as already
demonstrated by complete graphs for which we have ${\rm dim}_{\rm
n\ell}(K_{n})=0$ and $\dim(K_{n})=n-1$ for every $n\geq 1$.

We proceed as follows. In the next section we first recall definitions,
notation, and a result needed later. Then we characterize the graphs with the
nonlocal metric dimension equal to $1$, and show that ${\rm dim}_{\rm
n\ell}(G)=\dim(G)$ holds for bipartite graphs $G$. In Section 3 we determine
the nonlocal metric dimension for block graphs and for corona products. The
latter result is reduced to a join of a graph with $K_{1}$. This motivates us
to determine the nonlocal metric dimension of wheels in Section 4. In the
subsequent section we prove two upper bounds on the nonlocal metric dimension
and characterize graphs $G$ with ${\rm dim}_{\rm n\ell}(G)=n(G)-2$. In Section
6, we embed an arbitrary graph into a supergraph with a small nonlocal metric
dimension and small diameter. In the concluding section directions for further
study are indicated.

##  2 Preliminaries

Unless stated otherwise, graphs considered will be connected. The order of a
graph $G$ will be denoted by $n(G)$. If $X=\\{x_{1},\dots,x_{k}\\}$ and $u\in
V(G)$, then the metric representation of u with respect to $X$ is the vector
$r(u|X)=(d_{G}(u,x_{1}),\dots,d_{G}(u,x_{k}))$. The diameter ${\rm diam}(G)$
of $G$ is the largest distance between pairs of vertices of $G$. The clique
number of $G$ is the order of a largest complete subgraph in $G$ and denoted
by $\omega(G)$. As usual, the chromatic number of $G$ is denoted by $\chi(G)$.
The edge cover number $\beta^{\prime}(G)$ of $G$ is the smallest number of
edges such that each vertex is incident with at least one of these edges. The
join $G+H$ of graphs $G$ and $H$ is obtained from the disjoint union of a copy
of $G$ and a copy of $H$ by adding an edge between each vertex of $G$ and each
vertex of $H$. The complement of $G$ will be denoted by $\overline{G}$. For a
positive integer $k$ we will use the notation $[k]=\\{1,\ldots,k\\}$.

A vertex of degree at least $3$ in a tree $T$ is called a _branch vertex_. A
leaf $u$ of $T$ is called a _terminal leaf_ of a branch vertex $v$ of $T$ if
$d_{T}(u,v)<d_{T}(u,w)$ for every other branch vertex $w$ of $T$. A branch
vertex $v$ of $T$ is an _exterior branch vertex_ of $T$ if it has at least one
terminal leaf. The path from an exterior branch vertex to its terminal leaf is
called a _terminal path_. Let $n_{1}(T)$ denote the number of leaves of $T$,
and let ${\rm ex}(T)$ denote the number of exterior branch vertices of $T$. In
[5, 7, 15] it was proved that if $T$ is a tree that is not a path, then

$\dim(T)=n_{1}(T)-{\rm ex}(T).$ (2)

We already mentioned that ${\rm dim}_{\rm n\ell}(K_{n})=0$ for $n\geq 1$.
Moreover, as soon as $G$ is not complete, ${\rm dim}_{\rm n\ell}(G)\geq 1$.
Clearly, ${\rm dim}_{\rm n\ell}(P_{n})=1$ for $n\geq 3$. It is also not
difficult to see that ${\rm dim}_{\rm n\ell}(C_{n})=2$ for $n\geq 4$.

To characterize graphs $G$ with ${\rm dim}_{\rm n\ell}(G)=1$, we need the
following concept. If $x\in V(G)$ and $k\geq 0$, then $L_{k}(x)=\\{u\in V(G):\
d_{G}(x,u)=k\\}$ is a distance level of $x$. In particular,
$L_{0}(x)=\\{x\\}$, and $L_{1}(x)$ is the (open) neighborhood of $x$.

###### Proposition 2.1

If $G$ is a non-complete graph, then ${\rm dim}_{\rm n\ell}(G)=1$ if and only
if there exists a vertex $x$ such that $L_{k}(x)$ induces a complete graph for
every $k\leq{\rm diam}(G)$.

Proof. Assume first that ${\rm dim}_{\rm n\ell}(G)=1$ and let $\\{x\\}$ be a
nonlocal metric basis. If $u,v\in L_{k}(x)$ for some $k\geq 1$, then
$d_{G}(x,u)=d_{G}(x,v)=k$ and hence $u$ and $v$ must be adjacent. Thus
$L_{k}(x)$ induces a complete graph. ($L_{0}(x)$ is trivially complete.)

Conversely, let $x$ be a vertex whose all distance levels induce complete
graphs. Therefore, if $u,v\in V(G)$ and $uv\notin E(G)$, then $d_{G}(x,u)\neq
d_{G}(x,v)$ and so $u$ and $v$ are resolved by $x$. $\square$

In general ${\rm dim}_{\rm n\ell}(G)$ can be arbitrary smaller than $\dim(G)$.
This cannot happen if $G$ is bipartite as the next result asserts.

###### Proposition 2.2

If $G$ is a bipartite graph with $n(G)\geq 3$, then ${\rm dim}_{\rm
n\ell}(G)=\dim(G)$.

Proof. By (1) we have ${\rm dim}_{\rm n\ell}(G)\leq\dim(G)$. Let $X$ be a
nonlocal metric basis of $G$. As $n(G)\geq 3$, $G$ is not complete and hence
$|X|\geq 1$. Consider arbitrary vertices $u,v\in V(G)$. If $uv\notin E(G)$,
then $u$ and $v$ are resolved by $X$ because $X$ is a nonlocal resolving set.
If $uv\in E(G)$, then $u$ and $v$ are resolved by $X$ since $G$ is bipartite.
It follows that $X$ is also a resolving set. Hence $\dim(G)\leq|X|={\rm
dim}_{\rm n\ell}(G)$ and we are done. $\square$

##  3 Block graphs and corona products

Proposition 2.2 implies that if $T$ is a tree with $n(T)\geq 3$, then ${\rm
dim}_{\rm n\ell}(T)=\dim(T)$. This fact generalizes to block graphs as
follows. Let $G$ be a block graph. The block-cutpoint tree $\widehat{G}$ of
$G$ is the tree whose vertices are the blocks and the cut-vertices of $G$, and
a block $B$ is adjacent to a cut-vertex $v$ if $v\in V(B)$, cf. [19,
Definition 4.1.20].

###### Theorem 3.1

If $G$ is a block graph with $n(G)\geq 3$, then ${\rm dim}_{\rm
n\ell}(G)=\dim(\widehat{G})$.

Proof. We can extend the terminology for trees from the previous section to
block graphs as follows. Let $G$ be a block graph. A block $B$ of $G$ is
called a _branch block_ if the vertices of $B$ have at least three independent
neighbors outside of $B$. A branch block $B$ of $G$ is an _exterior branch
block_ of $G$ if in $\widehat{G}$ there exist $t\geq 1$ terminal paths
emanating from a cut-vertex of $B$. If so, we say that $B$ has $t$ rays.

Let now $X$ be a nonlocal resolving set of $G$. If $B$ is an exterior branch
block of $G$ with $t$ rays, then we claim that $X$ has at least $t-1$ vertices
in these rays, each one from a different ray. Indeed, otherwise there exist
two rays $R_{1}$ and $R_{2}$ with no vertex from $X$. Let $R_{1}$ and $R_{2}$
be attached to $B$ at vertices $u_{1}$ and $u_{2}$ (note that $u_{1}=u_{2}$ is
possible), and select neighbors $v_{1}$ and $v_{2}$ of $u_{1}$ and $u_{2}$ in
$R_{1}$ and $R_{2}$, respectively, Then $v_{1}$ and $v_{2}$ are not adjacent
and have the same metric representation with respect to $X$. This proves the
claim. Each exterior branch block of $G$ corresponds to an exterior branch
vertex of $\widehat{G}$. Since $\widehat{G}$ is a tree, (2) implies that ${\rm
dim}_{\rm n\ell}(G)\geq\dim(\widehat{G})$.

To prove that ${\rm dim}_{\rm n\ell}(G)\leq\dim(\widehat{G})$ holds, let $X$
be a metric basis of $\widehat{G}$. We may without loss of generality assume
that every element of $X$ is a leaf of $\widehat{G}$. Then each element $x\in
X$ corresponds to a terminal block $B_{x}$ of $G$, that is, a block which
contains exactly one cut-vertex. For every $x\in X$, let $w_{x}$ be an
arbitrary but fixed vertex of $B_{x}$ which is not a cut-vertex. Set
$Y=\\{w_{x}:\ x\in X\\}$. Since we do not need to resolve adjacent vertices,
it is straightforward to check that $Y$ is a nonlocal resolving set of $G$.
Hence ${\rm dim}_{\rm n\ell}(G)\leq|Y|=|X|=\dim(\widehat{G})$. $\square$

The metric dimension of block graphs was studied in [8]. It was proved that
the metric dimension of a block graph $G$ is equal to the metric dimension of
a tree, obtained from $G$ by replacing each block $B$ of size at least $3$ by
a star whose leaves are the vertices of $B$. The local metric dimension of
block graphs was investigated in [14].

Let $G$ and $H$ be graphs where $V(G)=\\{g_{1},\ldots,g_{n(G)}\\}$. The
_corona product_ of $G$ and $H$, denoted by $G\odot H$, is a graph obtained
from the disjoint union of a copy of $G$ and $n(G)$ copies of $H$, denoted by
$H_{i}$, $i\in[n(G)]$. The product $G\odot H$ is then constructed by making
$g_{i}$ adjacent to every vertex in $H_{i}$ for each $i\in[n(G)]$. Let further
$\widetilde{H_{i}}$ be the subgraph of $G\odot H$ induced by
$V(H_{i})\cup\\{g_{i}\\}$. Clearly, $\widetilde{H_{i}}\cong H+K_{1}$. We will
use this notation in the rest of the section.

The metric dimension of corona products has been investigated in [9, 20]. The
local metric dimension of corona products has been studied in [13] and more
generally of generalized hierarchical products in [10]. In particular, in [13]
it is proved for the local metric dimension ${\rm dim_{\ell}}$ that if $G$ is
a connected graph and $H$ is a graph of radius at least $4$, then ${\rm
dim_{\ell}}(G\odot H)=n(G)\cdot{\rm dim_{\ell}}(H+K_{1})$. In general, ${\rm
dim_{\ell}}(G\odot H)\leq n(G)\cdot{\rm dim_{\ell}}(H+K_{1})$, see [10]. Here
we add the following formula for the nonlocal metric dimension.

###### Theorem 3.2

If $G$ is a graph and $H$ a non-complete graph, then

${\rm dim}_{\rm n\ell}(G\odot H)=n(G)\cdot{\rm dim}_{\rm n\ell}(H+K_{1}).$

Proof. Let $X$ be a nonlocal metric basis of $G\odot H$ and let $X_{i}=X\cap
V(\widetilde{H_{i}})$. If $u,v\in V(H_{i})$ and $w\in V(G\odot H)\setminus
V(H_{i})$, then $d_{G\odot H}(u,w)=d_{G\odot H}(v,w)$. Since also $d_{G\odot
H}(u,g_{i})=d_{G\odot H}(v,g_{i})=1$, any two non-adjacent vertices from
$H_{i}$ must be resolved by some vertex from $H_{i}$. Therefore, $X_{i}$ is a
nonlocal resolving set of $\widetilde{H_{i}}$ and so $|X_{i}|\geq{\rm
dim}_{\rm n\ell}(\widetilde{H_{i}})={\rm dim}_{\rm n\ell}(H+K_{1})$.
Consequently,

${\rm dim}_{\rm n\ell}(G\odot
H)=|X|=\sum_{i=1}^{n(G)}|X_{i}|\geq\sum_{i=1}^{n(G)}{\rm dim}_{\rm
n\ell}(\widetilde{H_{i}})=n(G)\cdot{\rm dim}_{\rm n\ell}(H+K_{1}).$

Let now $Y$ be a nonlocal metric basis of $H\odot K_{1}$. Since $H$ is not
complete, $|Y|\geq 1$. For each $i\in[n(G)]$, let $Y_{i}$ be the copy of $Y$
in $\widetilde{H_{i}}$. Note that $g_{i}\notin Y_{i}$. We claim that
$\cup_{i=1}^{n(G)}Y_{i}$ is a nonlocal resolving set of $G\odot H$. Indeed, if
vertices $u$ and $v$ from $V(H_{i})$ are non-adjacent, then they are resolved
by some vertex from $Y_{i}$. Assume next $u\in V(\widetilde{H_{i}})$ and $v\in
V(\widetilde{H_{j}})$, where $i\neq j$. If $y_{i}\in Y_{i}$, then
$d(y_{i},u)\leq 2$ and $d(y_{i},v)\geq 3$, hence $u$ and $v$ are again
resolved. We have thus seen that $\cup_{i=1}^{n(G)}Y_{i}$ is a nonlocal
resolving set and henceforth,

${\rm dim}_{\rm n\ell}(G\odot
H)\leq|\cup_{i=1}^{n(G)}Y_{i}|=n(G)\cdot|Y|=n(G)\cdot{\rm dim}_{\rm
n\ell}(H+K_{1}).$

We conclude that ${\rm dim}_{\rm n\ell}(G\odot H)=n(G)\cdot{\rm dim}_{\rm
n\ell}(H+K_{1})$. $\square$

In the case when the second factor of a corona product is complete, we can
bound the nonlocal metric dimension as follows.

###### Theorem 3.3

If $G$ is a graph and $n\geq 1$, then

$\dim(G)\leq{\rm dim}_{\rm n\ell}(G\odot K_{n})\leq n(G).$

Proof. To prove the upper bound we claim that $V(G)$ is a nonlocal resolving
set of $G\odot K_{n}$. Indeed, let $u,v\in V(G\odot K_{n})\setminus V(G)$ be
two non-adjacent vertices. Then $u\in H_{i}$ and $v\in H_{j}$ for some $i$ and
$j$, where $i\neq j$. As $d_{G\odot K_{n}}(u,g_{i})=1$ and $d_{G\odot
K_{n}}(v,g_{i})\geq 2$, the claim follows. Hence ${\rm dim}_{\rm n\ell}(G\odot
K_{n})\leq n(G)$.

Let now $X$ be a nonlocal metric basis of $G\odot H$; then $|X|={\rm dim}_{\rm
n\ell}(G\odot H)$. Let $Y\subseteq V(G)$ be the set obtained from $X$ by
replacing each vertex $u\in X\cap V(\widetilde{H_{i}})$ by $g_{i}$. Note that
this in particular means that if $g_{i}\in X$, then also $g_{i}\in Y$.
Clearly, $|Y|\leq|X|$. We claim that $Y$ is a resolving set of $G$. For this
sake consider arbitrary vertices $g_{i},g_{j}\in V(G)\subseteq V(G\odot H)$.
Let $u\in V(H_{i})$ and $v\in V(H_{j})$. Since $X$ is a nonlocal metric basis
of $G\odot H$ and $uv\notin E(G\odot H)$, there exists a vertex $w\in X$ such
that $d_{G\odot H}(u,w)\neq d_{G\odot H}(v,w)$. If
$w\in\widetilde{H_{i}}\cup\widetilde{H_{j}}$, then $g_{i}\in Y$ or $g_{j}\in
Y$ and there is nothing to be proved. Suppose henceforth that
$w\in\widetilde{H_{k}}$, where $k\neq i,j$. If $w\neq g_{k}$, then

$1+d_{G}(g_{i},g_{k})+1=d_{G\odot H}(u,w)\neq d_{G\odot
H}(v,w)=1+d_{G}(g_{j},g_{k})+1,$

and if $w=g_{k}$, then

$\displaystyle 1+d_{G}(g_{i},g_{k})$ $\displaystyle=1+d_{G}(g_{i},w)$
$\displaystyle=d_{G\odot H}(u,w)\neq d_{G\odot H}(v,w)$
$\displaystyle=1+d_{G}(g_{j},w)=1+d_{G}(g_{j},g_{k}).$

In either case we get $d_{G}(g_{i},g_{k})\neq d_{G}(g_{j},g_{k})$. As
$g_{k}\in Y$, we have proved that $Y$ is a resolving set of $G$ which in turn
implies that

$\dim(G)\leq|Y|\leq|X|={\rm dim}_{\rm n\ell}(G\odot H)$

and we are done. $\square$

If $r,s\geq 3$, then it can be checked that ${\rm dim}_{\rm
n\ell}(K_{r,s}\odot K_{n})=r+s-2={\rm dim}_{\rm
n\ell}(K_{r,s})=\dim(K_{r,s})$. This shows the sharpness of the lower bound of
Theorem 3.3. On the other hand, if $m\geq 2$ and $n\geq 1$, then ${\rm
dim}_{\rm n\ell}(P_{m}\odot K_{n})=2$. Since $\dim(P_{m})=1$ and $n(K_{m})=m$,
the case $m=2$ shows the tightness of the upper bound, while the cases $m\geq
3$ demonstrate that the intermediate values are also attainable.

##  4 Nonlocal metric dimension of wheels

In Theorem 3.2, the nonlocal metric dimension of a corona product $G\odot H$
is reduced to the nonlocal metric dimension of the join of $H$ with $K_{1}$.
To determine the latter deserves a special attention. Here we solve it for the
join of a cycle with $K_{1}$, that is, for wheels. Recall that the wheel graph
$K_{1}+C_{n}$ of order $n+1\geq 4$ is denoted by $W_{1,n}$.

As a consequence of [13, Corollary 5(iv)] we obtain ${\rm
dim_{\ell}}(W_{1,n})=\lceil n/4\rceil$. The metric dimension of $W_{1,n}$ was
independently studied in [4, 16], where it is proved that if $n\geq 7$, then

$\dim(W_{1,n})=\left\lfloor{\frac{2n+2}{5}}\right\rfloor.$

Clearly, ${\rm dim}_{\rm n\ell}(W_{1,3})=1$ and ${\rm dim}_{\rm
n\ell}(W_{1,4})={\rm dim}_{\rm n\ell}(W_{1,5})={\rm dim}_{\rm
n\ell}(W_{1,6})=2$. The main result of this section reads as follows.

###### Theorem 4.1

If $n\geq 7$, then

${\rm dim}_{\rm n\ell}(W_{1,n})=\left\lfloor{\frac{2n}{5}}\right\rfloor.$

Note that if $n\geq 7$, then $\dim(W_{1,n})={\rm dim}_{\rm n\ell}(W_{1,n})$ if
and only if $n\bmod 5\in\\{0,1,3\\}$. Otherwise, ${\rm dim}_{\rm
n\ell}(W_{1,n})=\dim(W_{1,n})-1$. In the rest of the section we prove Theorem
4.1, for which some additional terminology is needed.

Let $V(C_{n})=\\{0,1,\dots,n-1\\}$ with natural adjacency. Operation with
vertices will be done modulo $n$. Let $v$ be the central vertex of the wheel
$W_{1,n}$, where $n\geq 7$. Notice first that, $v$ does not belong to any
nonlocal metric basis, since for any $0\leq i\leq n-1$, $v$ and $i$ are
adjacent. Let $X\subset V(C_{n})$ be a set of vertices such that $|X|\geq 2$.
A gap of $X$ is a set of vertices $A_{i,j}=\\{i+1,\dots,j-1\\}$, $|i-j|\geq
1$, of $C_{n}$ such that $i,j\in X$ and $\\{i+1,\dots,j-1\\}\cap X=\emptyset$.
We call $i$ and $j$ neighboring vertices of $X$. Two gaps $A_{i,j}$ and
$A_{j,k}$ are called neighboring gaps.

###### Lemma 4.2

Let $n\geq 7$, and let $S$ be a nonlocal metric basis of $W_{1,n}$. Then the
following hold.

  1. (i)

$|A_{i,j}|\leq 4$ for each gap of $S$.

  2. (ii)

$|A_{i,j}|\geq 3$ holds for at most one gap of $S$.

  3. (iii)

If $|A_{i,j}|\geq 2$, then each of the two neighboring gaps of $A_{i,j}$
contains at most one vertex.

  4. (iv)

Moreover, $W_{1,n}$ contains a nonlocal metric basis $S^{\prime}$ that fulfils
conditions (i)-(iii) and in addition has no gap of size $3$.

Proof. (i) Consider the gap $A_{i,j}$ and suppose that $j\geq i+6$, where
$i\leq n-1$. Then the vertices $i+2$ and $i+4$ have the same metric
representation with respect to $S$. As they are not adjacent, we have a
contradiction.

(ii) Suppose there exist two distinct gaps $A_{i,i+k}$ and
$A_{j,j+k^{\prime}}$, where $k,k^{\prime}\in\\{4,5\\}$. Then for two non-
adjacent vertices $i+2$ and $j+2$ we have $r(i+2|S)=r(j+2|S)$, a
contradiction.

(iii) Let $A_{i,j}$ be a gap with $j\geq i+3$. Consider now a neighboring gap,
without loss of generality let it be $A_{i^{\prime},i}$, and suppose that
$i-i^{\prime}>2$. Then the vertices $i-1$ and $i+1$ have the same metric
representation with respect to $S$. Again, as they are not adjacent, we have a
contraction.

(iv) Assume that $S$ contains a gap $A_{i,i+4}$. By (ii), this gap is the only
gap of size $3$. Moreover, by (iii), there are the following cases to be
considered. Assume first that $i+5\notin S$. Then $i+6$ must belong to $S$.
Let $S^{\prime}=(S\cup\\{i+5\\})\setminus\\{i+4\\}$. Having in mind that $i+2$
and $i+3$ are adjacent, it is straightforward to verify that $S^{\prime}$ is a
required nonlocal metric basis. The case when $i-1\notin S$ is treated
analogously. The last case to consider is when $i-1,i+5\in S$. Then $i+6\notin
S$ and the set $S^{\prime}=(S\cup\\{i+6\\})\setminus\\{i+4\\}$ is a required
nonlocal metric basis. $\square$

###### Lemma 4.3

Let $n\geq 7$. If $X\subseteq V(C_{n})$ satisfies conditions (i)-(iii) of
Lemma 4.2, then $X$ is a nonlocal resolving set of $W_{1,n}$.

Proof. Notice that by Proposition 2.1, ${\rm dim}_{\rm n\ell}(W_{1,n})\geq 2$,
for $n\geq 7$. Let $u\in V(W_{1,n})\setminus X$. As the central vertex $v$ is
adjacent to any other vertex, we may assume that $u\neq v$. We then
distinguish three cases.

Case 1: $u$ belongs to a gap $A_{i,i+2}$ (gap of size $1$).
Then $u=i+1$ and $u$ has distance $1$ to $i,i+2\in X$ and distance $2$ to all
other vertices of $X$. Hence any other vertex has different metric
representation with respect to $X$ because $n\geq 7$.

Case 2: $u$ belongs to a gap $A_{i,i+3}$ (gap of size $2$).
Let without loss of generality $u=i+1$. Then $u$ has distance $1$ to $i$ and
distance $2$ to all other vertices of $X$. By condition (iii) from Lemma 4.2,
there is no any other vertex with the same metric representation.

Case 3: $u$ belongs to a gap $A_{i,i+j}$, $j\in\\{4,5\\}$.
If $u=i+1$, then $u$ has distance $1$ to $i$ and distance $2$ to all the other
vertices of $X$. Hence, by condition (iii) of Lemma 4.2, there is no other
vertex with the same metric representation. The case when $u=i+j-1$ is done
similarly. Now, if $u\in\\{i+2,i+j-2\\}$, then $r(u|X)=(2,\dots,2)$. If $j=4$,
then there is only one such vertex, and if $j=5$, there are two such vertices.
In the latter case these two vertices are adjacent. By condition (ii) from
Lemma 4.2, no other vertex has this metric representation. $\square$

We are now in a position to prove Theorem 4.1. We construct a set $S\subseteq
V(W_{1,n})$ with $|S|=\left\lfloor{\frac{2n}{5}}\right\rfloor$ depending on
the residue class modulo $5$.

Case 1: $n\bmod 5\in\\{0,1\\}$.
Then $n=5k$ or $n=5k+1$, where $k\geq 2$. In both cases let
$S=\\{5i,5i+2:i\in[k-1]\\}\cup\\{0,5k-1\\}$. Notice that
$|S|=2k=\left\lfloor{\frac{2n}{5}}\right\rfloor$.

Case 2: $n\equiv 2\bmod 5$.
Then $n=5k+2$, where $k\geq 1$. Let $S=\\{5i,5i+2:1\leq i\leq
k-1\\}\cup\\{0,5k\\}$. Then $|S|=2k=\left\lfloor{\frac{2n}{5}}\right\rfloor$.

Case 3: $n\bmod 5\in\\{3,4\\}$.
Then $n=5k+3$ or $n=5k+4$, where $k\geq 1$. In both cases let
$S=\\{5i,5i+2:i\in[k]\\}\cup\\{0\\}$. Then
$|S|=2k+1=\left\lfloor{\frac{2n}{5}}\right\rfloor$.

In each case, the set $S$ fulfils the conditions of Lemma 4.3, hence $S$ is a
nonlocal resolving set of $W_{1,n}$ and thus ${\rm dim}_{\rm
n\ell}(W_{1,n})\leq\left\lfloor{\frac{2n}{5}}\right\rfloor$.

To prove that ${\rm dim}_{\rm
n\ell}(W_{1,n})\geq\left\lfloor{\frac{2n}{5}}\right\rfloor$, consider an
arbitrary nonlocal resolving set $X$ of $W_{1,n}$. In view of Lemma 4.2(iv) we
may without loss of generality assume that $X$ has no gaps of size $3$. We
distinguish two cases.

Case 1: $|X|=2r$, where $r\geq 1$.
By Lemma 4.2(iii), at most $r$ gaps contain two or four vertices, and by Lemma
4.2(ii), at most one of these gaps contains $4$ vertices. Hence, there is at
most $2(r-1)+4+r=3r+2$ vertices belonging to the gaps. Since $n\leq
2r+(3r+2)$, we have that $|X|=2r\geq 2\left(\frac{n-2}{5}\right)$. Since $2r$
is an integer we conclude that
$|X|\geq\left\lceil{\frac{2}{5}n-\frac{4}{5}}\right\rceil=\left\lfloor{\frac{2n}{5}}\right\rfloor$.

Case 2: $|X|=2r+1$, where $r\geq 1$.
Again, By Lemma 4.2(iii), at most $r$ gaps contain two or four vertices, and
by Lemma 4.2(ii), at most one of these gaps contains $4$ vertices. Hence in
this case there is at most $2(r-1)+4+(r+1)=3r+3$ vertices belonging to the
gaps. Since $n\leq 2r+1+(3r+3)$, we have that
$|X|=2r+1\geq\left\lceil{\frac{2}{5}n-\frac{3}{5}}\right\rceil\geq\left\lfloor{\frac{2n}{5}}\right\rfloor$.

This proves Theorem 4.1.

##  5 Upper bounds

In this section we prove two upper bounds on the nonlocal metric dimension.
Along the way we show that complete bipartite graphs can be characterized as
the graphs $G$ with ${\rm dim}_{\rm n\ell}(G)=n(G)-2$.

###### Proposition 5.1

If $G$ is a graph, then ${\rm dim}_{\rm n\ell}(G)\leq n(G)-\omega(G)$. In
particular, if $n(G)\geq 2$, then ${\rm dim}_{\rm n\ell}(G)\leq n(G)-2$.

Proof. Since ${\rm dim}_{\rm n\ell}(K_{n})=0$ for $n\geq 1$, the result holds
for complete graphs. Hence assume in the rest that $G$ is not complete and
$n(G)\geq 3$.

Let $Q$ be a clique of $G$ of order $\omega(G)$. Then we claim that
$V(G)\setminus V(Q)$ is a nonlocal resolving set. Indeed, let $u$ and $v$ be
non-adjacent vertices. At least one of them is not in $Q$, say $u$. Then
$d_{G}(u,u)=0<d_{G}(u,v)$ and since $u\in V(G)\setminus V(Q)$, the claim is
proved. Hence ${\rm dim}_{\rm n\ell}(G)\leq n(G)-n(Q)=n(G)-\omega(G)$. The
second assertion, ${\rm dim}_{\rm n\ell}(G)\leq n(G)-2$, follows using the
same argument except that we consider an arbitrary $K_{2}$ as a complete
subgraph. $\square$

In view of Proposition 5.1 we next describe graphs that attain the bound
$n(G)-2$.

###### Proposition 5.2

If $G$ is a graph, then ${\rm dim}_{\rm n\ell}(G)=n(G)-2$ if and only if
$G=K_{s,t}$, where $s\geq 1$ and $t\geq 2$.

Proof. If ${\rm dim}_{\rm n\ell}(G)=n(G)-2$, then by (1) we have $\dim(G)\geq
n(G)-2$. Since the only graphs $G$ with $\dim(G)=n(G)-1$ are complete graphs,
we can restrict our attention to the graphs $G$ with $\dim(G)=n(G)-2$. In [5]
it is proved that $\dim(G)=n(G)-2$ if and only if $G$ is one of the following
graphs: $K_{s,t}$ ($s\geq 1,t\geq 2$), $K_{s}+\overline{K_{t}}$ ($s\geq
1,t\geq 2$), and $K_{s}+(K_{1}\cup K_{t})$ ($s\geq 1,t\geq 1$). By (1) we know
that in each of these cases we have ${\rm dim}_{\rm n\ell}(G)\leq n(G)-2$.
Hence we need to determine in which of these cases we have ${\rm dim}_{\rm
n\ell}(G)\geq n(G)-2$.

Consider first complete bipartite graphs $K_{s,t}$ and let $S$ and $T$ be its
bipartition sets, where $|S|=s$ and $|T|=t$. If $u,v\in S$, then $u$ and $v$
have the same distance to all the other vertices. If follows that for each
nonlocal metric basis $X$ we have $|X\cap S|=s-1$. Analogously we get $|X\cap
T|=t-1$. Hence $|X|=(s-1)+(t-1)=n(K_{s,t})-2$.

Consider next joins $K_{s}+\overline{K_{t}}$, $s\geq 1$, $t\geq 2$. The case
$s=1$ has already been treated in the above paragraph, so assume that $s,t\geq
2$. Then $\omega(K_{s}+\overline{K_{t}})=s+1\geq 3$, and hence by Proposition
5.1 we have ${\rm dim}_{\rm n\ell}(K_{s}+\overline{K_{t}})\leq
n(K_{s}+\overline{K_{t}})-\omega(K_{s}+\overline{K_{t}})<n(K_{s}+\overline{K_{t}})-2$.

The last class of graphs to be considered is $K_{s}+(K_{1}\cup K_{t})$, $s\geq
1$, $t\geq 1$. If $s=t=1$, then $G=P_{3}$ which has already been considered
earlier. And if $s\geq 2$ or $t\geq 2$, then $\omega(G)\geq 3$ and we conclude
as in the previous case that none of the graphs qualifies for the theorem.
$\square$

###### Theorem 5.3

If $G$ is a graph of girth at least $7$, then ${\rm dim}_{\rm
n\ell}(G)\leq\beta^{\prime}(G)-1$. Moreover, if $G$ is a tree, then the
equality holds if and only if $G$ is obtained from a star by subdividing all
but one of the edges at most once.

Proof. Note first that the assertion is true for $K_{2}$ since ${\rm dim}_{\rm
n\ell}(K_{2})=0$. It is also clear that the result holds for paths since ${\rm
dim}_{\rm n\ell}(P_{n})=1$ for $n\geq 3$. Hence in the rest $n(G)\geq 4$ and
$\Delta(G)\geq 3$.

Assume first that there exists an edge cover $S$ of $G$ with
$|S|=\beta^{\prime}(G)\geq 2$, such that $S$ contains edges $xy$ and
$xy^{\prime}$, where $y\neq y^{\prime}$. We distinguish two cases.

Case 1: $\deg_{G}(y)=\deg_{G}(y^{\prime})=1$.
Then $\deg_{G}(x)\geq 3$. We define a set $X\subset V(G)$ as follows. Put into
$X$ all the neighbors of $x$ but $y^{\prime}$. Complete the construction of
$X$ by putting into it an arbitrary vertex from each of the edges $f\in S$
which has no vertex yet in $X$. Let $x^{\prime}$ be a neighbor of $x$
different from $y$ and $y^{\prime}$. Since $G$ is triangle-free, the vertex
$x^{\prime}$ is covered either by the edge $xx^{\prime}$, or by an edge
$x^{\prime}x^{\prime\prime}$, where $x^{\prime\prime}$ is not adjacent to $x$.
Therefore, $|X|\leq\beta^{\prime}(G)-1$. Note also that $x\notin X$. We claim
that $X$ is a nonlocal resolving set. For this sake select arbitrary vertices
$u,v\notin X$ such that $uv\notin E(G)$. If $u\in\\{x,y^{\prime}\\}$, then
because $\deg_{G}(y)=1$, the vertices $u$ and $v$ are resolved by $y$. Assume
next that $u,v\notin\\{x,y^{\prime}\\}$. Then there exist vertices
$u^{\prime}$ and $v^{\prime}$ such that $uu^{\prime},vv^{\prime}\in E(G)$ and
$u^{\prime},v^{\prime}\in X$. We claim that $u$ and $v$ are resolved by
$u^{\prime}$ and $v^{\prime}$. If this is not the case, then since
$d_{G}(u,u^{\prime})=1$ we have $d_{G}(v,u^{\prime})=1$, and because
$d_{G}(v,v^{\prime})=1$ we have $d_{G}(u,v^{\prime})=1$. But this implies that
$uu^{\prime}vv^{\prime}u$ is a $4$-cycle, a contradiction with our girth
assumption.

Case 2: $\deg_{G}(y)\geq 2$.
Let $y^{\prime\prime}$ be a neighbor of $y$ different from $x$. Then we infer
that $yy^{\prime\prime}\notin S$. Indeed, if $yy^{\prime\prime}\in S$, then
$S^{\prime}=S\setminus\\{xy\\}$ is an edge cover of $G$ of cardinality
$\beta^{\prime}(G)-1$. Hence $y^{\prime\prime}$ is an end-vertex of some edge
$y^{\prime\prime}y^{\prime\prime\prime}\in S$. Define now a set $X\subset
V(G)$ as follows. First put $x$ and $y^{\prime\prime}$ into $X$. In addition,
for any edge $f\in
S\setminus\\{xy,xy^{\prime},y^{\prime\prime}y^{\prime\prime\prime}\\}$ put
into $X$ an arbitrary vertex from $f$. Note that $|X|\leq\beta^{\prime}(G)-1$.
We claim that $X$ is a nonlocal resolving set. Let $u,v\notin X$ such that
$uv\notin E(G)$. Then we see that in every case there exist vertices
$u^{\prime}$ and $v^{\prime}$ such that $uu^{\prime},vv^{\prime}\in E(G)$ and
$u^{\prime},v^{\prime}\in X$. In particular, if $u=y$ and $v=y^{\prime}$, then
set $u^{\prime}=y^{\prime\prime}$ and $v^{\prime}=x$. Similarly, if $u=y$ and
$v=y^{\prime\prime\prime}$, then select $u^{\prime}=x$ and
$v^{\prime}=y^{\prime\prime}$. And if $u=y^{\prime}$ and
$v=y^{\prime\prime\prime}$, then set $u^{\prime}=x$ and
$v^{\prime}=y^{\prime\prime}$. In any case we see that the vertices $u$, $v$,
$u^{\prime}$ and $v^{\prime}$ lead to a $4$-cycle.

Assume second that every edge cover $G$ has cardinality $n(G)/2$. Let $S$ be
such an edge cover. Again we distinguish two cases.

Case 1: every edge from $S$ has an end-vertex of degree $1$.
Let $S=\\{x_{i}y_{i}:\ i\in[n(G)/2]\\}$ and assume without loss of generality
that $\deg(x_{i})=1$ for all $i\in[n(G)/2]$. Set
$X=\\{x_{2},\ldots,x_{n(G)/2}\\}$. We claim that $X$ is a nonlocal resolving
set. Let $u$ and $v$ be arbitrary non-adjacent vertices from $V(G)\setminus
X$. Then at least one of $u$ or $v$ is from $\\{y_{2},\ldots,y_{n(G)/2}\\}$,
say $u=y_{i}$, $i\geq 2$. But then $x_{i}$ resolves $u$ and $v$, and the claim
is proved.

Case 2: there is an edge $xy\in S$ such that $\deg_{G}(x)\geq 2$ and
$\deg_{G}(y)\geq 2$.
Let $x^{\prime}$ be a neighbor of $x$ different from $y$, and let $y^{\prime}$
be a neighbor of $y$ different from $x$. By the assumption on $S$, there exist
vertices $x^{\prime\prime}$ and $y^{\prime\prime}$ such that
$x^{\prime}x^{\prime\prime},y^{\prime}y^{\prime\prime}\in S$. Let $X\subset
V(G)$ be the set containing $x^{\prime}$, $y^{\prime}$, and an arbitrary
vertex from each edge $f\in
S^{\prime}=S\setminus\\{xy,x^{\prime}x^{\prime\prime},y^{\prime}y^{\prime\prime}\\}$.
We claim that $X$ is a nonlocal resolving set. Let $f=ww^{\prime}\in
S^{\prime}$, where $w^{\prime}\in X$. Then since $d_{G}(w,w^{\prime})=1$ and
since each of the vertices $x$, $y$, $x^{\prime\prime}$, and
$y^{\prime\prime}$ has either $x^{\prime}\in X$ or $y^{\prime}\in X$ as a
neighbor, we get that $X$ resolves $w$ from each of the vertices from
$\\{x,y,x^{\prime\prime},y^{\prime\prime}\\}$. Similarly we infer that the
pairs $x^{\prime\prime},y$, and $x^{\prime\prime},y^{\prime\prime}$, and
$x,y^{\prime\prime}$ are resolved by $X$. The only pairs left to be considered
are $x,x^{\prime\prime}$ and $y,y^{\prime\prime}$. Suppose on the contrary
that the pair $x,x^{\prime\prime}$ is not resolved by $X$. Since
$d_{G}(x,y^{\prime})=2$, we must have $d_{G}(x^{\prime\prime},y^{\prime})=2$.
Then $y^{\prime}x^{\prime}\in E(G)$, or $y^{\prime\prime}x^{\prime\prime}\in
E(G)$, or there is a new vertex $z$ such that
$y^{\prime}z,zx^{\prime\prime}\in E(G)$. In either case we have a cycle of
length at most $6$ in $G$ which is not possible. The other pair
$y,y^{\prime\prime}$ is treated analogously.

Let now $G$ be a tree. Let $W$ be the set of exterior branch vertices of $T$,
and for a vertex $w\in W$, let $p(w)$ be the number of terminal paths of $w$.
Then we have

$\beta^{\prime}(T)\geq\sum_{w\in W}p(w).$

On the other hand, by (2) and Proposition 2.2 we have

${\rm dim}_{\rm n\ell}(T)=\sum_{w\in W}(p(w)-1).$

Hence ${\rm dim}_{\rm n\ell}(G)=\beta^{\prime}(G)-1$ can hold only when
$|W|=1$. Suppose hence that $G$ is a tree with only one exterior branch
vertex. Then $G$ is obtained from a star $K_{1,n}$, $n\geq 3$, by subdividing
each of its edges an arbitrary number of times. By (2), ${\rm dim}_{\rm
n\ell}(G)=n-1$. Moreover, if at least one edge of $K_{1,n}$ has been
subdivided at least two times, then $\beta^{\prime}(G)\geq n+1$. Suppose next
that each edge of $K_{1,n}$ has been subdivided exactly once. Then
$\beta^{\prime}(G)=n+1$. So we are left with trees $G$ obtained from $K_{1,n}$
by subdividing all but one of the edges at most once. In this case we have
${\rm dim}_{\rm n\ell}(G)=n-1=\beta^{\prime}(G)-1$. $\square$

##  6 Embeddings

In our final result we prove that any graph can be embedded as an induced
subgraph into a supergraph with a small nonlocal metric dimension and small
diameter. More precisely, the following holds.

###### Theorem 6.1

Every connected graph $G$ is an induced subgraph of a graph $H$ with ${\rm
dim}_{\rm n\ell}(H)\leq\left\lceil\log(\chi(\overline{G}))\right\rceil$ and
${\rm diam}(H)\leq 4$. Moreover, if $2^{k-1}\leq\chi(\overline{G})<2^{k}$, for
some integer $k$, then ${\rm diam}(H)\leq 3$.

Proof. If $\chi(\overline{G})=1$, then $\overline{G}$ is an edge-less graph
and hence $G$ is complete. Then, by definition, ${\rm dim}_{\rm n\ell}(G)=0$
and hence the conclusion holds in this case by embedding the complete graph
into itself. We may thus assume in the rest that $\chi(\overline{G})=s\geq 2$.
Let $k$ be the unique integer with $2^{k-1}<s\leq 2^{k}$.

Let $X_{0},\ldots,X_{s-1}$ be the color classes of $\overline{G}$ under some
optimal coloring of it. By our assumption, $2^{k-1}<s\leq 2^{k}$. Then the
sets $X_{0},\ldots,X_{s-1}$ respectively induce complete subgraphs of $G$.
Since $G$ is connected, we may without loss of generality assume that there
exists an edge connecting a vertex from $X_{0}$ by a vertex from $X_{s-1}$.
Construct now a graph $H$ as follows. First take the disjoint union of $G$ and
$K_{k}$. For each $X_{i}$ write $i$ in its binary representation, say
$i=i_{1}\ldots i_{k}$. Then for each $j$ such that $i_{j}=0$, add all the
edges between the vertex $j\in V(K_{k})$ and $X_{i}$. See Fig. 1 for an
example of the construction where $G$ is the Petersen graph $P$. For it note
that $\chi(\overline{P})=5$.

$000$$001$$010$$011$$100$ Figure 1: Embedding the Petersen graph into a graph
$H$ as in the proof of Theorem 6.1. A thick edge means that a bottom vertex is
adjacent to both encircled vertices.

We claim that $D=V(K_{k})$ is a nonlocal resolving set of $H$. For this sake
let $u$ and $v$ be arbitrary non-adjacent vertices of $H$. If at least one of
$u$ and $v$ belongs to $D$, there is nothing to prove. Otherwise, $u\in X_{i}$
and $v\in X_{j}$, where $i\neq j$. If $i=i_{1}\ldots i_{k}$ and $j=j_{1}\ldots
j_{k}$ are the binary representations of $i$ and $j$, then there exists $p$
such that, without loss of generality, $i_{p}=0$ and $j_{p}=1$. Then
$d_{H}(p,u)=1\neq 2=d_{H}(p,v)$, hence $u$ and $v$ are resolved. This proves
the claim. Since
$|D|=k=\left\lceil\log(s)\right\rceil=\left\lceil\log(\chi(\overline{G}))\right\rceil$,
we conclude that ${\rm dim}_{\rm
n\ell}(H)\leq\left\lceil\log(\chi(\overline{G}))\right\rceil$.

To show that ${\rm diam}(H)\leq 4$, let again $u$ and $v$ be arbitrary
vertices of $H$. Note first that if $u\in V(K_{k})$, then $d_{H}(u,v)\leq 2$.
Assume hence that $u\in X_{i}$ and $v\in X_{j}$, where $i<j$. Suppose first
$j<2^{k}$. Then each of $u$ and $v$ has a neighbor in $V(K_{k})$ which implies
that $d_{H}(u,v)\leq 3$. Note that this fact in particular implies that if
$\chi(\overline{G})<2^{k}$, then ${\rm diam}(H)\leq 3$. Suppose second that
$j=2^{k}$. By our selection of $X_{0}$ and $X_{2^{k}}$, there is an edge
$v^{\prime}w$, where $v^{\prime}\in X_{2^{k}}$ and $w\in X_{0}$. As $w$ is
adjacent to all the vertices of $V(K_{k})$ and $u$ has at least one neighbor
in $V(K_{k})$, we have a $u,v$-path of length $4$. $\square$

A result for the standard metric dimension which would be parallel to Theorem
6.1 is not possible. The reason is the following. Imagine a connected, non-
complete graph $G$ and having a color class (in an optimal coloring of it) of
order $2^{r}$, $r\geq 2$. Then $G$ contains a clique of the same order and
hence in whichever graph $H$ we embed $G$ as an induced subgraph, we have
$\omega(H)\geq 2^{r}$. Then [5, Theorem 1] which asserts that if $G$ is a
graph with ${\rm diam}(G)=d$, then $f(n,d)\leq\dim(G)\leq n-d$, where $f(n,d)$
is the least positive integer $k$ for which $k+d^{k}\geq n$, implies that
$\dim(H)\geq r$. So $\dim(H)$ can be arbitrary larger than
$\left\lceil\log(\chi(\overline{G}))\right\rceil$ (actually, arbitrary larger
than $\chi(\overline{G})$ for that matter).

##  7 Concluding remarks

In this article we have introduced the concept of nonlocal metric dimension,
which seems to deserve wider interest, not least because it is in some sense a
complementary concept to the established local metric dimension. Many problems
about this new concept remain open, let us mention here just a few that follow
from our results.

In Theorem 3.2 we have proved a formula for the local metric dimension of
corona products with the second factor being not complete. Extending this
theorem (as done in [10] for the local metric dimension) to generalized
hierarchical products is open. In view of Theorem 3.3 it would be interesting
to prove a formula for ${\rm dim}_{\rm n\ell}(G\odot K_{n})$. Theorem 5.3 is
proved for graphs of girth at least $7$. We suspect that the condition can be
relaxed to girth at least $5$. Moreover, the edge cover number in triangle-
free graphs (that is, of girth at least $4$) is equal to the clique cover
number. Hence extending Theorem 5.3 to arbitrary graphs, where the upper bound
would be stated as a function of the clique covering number would be of
interest.

## Acknowledgements

We would like to express our sincere thanks to the reviewers for their very
careful reading of the paper.

Sandi Klavžar acknowledges the financial support from the Slovenian Research
Agency through research core funding No. P1-0297 and projects J1-2452 and
N1-0285. Dorota Kuziak was partially supported by the Spanish Ministry of
Science and Innovation through the grant PID2019-105824GB-I00. and by “Plan
Propio de Investigación-UCA” ref. no. EST2022-075.

## References

  * [1] G. Abrishami, M.A. Henning, M. Tavakoli, Local metric dimension for graphs with small clique numbers, Discrete Math. 345 (2022) 112763.
  * [2] G.A. Barragán-Ramírez, A. Estrada-Moreno, Y. Ramírez-Cruz, J.A. Rodríguez-Velázquez, The local metric dimension of the lexicographic product of graphs, Bull. Malays. Math. Sci. Soc. 42 (2019) 2481–2496.
  * [3] G.A. Barragán-Ramírez, J.A. Rodríguez-Velázquez, The local metric dimension of strong product graphs, Graphs Combin. 32 (2016) 1263–1278.
  * [4] P. S. Buczkowski, G. Chartrand, C. Poisson, P. Zhang, On $k$-dimensional graphs and their bases, Period. Math. Hungar. 46 (2003) 9–15.
  * [5] G. Chartrand, L. Eroh, M.A. Johnson, O.R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105 (2000) 99–113.
  * [6] V.F. Fancy, V.J.A. Cynthia, Local metric dimension of families of certain graphs, J. Comb. Inf. Syst. Sci. 42(4) (2017) 179–186.
  * [7] F. Harary, R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976) 191–195.
  * [8] S. Hoffmann, A. Elterman, E. Wanke, A linear time algorithm for metric dimension of cactus block graphs, Theoret. Comput. Sci. 630 (2016) 43–62.
  * [9] H. Iswadi, E.T. Baskoro, R. Simanjuntak, On the metric dimension of corona product of graphs, Far East J. Math. Sci. 52 (2011) 155–170.
  * [10] S. Klavžar, M. Tavakoli, Local metric dimension of graphs: generalized hierarchical products and some applications, Appl. Math. Comput. 364 (2020) 124676.
  * [11] D. Kuziak, I.G. Yero, Metric dimension related parameters in graphs: A survey on combinatorial, computational and applied results, arXiv:2107.04877 [math.CO] (10 Jul 2021).
  * [12] F. Okamoto, B. Phinezy, P. Zhang, The local metric dimension of a graph, Math. Bohem. 135 (2010) 239–255.
  * [13] J.A. Rodríguez-Velázquez, G.A. Barragán-Ramírez, C. García Gómez, On the local metric dimension of corona product graphs, Bull. Malays. Math. Sci. Soc. 39 (2016) S157–S173.
  * [14] J. A. Rodríguez-Velázquez, C. García Gómez, G. A. Barragán-Ramírez, Computing the local metric dimension of a graph from the local metric dimension of primary subgraphs, Int. J. Comput. Math. 92 (2015) 686–693.
  * [15] P. J. Slater, Leaves of trees, Congr. Numer. 14 (1975) 549–559.
  * [16] B. Shanmukha, B. Sooryanarayana, K. Harinath, Metric dimension of wheels, Far East J. Math. Sci. 8 (2002) 217–229.
  * [17] L. Susilowati, I.M. Slamin, N. Estuningsih, The similarity of metric dimension and local metric dimension of rooted product graph, Far East J. Math. Sci. 97 (2015) 841–856.
  * [18] R.C. Tillquist, R.M. Frongillo, M.E. Lladser, Getting the lay of the land in discrete space: A survey of metric dimension and its applications, arXiv:2104.07201 [math.CO] (15 Apr 2021).
  * [19] D.B. West, Introduction to Graph Theory, 2nd ed., Prentice-Hall, NJ, 2001.
  * [20] I.G. Yero, D. Kuziak, J.A. Rodríguez-Velázquez, On the metric dimension of corona product graphs, Comput. Math. Appl. 61 (2011) 2793–2798.