# Hardwiring ViT Patch Selectivity into CNNs using Patch Mixing

Ariel Lee
Boston University
<EMAIL_ADDRESS>
&Sarah Adel Bargal
Georgetown University
<EMAIL_ADDRESS>
&Janavi Kasera
Boston University
<EMAIL_ADDRESS>
&Stan Sclaroff
Boston University
<EMAIL_ADDRESS>
&Kate Saenko
FAIR
Boston University
<EMAIL_ADDRESS>
&Nataniel Ruiz
Boston University
<EMAIL_ADDRESS>

###### Abstract

Vision transformers (ViTs) have significantly changed the computer vision
landscape and have periodically exhibited superior performance in vision tasks
compared to convolutional neural networks (CNNs). Although the jury is still
out on which model type is superior, each has unique inductive biases that
shape their learning and generalization performance. For example, ViTs have
interesting properties with respect to early layer non-local feature
dependence, as well as self-attention mechanisms which enhance learning
flexibility, enabling them to ignore out-of-context image information more
effectively. We hypothesize that this power to ignore out-of-context
information (which we name patch selectivity), while integrating in-context
information in a non-local manner in early layers, allows ViTs to more easily
handle occlusion. In this study, our aim is to see whether we can have CNNs
simulate this ability of patch selectivity by effectively hardwiring this
inductive bias using Patch Mixing data augmentation, which consists of
inserting patches from another image onto a training image and interpolating
labels between the two image classes. Specifically, we use Patch Mixing to
train state-of-the-art ViTs and CNNs, assessing its impact on their ability to
ignore out-of-context patches and handle natural occlusions. We find that ViTs
do not improve nor degrade when trained using Patch Mixing, but CNNs acquire
new capabilities to ignore out-of-context information and improve on occlusion
benchmarks, leaving us to conclude that this training method is a way of
simulating in CNNs the abilities that ViTs already possess. We will release
our Patch Mixing implementation and proposed datasets for public use. Project
page: https://arielnlee.github.io/PatchMixing/

##  1 Introduction

Convolutional neural networks (CNNs) and Vision Transformers (ViTs) are two
dominant deep learning models for computer vision tasks. Although CNNs have
established themselves as the go-to approach for many years, the introduction
of ViTs has significantly changed the landscape and they have consistently
achieved comparable or superior performance compared to CNNs for key computer
vision tasks such as object recognition, object detection, semantic
segmentation, and many others.

In recent years, a relatively robust literature has developed comparing CNNs
and Vision Transformers in terms of overall performance on standard
benchmarks, robustness to OOD inputs, robustness to adversarial attacks, and
other evaluations [18, 30, 2, 19, 1, 25, 17, 23], as well as analysis work
that compares the way both architecture types understand images and how they
ultimately arrive at their predictions [25, 23, 20, 22].

We note that one important research topic remains under-explored: how these
architectures handle occlusion. There exists work that compare both
architectures using simple simulations of occlusion such as patch dropping
[20], or occlusion in a simulated environment [25]. Additionally, in work by
Pinto et al. [22], they found no clear winner between modern CNNs and ViTs for
different robustness tests. In this work, we dive deeply into this specific
area and present four main contributions:

  * •

We find a previously undiscovered incontrovertible difference in performance
between modern ViTs and CNNs. ViTs are naturally more robust when out-of-
context information is added to an image compared to CNNs. We call this
ability to ignore out-of-context patches: patch selectivity.

  * •

We revisit Patch Mixing, a data augmentation method where patches from other
images are introduced into training images and ground-truth labels are
interpolated. We show that by training CNNs using Patch Mixing, we simulate
the natural ability of ViTs to ignore out-of-context information.

  * •

We show that models with better patch selectivity tend to be more robust to
natural occlusion. Specifically, we introduce two new challenging datasets to
evaluate performance of image classifiers under occlusion: the Superimposed
Masked Dataset (SMD) and the Realistic Occlusion Dataset (ROD). Moreover, our
CNN models trained using Patch Mixing become more robust to occlusion in
these, and other datasets.

  * •

We propose a new explainability method, c-RISE \- a contrastive version of the
RISE [21] explainability method that allows for agnostic analysis of input
sensibility under occlusion for both CNNs and Transformers. Using c-RISE we
are able to measure patch selectivity and show that augmentation using Patch
Mixing improves CNN patch selectivity.

Figure 1: Patch Mixing augmentation with label smoothing improves the ability
of CNNs to handle a multitude of alterations and occlusions, bridging the gap
with ViTs.

##  2 Deep Dive Into Patch Selectivity

#### Modern CNN and ViT Inductive Biases

Convolutional neural networks (CNNs) are traditionally composed of a series of
trainable convolutional layers. Modern CNN architectures such as ConvNeXt [17]
differ in many respects, yet still follow a purely convolutional approach. A
particularly important change is the use of a patchify stem - this change can
both increase the overall receptive field in early layers in modern convnets
as opposed to traditional convnets, as well as decrease strong local
dependencies that are created in the early layers of the network, since the
patches are non-overlapping. Nevertheless, this, and other changes, do not
completely change the inductive bias of the architecture: the network remains
a purely convolutional network that uses square conv filters, has a propensity
to more strongly weight proximal evidence, and has relatively small effective
receptive fields in early layers.

The Vision Transformer (ViT) [6] is a neural network architecture for image
recognition that uses self-attention based Transformer layers. An image is
first divided into non-overlapping patches, that are then transformed into
embeddings. These embeddings are used as inputs for the Transformer layers.
ViTs possess distinct properties and inductive biases when compared to CNNs,
some of which are particularly important to highlight.

#### ViT Early Layer Long-Range Dependence

In CNNs the receptive field at a specific layer is fully determined by the
size of the convolution kernel and the stride of that layer, as well as the
layers that precede the layer of interest. For this reason, given limits on
the convolutional kernel size and the stride of the kernel, the receptive
field for early CNN layers does not encompass the full image input. In
contrast, early layers of ViTs have a large receptive field because they use
self-attention, which allows them to attend to any part of the input image
beginning at the first layer of the architecture. As a result, ViTs can learn
relationships between pixels that are far apart in the input image [23], while
CNNs are limited to learning relationships between proximal pixels. In this
way, ViTs have the property of early-layer long-range dependency that is not
possible to structurally mimic in CNNs, even with modernized CNN architectures
that include patchify stems. In this work we pose the following:

######  Hypothesis 1.

Hierarchical attention in ViT-style networks allows them to more easily
discount signal from out-of-context information in an image when compared to
CNNs, which, due to their structure and inherent inductive biases, have a
harder time discounting signal from out-of-context patches.

Specifically, in this work we evaluate this hypothesis using empirical means.
This hypothesis has been discussed in the prominent work of Naseer et al. [20]
that compares ViT and CNN performance when faced with occlusion. They study
occlusion by simulating it using either random or saliency-guided patch
dropping in images. In particular, the main conclusion is that ViTs were
vastly better at dealing with out-of-context patches. Nevertheless, this study
focused on older convnet architectures such as ResNet50, DenseNet121 and
VGG19. Modern convnets such as ConvNeXt, proposed in the influential work of
Liu et al. [17], possess very different architectures while remaining fully-
convolutional. There is a relative scarcity of study of these new
architectures with respect to occlusion, although recent work [25] proposes to
study occlusion for Swin Transformers and ConvNeXt CNNs. Interestingly, they
find that new innovations in architecture and training regime makes these new
convnets much stronger than older convnets such as ResNet50 at ignoring
dropped patches, yet still lagging behind ViTs at higher levels of information
loss.

One important issue to raise, is that patch drop is a poor approximation of
real world occlusion, where occluders are usually other objects that have
their own shape and texture, which adds another dimension to the problem. The
question then remains: Are ViTs truly better at handling occlusion and
discounting signal from out-of-context patches than CNNs?

We find that the answer is a resounding yes. Specifically, when comparing ViTs
and modern convnets that have identical parameter count, FLOPs and very close
ImageNet validation performance, ViTs degrade much less when out-of-context
patches are introduced into an image. In Figure 2, we show the accuracy of
comparable ConvNeXt and Swin models when out-of-context patches are introduced
into test images. We see a much larger decrease in accuracy in ConvNeXt
compared to Swin, with a widening gap as information loss increases. This
finding is particularly interesting in the context of recent work by Pinto et
al. [22], which finds no clear winner in a contest between ConvNeXt and Swin
models of different sizes for different robustness tests such as simplicity
bias, background bias, texture bias, OOD detection and other tasks. To the
best of our knowledge we are the first to find an incontrovertible difference
between these two classes of models that stands out.

Figure 2: ConvNeXt performance severely decreases as more out-of-context
patches are inserted into test images, with Swin proving to be more resilient
to this type of occlusion.

This experiment is a rough approximation of natural occlusions, where objects
or surfaces occlude the main object in an image. We do, however, hypothesize
that networks that can more easily discount signal from out-of-context patches
will tend to perform better under naturalistic occlusion:

######  Hypothesis 2.

A model with better patch selectivity will tend to perform better under
naturalistic occlusion.

In order to test this, we first evaluate the patch selectivity of our trained
models, and then extensively test them on four different benchmarks, including
two datasets that we propose as contributions: the Superimposed Masked Dataset
(SMD) and the Realistic Occlusion Dataset (ROD) which will be described
further below. We find that there is indeed a positive correlation between
patch selectivity and performance under occlusion, and supply the details in
the Experiments section.

Finally, we pose the following final hypothesis:

######  Hypothesis 3.

A model that is explicitly trained to deal with out-of-context patches using
data augmentation will tend to improve at ignoring out-of-context information
at test-time.

In our experiments we evaluate this hypothesis and show that using Patch
Mixing at training time improves CNN patch selectivity, but, surprisingly,
does not improve ViT patch selectivity. We believe this is due to the fact
that patch selectivity is already a natural capability of ViTs, whereas CNNs
have lesser patch selectivity and attention bleeds out from in-context patches
to neighbouring out-of-context patches. By combining verified Hypotheses 2 and
3, we can conclude that CNNs trained using Patch Mixing are more robust to
natural occlusions in the real world. We indeed confirm this experimentally.

###  2.1 Augmentation by Patch Mixing

Previous work has introduced the notion of inserting parts of different images
into training images in different manners. CutMix [33] proposes to cut and
paste one contiguous rectangle from another image into a training image, and
mix the ground truth labels proportionally to the area of each image.
Cascante-Bonilla et al. [3] propose random and evolutionary search-guided
replacement of training image square patches with patches from another
training image, also mixing ground truth labels in proportional fashion. [32]
proposes replacing rectangular patches in an image, with patches from many
other training images, in order to augment small datasets in few-shot
learning.

Our proposed augmentation is named Patch Mixing. Let $x\in\mathbb{R}^{H\times
W\times C}$ and $y$ denote the image and its label respectively. We seek to
generate an image/label pair $(\tilde{x},\tilde{y})_{i}$ by mixing patches
from images $x_{A}$ and $x_{B}$ while appropriately mixing labels $y_{A}$ and
$y_{B}$. For this we generate a mask composed of patches
$M\in\\{0,1\\}^{N\times P^{2}\times C}$, where $(H,W)$ is the resolution of
the original image, $C$ is the number of channels, $(P,P)$ is the resolution
of each image patch, and $N=\frac{HW}{P^{2}}$ is the resulting number of
patches. We initialize the elements of this mask to $0$. We then select
$N_{1}$ patches from this mask, following uniform random sampling and set the
elements of those patches to $1$. These are the patches that will be replaced
in image $x_{A}$. We select $N_{1}$ based on a proportion hyperparameter
$r=N_{1}/N$ which represents the proportion of patches that are replaced.
Finally, we generate $\tilde{x}$:

$\tilde{x}=(1-M)\odot x_{A}+M\odot x_{B}.$ (1)

Labels $y_{A}$ and $y_{B}$ are mixed to generate label $\tilde{y}$, using the
proportion $r$. The resulting vector is smoothed using label smoothing [27].

Our proposed Patch Mixing most resembles one method mentioned in [3], with
some important differences in both application scenario and implementation.
For the application scenario, their work does not study the effects of Patch
Mixing on Transformers, doing so only on CNNs. Moreover, they solely study
ResNet and MobileNet architectures, and the method was not applied to modern
convnets given the concurrency of [17] and their work. Finally, most
evaluations in their work are based on the CIFAR-10 dataset [16], while we
evaluate improved networks on four datasets that present different types of
occlusion simulations and real-world occlusions.

Our Patch Mixing implementation has important differences with [3]. First, we
find that in order to recover the strong performance exhibited by modern CNNs
on ImageNet it is imperative to disable random erasing when using patch
mixing. When both are used simultaneously, information loss is too high,
resulting in lower overall performance. Next, our version uses label smoothing
[27] which increases performance. We also find that using a more granular grid
for patch replacement improves results for modern CNNs - thus we use a 7x7
grid instead of a 4x4 grid. Their work focuses on a guided version of mixing
patches using evolutionary search. We find that random patch mixing is less
computationally expensive and suffices to evaluate the hypotheses of this
work.

###  2.2 Contrastive RISE (c-RISE) and Patch Selectivity

Petsiuk et al. [21] proposed Randomized Input Sampling for Explanation of
Black-box Models (RISE), a method that generates an image heatmap that
highlights the importance of pixel evidence in that image for a specific
prediction $y_{\text{pred}}$. This method is a perfect fit for our problem
since it is an empirical method that is model agnostic and can be applied to
both modern CNNs and ViTs. Specifically, it uses iterative random masking of
an image using Monte Carlo sampling, and evaluates the predictions of the
model on the masked images to generate an importance map. Unfortunately, RISE
is not a contrastive method that generates evidence maps for a specific class,
and only that class. This is a direly needed property for us, since occluders
can be in the label space of the model, which can cause them to be highlighted
as non-specific evidence using traditional RISE. We propose a grey-box
modification of RISE called contrastive RISE (c-RISE), where the Monte Carlo
equation becomes:

$S_{x,f}(\lambda)\overset{\mathrm{MC}}{\approx}\frac{1}{\mathbb{E}[B]\cdot
N_{B}}\sum_{i=1}^{N_{B}}[f(x\odot B_{i})-f^{\prime}(x\odot B_{i})]\cdot
B_{i}(\lambda).$ (2)

Where $B_{i}$ is the sample binary mask, and $f^{\prime}$ is the classifier
$f$ with the weights of the last fc layer flipped (multiplied by $-1$)
following the trick proposed in [35]. For more information on c-RISE please
refer to the supplementary material.

Finally, we present an empirical approximation of patch selectivity using
c-RISE, which corresponds to the contrastive importance of in-context areas of
the image. Simply, we sum the parts of the c-RISE importance heatmap that
overlap with image patches that are from the original image (and not from the
occluder image):

$\mathcal{P}_{f}(x)=\frac{1}{N}\sum S_{x,f}\odot(1-M).$ (3)

##  3 Datasets

#### Realistic Occlusion Dataset (ROD)

The Realistic Occlusion Dataset is the product of a meticulous object
collection protocol aimed at collecting and capturing 40+ distinct objects
from 16 classes: banana, baseball, cowboy hat, cup, dumbbell, hammer, laptop,
microwave, mouse, orange, pillow, plate, screwdriver, skillet, spatula, and
vase. Images are taken in a bright room with soft, natural light. All objects
are captured on a brown wooden table against a solid colored wall. An iPhone
13 Pro ultra-wide camera with a tripod is used to capture images at an
elevation of approximately 90∘ and distance of 1 meter from the object.
Occluder objects are wooden blocks or square pieces of cardboard, painted red
or blue. The occluder object is added between the camera and the main object
and its x-axis position is varied such that it begins at the left of the frame
and ends at the right. In total, 1 clean image and 12 occluded images are
captured for each object. Each object is measured and the occluder step size
is broken up into equal sizes.

#### Superimposed Masked Dataset (SMD)

We generate three versions of SMD, an occluded ImageNet-1K validation set, as
an additional way to evaluate the impact of occlusion on model performance.
This experiment used a variety of occluder objects that are not in the
ImageNet-1K label space and are unambiguous in relationship to objects that
reside in the label space. Two occluder objects for each of the following
classes were segmented using Meta’s Segment Anything [12]: airpods, virtual
reality headset, drone, graduation cap, anatomical heart, origami heart,
skateboard, diamonds (stones, not in a setting), Grogu (baby yoda), person,
popcorn, coronavirus, bacteriophage, and bacteria. Figure 3 shows examples of
images from the SMD datasets with varying levels of occlusion.

Figure 3: Random examples from our proposed challenging occlusion datasets:
SMD (left 3 images) and ROD (right 3 images) datasets.

##  4 Experiments

#### Models and Training

The Patch Mixing models are trained from scratch using the original training
scripts. The only hyperparameter change made is the removal of random erasing.
When augmenting, we set an equal probability of using Mixup, CutMix, or Patch
Mixing. For each batch of images, the patching ratio is randomly sampled from
a beta distribution. If not specified, experiments are conducted on the
ImageNet validation set. Tiny networks were trained on 4 RTX8000 and Small
networks on 4 A6000.

###  4.1 Patch Selectivity

#### ViTs have better patch selectivity than CNNs

To test a model’s ability to ignore out-of-context patches, we run patch
mixing experiments on ImageNet-1K val and report the Top-1 accuracy as a
function of information loss in Figures 4. Note that no label smoothing is
applied for attacked images and the information loss degree is deterministic.
We present different experiments using different number of image patches. We
observe that Original Swin models vastly outperform Original ConvNeXt models
as information loss increases. Specifically, this shows that Swin can
naturally ignore out-of-context patches better than ConvNeXt.

#### Using Patch Mixing augmentation, CNNs have similar patch selectivity to
ViTs

By examining Figures 4, we can see that using patch mixing augmentation
ConvNeXt equals the performance of original Swin with respect to patch
replacement attacks, gaining the ability of patch selectivity that ViTs
inherently have. To add further evidence to this, Swin networks do not improve
much on average using patch mixing, which suggests that we are supplying an
inductive bias that is already present in the architecture.

Figure 4: Patch Mixing experiments on tiny and small networks on ImageNet-1K
val. ViTs natively have better patch selectivity than CNNs, yet when we use
Patch Mixing augmentation, CNNs have similar patch selectivity to ViTs.

###  4.2 Spatial structure invariance

#### Patch Mixing bestows better spatial structure invariance to CNNs

The fundamental architecture of ViTs offers inherent, "out-of-the-box"
permutation invariance. We re-implement the patch permutation experiments
conducted in [20] and find that, surprisingly, Patch Mixing reduces modern
CNNs reliance on spatial structure, resulting in context-independence and
robustness to permutations on par with ViT models. In Figure 5 we see that the
performance gap between original and Patch Mixing trained ConvNeXt models
increases with the shuffle grid size. Conversely, the performance gap between
ConvNeXt-T trained with Patch Mixing and the original Swin-T network remains
small even as the shuffle grid size increases. The accuracy of ConvNeXt-S
patch is nearly identical to the original Swin-S network. Interestingly, this
is the only experiment where Swin trained with Patch Mixing shows a consistent
improvement over its original counterpart.

(a)

(b)

(c) 2x2 grid

(d) 4x4 grid

Figure 5: Better patch selectivity means greater resistance to abnormal
spatial structure: Top-1 accuracy on IN-1k val set is plotted against shuffle
grid size for the patch permutation experiments on Tiny (a) and Small (b)
networks. Examples of patch permutations can be seen in (c) and (d).

###  4.3 Robustness to occlusion

#### Patch Mixing improves robustness to occlusion for CNNs but not for ViTs

Table 1 presents a summary of the results for different network architectures
tested on three datasets: ImageNet-1K val (IN) top-1, SMD top-1 (avg. over
10-30% occlusion), NVD [25] simulated occlusion validation top-5, and ROD
top-5. The ConvNeXt and Swin networks are compared in their standard and Patch
versions, both in Tiny (T) and Small (S) configurations. In the Tiny category,
ConvNeXt-T and ConvNeXt-T Patch Mixing both achieved an IN top-1 score of
82.1%, but the Patch Mixing version performed better in the NVD occlusion set
(26.1% vs. 25.4%), SMD (48.9% vs. 47.6%), and ROD (42.6% vs. 40.4%). For the
Swin-T versions, the Patch Mixing model showed minor improvements over the
original in the IN and NVD occlusion datasets but slightly under-performed on
ROD. The trend is mirrored for Small models.

Overall, the table suggests that the Patch variants of CNNs generally showed
improved performance on occluded datasets compared to their original
counterparts, whereas ViTs do not substantially improve.

Table 1: Mean accuracy results for IN, ROD, SMD, and NVD test sets (%).

Architecture | IN | SMD | NVD | ROD
---|---|---|---|---
ConvNeXt-T Original | 82.1 | 47.6 | 25.4 | 40.4
ConvNeXt-T Patch Mixing | 82.1 |  48.9 |  26.1 |  42.6
ConvNeXt-S Original | 83.1 | 49.4 | 21.9 | 48.4
ConvNeXt-S Patch Mixing |  83.2 |  50.1 |  25.8 | 48.4
Swin-T Original | 81.2 | 56.5 | 18.4 |  41.9
Swin-T Patch Mixing |  81.3 |  57.2 |  18.9 | 40.2
Swin-S Original |  83.2 |  60.4 |  20.5 | 44.3
Swin-S Patch Mixing | 82.9 | 60.2 | 18.2 |  48.2

#### Random Patch Drop

Figure 6 illustrates that for tiny and small networks with grid size (14, 14)
ConvNeXt trained with Patch Mixing outperforms its counterpart, and in some
cases achieves the best result with increasing information loss. We also see
that Swin performance either stays static or slightly increases, but not by
the same magnitude as ConvNeXt performance.

Figure 6: Random patch drop: Tiny and Small networks

#### c-RISE

We obtain c-RISE maps from images that are attacked using patch mixing for
both original and improved ConvNeXt and Swin models. We normalize the
importance map using a Softmax function and calculate the inverse of our
defined patch selectivity metric in Equation 3 by summing the importance
values in out-of-context patches. To obtain granular heatmaps we increase the
number of RISE masks to 14,000 and use a stride of 14.

#### CNNs trained with Patch Mixing exhibit increased patch selectivity,
rivaling that of ViTs

We show the quantitative results of inverse patch selectivity in Table 2 for
Tiny networks using grid sizes of (7, 7) and (14, 14). We also illustrate the
differences between the models’ heatmap appearances in Figure 7. Specifically,
we can see how ConvNeXt Original’s importance map spills from in-context to
out-of-context patches due to the convolutional architecture, a phenomenon
that is addressed in ConvNeXt w/ Patch Mixing. ConvNeXt Patch Mixing and Swin
Original both correctly classify the airplane carrier in Figure 7, but
ConvNeXt original incorrectly classifies the image as carousel. This shows
that ConvNeXt Patch Mixing more effectively ignores occluders that are out-of-
context in general, with importance maps that mirror those of Swin.

Table 2: Inverse patch selectivity (lower is better) using c-RISE and patch attack grid sizes of (7, 7) and (14, 14). We evaluate 5 images per class for 100 classes using Softmax normalized saliency maps. Model | Inverse Patch Selectivity
---|---
| (7, 7) | (14, 14)
ConvNeXt-T Original | 0.0201 | 0.0198
ConvNeXt-T Patch Mixing | 0.0194 | 0.0196
Swin-T Original | 0.0196 | 0.0197
Swin-T Patch Mixing | 0.0197 | 0.0198
Figure 7: Saliency maps of spider monkey (top) and airplane carrier (bottom).
ConvNeXt w/ Patch Mixing shows a strongly improved ability to ignore out-of-
context patches.

##  5 Related Work

#### Data Augmentation

There are many data augmentations that attempt to address the issue of
occlusion, from stochastic elimination of regions within training images to
regional dropout [37, 5, 31]. To effectively address the limitations of
traditional empirical risk minimization approaches in training deep neural
networks, Zhang et al. [34] introduced Mixup. A now widely utilized data
augmentation technique, Mixup synthesizes new training instances by linearly
interpolating between random image pairs and their respective labels. This
approach encourages the model to produce smoother decision boundaries, leading
to better generalization. As noted by Yun et al. [33], Mixup samples are
locally ambiguous and unnatural, often confusing the model. To address this,
Yun et al. presented CutMix, a regularization strategy for training robust
classifiers with localizable features. CutMix combines the benefits of
previous data augmentation techniques, such as Mixup and Cutout [5], by
overlaying patches of one image onto another and adjusting the corresponding
labels proportionally.

#### Occlusion

Current related works on occlusion in object detection and image
classification indicate that while systems have evolved to be more robust,
they still fail to accurately classify and detect objects under severe
occlusion. Existing approaches like Region Proposal Networks [8], which are
applied for learning fast detection approaches [9], perform well for object
detection tasks but fail when the bounding box of an object is occluded.
Recent works have shown that traditional approaches like Deep Convolutional
Neural Networks (DCNNs) such as ResNet [10] or VGG [26] display little
robustness to occlusion [38, 15]. Addressing this issue with data
augmentations simulating partial occlusion has had limited success [5].
Conversely, generative compositional models have been shown to be robust to
partial object occlusion with the ability to still detect object features [11,
7, 4, 29]. Recently, CompositionalNets, which incorporate DCNN architecture,
have been proven to be far more robust to occlusion than their traditional
counterparts [14, 13]. Building off this work, context-aware CompositionalNets
were introduced to control the influence of the object’s context on the
classification result, increasing accuracy when confronted with largely
occluded objects [28]. Other deep learning approaches require detailed part-
level annotations to reconstruct occluded objects, which is costly [36, 24].

##  6 Conclusion

In this paper, we investigated the difference between CNNs and ViTs in terms
of their ability to handle occlusion and ignore out-of-context information. In
particular, we introduced the concept of patch selectivity as a measure of
this ability and showed that ViTs naturally possess higher patch selectivity
than CNNs. We also proposed Patch Mixing, a data augmentation method that
simulates patch selectivity in CNNs by inserting patches from other images
onto training images. We demonstrated that Patch Mixing improves the
performance of CNNs on various occlusion benchmarks, including two new
datasets that we created: SMD and ROD. Furthermore, we developed c-RISE, a
contrastive explainability method that allows us to visualize and quantify
patch selectivity for both CNNs and ViTs. Our results suggest that patch
selectivity is an important element for occlusion robustness and Patch Mixing
is an effective method to amplify this characteristic within CNNs, bridging
the gap with respect to ViTs that are naturally stronger in this area.

## References

  * [1] Y. Bai, J. Mei, A. L. Yuille, and C. Xie.  Are transformers more robust than cnns?  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 26831–26843. Curran Associates, Inc., 2021.
  * [2] A. Borji.  Cnns and transformers perceive hybrid images similar to humans.  arXiv preprint arXiv:2203.11678, 2022.
  * [3] P. Cascante-Bonilla, A. Sekhon, Y. Qi, and V. Ordonez.  Evolving image compositions for feature representation learning.  arXiv preprint arXiv:2106.09011, 2021.
  * [4] J. Dai, Y. Hong, W. Hu, S.-C. Zhu, and Y. Wu.  Unsupervised learning of dictionaries of hierarchical compositional models.  Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 2505–2512, 09 2014.
  * [5] T. Devries and G. W. Taylor.  Improved regularization of convolutional neural networks with cutout.  CoRR, abs/1708.04552, 2017.
  * [6] A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  In International Conference on Learning Representations, 2020.
  * [7] S. Fidler, M. Boben, and A. Leonardis.  Learning a hierarchical compositional shape vocabulary for multi-class object representation.  CoRR, abs/1408.5516, 2014.
  * [8] R. Girshick, J. Donahue, T. Darrell, and J. Malik.  Rich feature hierarchies for accurate object detection and semantic segmentation.  Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 11 2013.
  * [9] R. B. Girshick.  Fast R-CNN.  CoRR, abs/1504.08083, 2015.
  * [10] K. He, X. Zhang, S. Ren, and J. Sun.  Deep residual learning for image recognition.  In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 770–778, 2016.
  * [11] Y. Jin and S. Geman.  Context and hierarchy in a probabilistic image model.  In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, volume 2, pages 2145 – 2152, 02 2006\.
  * [12] A. Kirillov, E. Mintun, N. Ravi, H. Mao, C. Rolland, L. Gustafson, T. Xiao, S. Whitehead, A. C. Berg, W.-Y. Lo, P. Dollár, and R. Girshick.  Segment anything, 2023.
  * [13] A. Kortylewski, C. Blumer, and T. Vetter.  Greedy compositional clustering for unsupervised learning of hierarchical compositional models.  CoRR, abs/1701.06171, 2017.
  * [14] A. Kortylewski, J. He, Q. Liu, and A. L. Yuille.  Compositional convolutional neural networks: A deep architecture with innate robustness to partial occlusion.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
  * [15] A. Kortylewski, Q. Liu, H. Wang, Z. Zhang, and A. L. Yuille.  Compositional convolutional networks for robust object classification under occlusion.  CoRR, abs/1905.11826, 2019.
  * [16] A. Krizhevsky, V. Nair, and G. Hinton.  The cifar-10 dataset.  online: http://www. cs. toronto. edu/kriz/cifar. html, 55(5), 2014\.
  * [17] Z. Liu, H. Mao, C.-Y. Wu, C. Feichtenhofer, T. Darrell, and S. Xie.  A convnet for the 2020s.  Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2022.
  * [18] K. Mahmood, R. Mahmood, and M. van Dijk.  On the robustness of vision transformers to adversarial examples.  In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pages 7838–7847, October 2021.
  * [19] C. Matsoukas, J. F. Haslum, M. Söderberg, and K. Smith.  Is it time to replace cnns with transformers for medical images?  arXiv preprint arXiv:2108.09038, 2021.
  * [20] M. M. Naseer, K. Ranasinghe, S. H. Khan, M. Hayat, F. Shahbaz Khan, and M.-H. Yang.  Intriguing properties of vision transformers.  Advances in Neural Information Processing Systems, 34, 2021.
  * [21] V. Petsiuk, A. Das, and K. Saenko.  Rise: Randomized input sampling for explanation of black-box models.  In Proceedings of the British Machine Vision Conference (BMVC), 2018\.
  * [22] F. Pinto, P. H. Torr, and P. K. Dokania.  An impartial take to the cnn vs transformer robustness contest.  In Computer Vision–ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23–27, 2022, Proceedings, Part XIII, pages 466–480. Springer, 2022.
  * [23] M. Raghu, T. Unterthiner, S. Kornblith, C. Zhang, and A. Dosovitskiy.  Do vision transformers see like convolutional neural networks?  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 12116–12128. Curran Associates, Inc., 2021.
  * [24] N. D. Reddy, M. Vo, and S. G. Narasimhan.  Occlusion-net: 2d/3d occluded keypoint localization using graph networks.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 7326–7335, 2019.
  * [25] N. Ruiz, S. Bargal, C. Xie, K. Saenko, and S. Sclaroff.  Finding differences between transformers and convnets using counterfactual simulation testing.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 14403–14418. Curran Associates, Inc., 2022.
  * [26] K. Simonyan and A. Zisserman.  Very deep convolutional networks for large-scale image recognition.  In International Conference on Learning Representations, 2015.
  * [27] C. Szegedy, V. Vanhoucke, S. Ioffe, J. Shlens, and Z. Wojna.  Rethinking the inception architecture for computer vision.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2818–2826, 2016.
  * [28] A. Wang, Y. Sun, A. Kortylewski, and A. L. Yuille.  Robust object detection under occlusion with context-aware compositionalnets.  CoRR, abs/2005.11643, 2020.
  * [29] J. Wang, C. Xie, Z. Zhang, J. Zhu, L. Xie, and A. L. Yuille.  Detecting semantic parts on partially occluded objects.  CoRR, abs/1707.07819, 2017.
  * [30] Z. Wang, Y. Bai, Y. Zhou, and C. Xie.  Can cnns be more robust than transformers?  arXiv preprint arXiv:2206.03452, 2022.
  * [31] M. Xiao, A. Kortylewski, R. Wu, S. Qiao, W. Shen, and A. L. Yuille.  Tdapnet: Prototype network with recurrent top-down attention for robust object classification under partial occlusion.  CoRR, abs/1909.03879, 2019.
  * [32] C. Xu, C. Liu, X. Sun, S. Yang, Y. Wang, C. Wang, and Y. Fu.  Patchmix augmentation to identify causal features in few-shot learning.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022\.
  * [33] S. Yun, D. Han, S. J. Oh, S. Chun, J. Choe, and Y. Yoo.  Cutmix: Regularization strategy to train strong classifiers with localizable features.  In Proceedings of the IEEE/CVF international conference on computer vision, pages 6023–6032, 2019.
  * [34] H. Zhang, M. Cisse, Y. N. Dauphin, and D. Lopez-Paz.  mixup: Beyond empirical risk minimization.  arXiv preprint arXiv:1710.09412, 2017.
  * [35] J. Zhang, S. A. Bargal, Z. Lin, J. Brandt, X. Shen, and S. Sclaroff.  Top-down neural attention by excitation backprop.  International Journal of Computer Vision, 126(10):1084–1102, 2018\.
  * [36] S. Zhang, L. Wen, X. Bian, Z. Lei, and S. Z. Li.  Occlusion-aware R-CNN: detecting pedestrians in a crowd.  CoRR, abs/1807.08407, 2018.
  * [37] Z. Zhong, L. Zheng, G. Kang, S. Li, and Y. Yang.  Random erasing data augmentation.  CoRR, abs/1708.04896, 2017.
  * [38] H. Zhu, P. Tang, and A. L. Yuille.  Robustness of object recognition under extreme occlusion in humans and computational models.  CoRR, abs/1905.04598, 2019.

## Supplementary Material

## Superimposed Masked Dataset (SMD) Details

Here we present additional details and experimental results regarding SMD,
which is introduced in Section 3 of the main paper. Figure 8 provides
additional images from SMD, and Figure 9 shows one example of each occluder
for each class.

Occluder objects are randomly selected and rotated prior to being applied to
the validation images. So as not to completely occlude important image
features, we place multiple instances of the same occluder object on each
image. Pertinent information, including occluder masks, classes, and
percentage of occlusion, is saved for future use. For lower levels of
occlusion, the occluders do not overlap. For images with higher levels of
occlusion, overlapping occluders are taken into account when calculating the
final percentage of occlusion. Occluders are added to the image until the
desired level of occlusion is reached. Table 3 provides a comparison of the
performance of Tiny and Small networks’ Top-1 accuracy on three different
validation sets with occlusion levels of approximately 10%, 20%, and 30%. For
both Tiny and Small models, ConvNet Patch Mixing provides higher accuracy than
the original model across the board. However, the Swin models are always
superior to the ConvNeXt models, with Swin Patch Mixing outperforming or
matching Swin Original everywhere except the 30% and average SMD set using the
Small networks.

Table 3: Top-1 Accuracy on SMD. Three different validation sets of SMD are generated with occlusion levels of approximately 10%, 20%, and 30%. The average of all datasets, which is reported in the main paper, is also included. ConvNeXt trained with Patch Mixing outperforms all original ConvNeXt networks. Architecture | Tiny | Small
---|---|---
| 10% | 20% | 30% | Avg | 10% | 20% | 30% | Avg.
ConvNeXt Original | 63.2 | 41.1 | 38.6 | 47.6 | 65.1 | 42.8 | 40.4 | 49.4
ConvNeXt Patch Mixing | 64.2 | 42.5 | 40.1 | 48.9 | 65.4 | 43.2 | 41.6 | 50.1
Swin Original | 68.0 | 51.5 | 49.9 | 56.5 | 71.0 | 55.5 | 54.8 | 60.4
Swin Patch Mixing | 68.5 | 52.9 | 50.1 | 57.2 | 71.0 | 55.8 | 53.8 | 60.2

Figure 8: Examples from SMD with occlusion levels between 10-30%.

Figure 9: One example for each class of occluder object in SMD. From left to
right, the occluders in the first row are: airpods, bacteria, bacteriophage,
coronavirus, diamonds, drone, and graduation cap. Similarly for the second
row: Grogu (baby yoda), anatomical heart, origami heart, person, popcorn,
skateboard, and virtual reality headset.

## Realistic Occlusion Dataset (ROD) Details

Figure 10 contains representative samples of all 16 classes found in the ROD
dataset, as elaborated in Section 3 of the main text. It’s worth noting that
this figure is not comprehensive, as ROD contains over 40 distinct objects.
ConvNeXt-Tiny, when trained with Patch Mixing, outperforms the original model
on ROD, while the performance of Small networks remains unaffected.

Figure 10: From left to right, Row 1: dumbbell, cowboy hat, cup, and hammer.
Row 2: mouse, screwdriver, banana, and baseball. Row 3: laptop, microwave,
vase, and orange. Row 4: pillow, spatula, skillet, and plate.

## Naturalistic Variation Object Dataset (NVD)

Counterfactual simulation testing of ConvNeXt and Swin networks was performed
using the NVD occlusion subset [25]. For this experiment, all occluded scenes
were compared to an initial, non-occluded scene where the occluder was absent.

As seen in Figure 11, both Swin and ConvNeXt performances for Tiny and Small
networks significantly decline as the main object is increasingly occluded,
reaching a minimum at zero on the x-axis. Notwithstanding, ConvNeXt networks
trained with Patch Mixing demonstrate enhanced occlusion robustness compared
to their original versions. For less substantial occlusions, the ConvNeXt
Patch Mixing networks outperform the original models and even the Swin models.
This trend is more significant in the Tiny networks, although unlike the small
networks performance deteriorates and falls below Swin original as the
occluder approaches the center of the main object. Interestingly, the results
of Swin Patch Mixing are much worse than the originals for Tiny and Small
networks regardless of the occluder’s position.

Figure 11:  Occluder object x-axis position: Tiny and Small networks (NVD)

## Patch Mixing

Figure 12 illustrates the patch mixing experiments for both (7, 7) and (14,
14) grid sizes as the number of out-of-context patches increases. This is
discussed in Section 4.1 of the main paper. ConvNeXt trained with Patch Mixing
performs better than the original model for all experiments.

Figure 12: Examples of patch mixing experiments with (14, 14) - top - and (7,
7) - bottom - grid sizes with increasing information loss from 10-50% in
decadal intervals.

## Random Patch Drop

In this section we provide additional patch drop experiments for (7, 7) and
(16, 16) grid sizes, illustrated in Figure 13. Similar to the results of the
(14, 14) grid shown in Section 4.3 of the main paper, ConvNeXt trained with
Patch Mixing outperforms its counterpart in all cases. Additionally, for the
(7, 7) grid we see that ConvNeXt Patch Mixing outperforms the original Swin
Models for Tiny and Small networks and is on par with Swin Patch Mixing. We
also see that Swin performance either stays static or slightly increases, but
not by the same magnitude as ConvNext performance.

Figure 13: Random patch drop: tiny and small networks

Figure 14 provides a visualization of the random patch drop [20] experiments
conducted for (7,7), (14,14), and (16,16) grids with increasing information
loss up to 80%.

Information loss
---
20% | 40% | 60% | 80%
|  |  |
|  |  |
|  |  |

Figure 14: Patch drop examples for the (7,7), (14,14), and (16,16) grid sizes
in the top, middle, and bottom rows, respectively.

## Patch permutations

Figure 15 illustrates the patch permutation experiments [20] discussed in
Section 4.2 of the main paper. Images are shown with increasing shuffle grid
size, which is the total quantity of image patches in the shuffled images. The
performance gap between original and Patch Mixing trained ConvNeXt models
widens with increasing shuffle grid size, reaching over 20%, while the gap
between ConvNeXt-T trained with Patch Mixing and the original Swin-T remains
negligible, even with larger shuffle grid sizes.

Figure 15: Examples of patch permutations. The sequence from left to right is:
the original, unaltered image, followed by images with shuffled patches. The
total shuffle grid sizes for these subsequent images are 4, 16, 64, and 196,
respectively.

## c-RISE

In Figure 16 we illustrate the average out-of-context Softmax metric by class
for a random subset of 20 classes from the 100 classes tested. The methods and
results of c-RISE are discussed in Sections 2.2 and 4.3 of the paper,
respectively. ConvNeXt Patch Mixing performs better than the original model
for all but 3 classes.

Figure 16: Average out-of-context SoftMax metric by class.

## Broader Impact Discussion

This research paper shares both the benefits and potential risks inherent in
advancing the discriminative behavior of computer vision models. Our
refinement of the Patch Mixing technique improves robustness of CNNs to
occlusion, making them more useful in real-world applications where partial
visibility of objects is common, such has autonomous vehicles, security
cameras, and biomedical imaging. It also extends our understanding of how ViTs
and CNNs differ in their treatment of out-of-context information, which could
have implications for their application in settings requiring robustness to
occlusion. Unfortunately, this method can also be used to compromise models by
exploiting the inductive bias linked to patch selectivity.

A key aspect of this research is the development of the c-RISE explainability
technique. c-RISE provides a valuable tool for machine learning researchers
seeking to distinguish evidence between the top-1 prediction and the remaining
classes. Such insights can help in debugging, fine-tuning, and generally
improving the reliability and fairness of AI systems, particularly in
sensitive areas like healthcare, where interpretability of AI decisions are
incredibly important.


# The domination game played on diameter $2$ graphs

Csilla Bujtás$\/{}^{a}$, Vesna Iršič$\/{}^{a,b}$, Sandi Klavžara,b,c, Kexiang
Xu$\/{}^{d}$

a Faculty of Mathematics and Physics, University of Ljubljana, Slovenia
b Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia
c Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia
d College of Science, Nanjing University of Aeronautics & Astronautics,
Nanjing, Jiangsu 210016, PR China
<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Let $\gamma_{g}(G)$ be the game domination number of a graph $G$. It is proved
that if ${\rm diam}(G)=2$, then
$\gamma_{g}(G)\leq\left\lceil\frac{n(G)}{2}\right\rceil-\left\lfloor\frac{n(G)}{11}\right\rfloor$.
The bound is attained: if ${\rm diam}(G)=2$ and $n(G)\leq 10$, then
$\gamma_{g}(G)=\left\lceil\frac{n(G)}{2}\right\rceil$ if and only if $G$ is
one of seven sporadic graphs with $n(G)\leq 6$ or the Petersen graph, and
there are exactly ten graphs of diameter $2$ and order $11$ that attain the
bound.

Keywords: domination game; diameter 2 graph; computer experiment

AMS Math. Subj. Class. (2020): 05C57, 05C69

##  1 Introduction

The domination game has been investigated in depth by now, hence let us very
quickly recall its definition [3]. The game is played on a graph $G$ by
Dominator and Staller who alternately select their vertices. Each selected
vertex is required to dominate at least one new vertex. The game ends when the
vertices selected form a dominating set; Dominator’s goal is to finish the
game as soon as possible, Staller’s goal is the opposite. If Dominator is the
first to play, we speak of a D-game, otherwise it is an S-game. The number of
vertices selected in a D-game under the assumption that both players follow
optimal strategies is the game domination number $\gamma_{g}(G)$ of $G$. The
corresponding invariant for the S-game is denoted by $\gamma_{g}^{\prime}(G)$.

A central theme in the investigation of the game domination number is its
upper bounds in terms of the order $n(G)$ of a graph $G$. It all started with
the $3/5$-Graph Conjecture [19] asserting that if $G$ is an isolate-free
graph, then $\gamma_{g}(G)\leq\frac{3}{5}n(G)$. A strong support for the
conjecture is [15, Theorem 2.7] which asserts that it is true for all graphs
with minimum degree at least $2$. The conjecture is still open in general, the
best upper bound that holds for all graphs is
$\gamma_{g}(G)\leq\frac{5}{8}n(G)$ [7, Theorem 2.25]. Another appealing
conjecture, first stated in [18], is Rall’s $1/2$-Conjecture which asserts
that if $G$ is a traceable graph, then
$\gamma_{g}(G)\leq\lceil\frac{1}{2}n(G)\rceil$, cf. [8]. For additional topics
of interest related to the domination game and its variants see [2, 4, 6, 11,
16, 17, 22, 23, 25, 26].

In this paper we focus on the domination game played on graphs with diameter
$2$ and proceed as follows. In the next section we present some preliminary
results and introduce a new proof technique (Lemma 2.5) to be used in the rest
of the paper. In Section 3 we prove that if $G$ is a graph with ${\rm
diam}(G)=2$, then $\gamma_{g}(G)\leq\left\lceil\frac{n(G)}{2}\right\rceil$.
Moreover, we show that the equality holds for precisely eight graphs,
including the Petersen graph. Based on Section 3, in the subsequent section we
prove that if $G$ is a graph with ${\rm diam}(G)=2$, then
$\gamma_{g}(G)\leq\left\lceil\frac{n(G)}{2}\right\rceil-\left\lfloor\frac{n(G)}{11}\right\rfloor$.
All equality graphs of order $11$ are also discovered. In the concluding
section we relate our results to Rall’s $1/2$-Conjecture.

##  2 Preliminaries

We follow the standard graph terminology and notation from [24]. In
particular, if $G$ is a graph, then its minimum degree, maximum degree, and
domination number are denoted by $\delta(G)$, $\Delta(G)$, and $\gamma(G)$,
respectively. Also, if $v\in V(G)$, then $N_{G}(v)$ and $N_{G}[v]$ denote the
open and the closed neighborhood of $v$, respectively.

First observe that a nontrivial graph $G$ satisfies ${\rm diam}(G)\leq 2$ if
and only if the open neighborhood $N(v)$ is a dominating set for every vertex
$v\in V(G)$. Therefore, ${\rm diam}(G)=2$ implies $\gamma(G)\leq\delta(G)$. By
[3, Theorem 1], we have $\gamma_{g}(G)\leq 2\gamma(G)-1$, and thus
$\gamma_{g}(G)\leq 2\delta(G)-1$. We formulate this observation as a lemma.

###### Lemma 2.1

If $G$ is a graph of diameter $2$, then $\gamma_{g}(G)\leq 2\delta(G)-1$.

Recall that if $S\subseteq V(G)$, then $G|S$ denotes a _partially dominated
graph_ , so a graph $G$, where vertices from $S$ are already dominated. The
number of moves remaining in the game on $G|S$ under optimal play when
Dominator, resp. Staller, has the next move is denoted by $\gamma_{g}(G|S)$,
resp. $\gamma_{g}^{\prime}(G|S)$.

###### Lemma 2.2

If $G=(V,E)$ is a graph of diameter $2$, and $X\subseteq V$ is a non-empty set
of (undominated) vertices with $|X|=x$, then the partially dominated graph
$G|(V\setminus X)$ satisfies $\gamma_{g}(G|(V\setminus
X))\leq\lfloor\frac{2}{3}x+\frac{1}{3}\rfloor$ and
$\gamma_{g}^{\prime}(G|(V\setminus
X))\leq\lfloor\frac{2}{3}x+\frac{2}{3}\rfloor$.

Proof. First, we claim that Dominator can play a vertex which dominates at
least two new vertices in each of his moves, except maybe in the last one.
Assume that it is Dominator’s turn and that he cannot finish the game with a
single move. Hence at least two vertices of $G$ are not yet dominated, say $u$
and $v$. Since ${\rm diam}(G)=2$, either $d(u,v)=1$ or $d(u,v)=2$. In the
first case, Dominator can play $u$ (or $v$) to dominate at least two vertices.
And if $d(u,v)=2$, then Dominator can play a common neighbor of $u$ and $v$,
thus again dominating at least two vertices.

Let us now consider the D-game. Assume that the game is played on
$G|(V\setminus X)$, and that Dominator uses the above strategy of dominating
at least two new vertices at each of his moves (except maybe in his last one),
and Staller plays optimally. We distinguish the following two cases.

Case 1: The last move of the game is played by Staller.
In this case the number of moves played is even, say $2k$, $k\geq 1$. The
strategy of Dominator assures that during the game at least $2k+k$ different
vertices are dominated. Since in this counting the vertices are pairwise
different, we infer that

$2k+k\leq x\,.$

Since Staller plays optimally, but Dominator maybe not, we can estimate the
game domination number as follows:

$\gamma_{g}(G|(V\setminus X))\leq
2k\leq\left\lfloor\frac{2}{3}x\right\rfloor\leq\left\lfloor\frac{2}{3}x+\frac{1}{3}\right\rfloor\,.$

Case 2: The last move of the game is played by Dominator.
Now the number of moves played is odd, say $2k+1$. If $k=0$, then Dominator’s
first move finishes the game. Thus $\gamma_{g}(G|(V\setminus
X))=1\leq\lfloor\frac{2}{3}x+\frac{1}{3}\rfloor$. So from now on, we can
assume that $k\geq 1$, and hence Dominator cannot finish the game with a
single move. By the strategy of Dominator, at least $2k+k+1$ different
vertices are dominated. In this sum, the last $1$ corresponds to the last move
of Dominator in which it is possible that he dominates only one new vertex. It
follows that $3k+1\leq x$. Again, as Staller plays optimally but Dominator
maybe not, we can estimate that

$\gamma_{g}(G|(V\setminus X))\leq
2k+1\leq\left\lfloor\frac{2}{3}(x-1)+1\right\rfloor=\left\lfloor\frac{2}{3}x+\frac{1}{3}\right\rfloor\,,$

and we are done also in this case.

Similar reasoning shows the result for the S-game. $\square$

###### Corollary 2.3

If $G$ is a graph with ${\rm diam}(G)=2$, then

$\gamma_{g}(G)\leq\left\lfloor\frac{2}{3}\Big{(}n(G)-\Delta(G)\Big{)}\right\rfloor+1\,.$

Moreover, equality holds if $\Delta(G)\in\\{n(G)-1,n(G)-2\\}$.

Proof. If $\Delta(G)=n(G)-1$, then $\gamma_{g}(G)=1$, and if
$\Delta(G)=n(G)-2$, then $\gamma_{g}(G)=2$. Hence in both cases the equality
holds. In the rest we may thus assume that $\Delta(G)\leq n(G)-3$.

Suppose that Dominator starts the game by playing a vertex $v$ of degree
$\Delta(G)$. After this move, we are observing an S-game on $G|N[v]$, thus, by
Lemma 2.2, we have
$\gamma_{g}^{\prime}(G|N[v])\leq\lfloor\frac{2}{3}x+\frac{2}{3}\rfloor$, where
$x=n(G)-(\Delta(G)+1)$. This immediately gives $\gamma_{g}(G)\leq
1+\gamma_{g}^{\prime}(G|N[v])\leq
1+\lfloor\frac{2}{3}(n(G)-\Delta(G))\rfloor$. $\square$

In [3] it was observed that $\gamma_{g}(P)=5$, where $P$ is the Petersen
graph. Hence the equality in Corollary 2.3 is also sharp for some graphs with
$\Delta(G)<n(G)-2$. The following result yields an infinite family of this
kind of sharpness examples. Recall that vertices $u$ and $v$ of a graph $G$
are twins if $N[u]=N[v]$.

###### Proposition 2.4

If $G$ is a twin-free graph with ${\rm diam}(G)=2$ and
$\Delta(G)\in\\{n(G)-3,n(G)-4\\}$, then $\gamma_{g}(G)=3$.

Proof. Under the given conditions, Corollary 2.3 directly implies
$\gamma_{g}(G)\leq 3$. To prove that $\gamma_{g}(G)\geq 3$, we need to
describe an appropriate strategy of Staller. Assume that Dominator plays a
vertex $w$ as his first move. Let $Y=V(G)-N[w]$ and note that $|Y|\geq 2$. If
there exist vertices $u,v\in Y$ such that $uv\notin E(G)$, then Staller can
play $u$ (or $v$) as her first move, forcing Dominator to play his second
move. So assume that $Y$ induces a complete subgraph of $G$ and consider
arbitrary vertices $u,v\in Y$. Since $G$ is twin-free, $N(u)\cap N(w)\neq
N(v)\cap N(w)$. Let $x\in N(w)$ be a vertex with $xu\in E(G)$ and $xv\notin
E(G)$. If Staller plays $x$ as her first move, then she again forces Dominator
to play one more move. We conclude that $\gamma_{g}(G)\geq 3$. $\square$

Let $G_{k}$, $k\geq 2$, be the graph obtained from the disjoint union of
$K_{1,k}$ with leaves $u_{1},\ldots,u_{k}$, and from $K_{k}$ with vertices
$v_{1},\ldots,v_{k}$, by adding the edges $v_{i}u_{j}$ for all $i,j\in[k]$,
$i\neq j$. (We note in passing that $G_{k}$ is the Mycielskian $M(K_{k})$ of
$K_{k}$ [13, 21].) It is straightforward to check that $G_{k}$ satisfies all
the assumptions of Proposition 2.4, hence constituting an infinite family of
equality cases in Proposition 2.4.

To see that the twin-free condition in Proposition 2.4 is needed, consider the
following example. Let $H_{k}$, $k\geq 4$, be constructed as follows. Start
with $K_{k,k}$, and select two adjacent vertices $u$ and $v$ from it. Add a
vertex $w$ and connect it to all vertices of $K_{k,k}$. Finally, add two new
vertices $x$ and $y$, the edge $xy$, and connect both $x$ and $y$ to both $u$
and $v$. Note that $x$ and $y$ are twins, ${\rm diam}(H_{k})=2$, and
$\Delta(H_{k})=n(H_{k})-3$. If Dominator plays $w$ as his first move, then
Staller is forced to finish the game with her first move. Hence,
$\gamma_{g}(H_{k})=2$. To have such examples of $G$ with $\Delta(G)=n(G)-4$,
proceed similarly as above, with the only difference that instead of adding
the edge $xy$, we add a triangle.

We conclude this section by proving another lemma, which seems rather
technical, but is extremely useful. In a D-game, let $U_{i}$ and
$U_{i}^{\prime}$ denote the set of undominated vertices after the move $d_{i}$
of Dominator and the move $s_{i}$ of Staller, respectively. Set further
$u_{i}=|U_{i}|$, $u_{i}^{\prime}=|U_{i}^{\prime}|$, and
$S^{\prime}_{i}=\\{d_{1},\dots,d_{i},s_{1},\dots,s_{i}\\}.$ A _greedy
strategy_ of Dominator means that, for every $i\geq 1$, he plays a vertex
$d_{i}$ that makes $u_{i}$ as small as possible, that is, Dominator will
always select a vertex $v$ that maximizes $|\,N[v]\setminus
N[S_{i}^{\prime}]\,|$.

###### Lemma 2.5

If $G$ is a graph on $n$ vertices with minimum degree $\delta$ and $i\geq 1$,
then

$\displaystyle u_{1}$ $\displaystyle\leq n-\delta-1,$ $\displaystyle u_{i+1}$
$\displaystyle\leq
u_{i}^{\prime}\left(1-\frac{\delta+1}{n-2i}\right)=u_{i}^{\prime}\cdot\frac{n-2i-\delta-1}{n-2i},$
$\displaystyle u_{i}^{\prime}$ $\displaystyle\leq u_{i}-1,$

if Dominator follows a greedy strategy.

Proof. It is clear that at least $\delta+1$ vertices become dominated with the
first move $d_{1}$ of Dominator, and therefore, $u_{1}\leq n-(\delta+1)$.
Since Staller must dominate at least one new vertex on each move, we also have
$u_{i}^{\prime}\leq u_{i}-1$ for every $i\geq 1$.

It remains to prove the upper bound for $u_{i+1}$. If a vertex $v$ is
undominated after the move $s_{i}$, then $N[v]\subseteq V\setminus
S_{i}^{\prime}$. As $|N[v]|\geq\delta+1$, each vertex from $U_{i}^{\prime}$
can be dominated by at least $\delta+1$ different vertices from $V\setminus
S_{i}^{\prime}$. Since $|V\setminus S_{i}^{\prime}|=n-2i$, we may assume
$\delta+1\leq n-2i$ as otherwise the game would be over before the move
$d_{i+1}$. A double counting argument shows that $\sum_{v\in
U_{i}^{\prime}}|N[v]|=\sum_{u\in V\setminus S_{i}^{\prime}}|N[u]\cap
U_{i}^{\prime}|$. As $\sum_{v\in U_{i}^{\prime}}|N[v]|\geq
u_{i}^{\prime}(\delta+1)$ and $|V\setminus S_{i}^{\prime}|=n-2i$, a vertex
from $V\setminus S_{i}^{\prime}$ dominates at least

$\frac{u_{i}^{\prime}(\delta+1)}{n-2i}$

new vertices on average. Thus, according to his greedy strategy, Dominator
plays such a vertex that

$u_{i+1}\leq
u^{\prime}_{i}-\frac{u_{i}^{\prime}(\delta+1)}{n-2i}=u_{i}^{\prime}\left(1-\frac{\delta+1}{n-2i}\right)\,,$

which concludes the proof. $\square$

##  3 One-half of the order upper bound

In this section we first prove the following result and close the section by
discussing an alternative approach to its proof.

###### Theorem 3.1

If $G$ is a graph with ${\rm diam}(G)=2$, then

$\gamma_{g}(G)\leq\left\lceil\frac{n(G)}{2}\right\rceil\,.$

Moreover, the equality holds if and only if $G$ is one of the graphs from Fig.
1 or the Petersen graph.

Figure 1: Sporadic graphs with $\gamma_{g}(G)=\lceil n(G)/2\rceil$.

Proof. Let $G$ be a graph with ${\rm diam}(G)=2$. Set for this proof $V=V(G)$,
$n=n(G)$, $\delta=\delta(G)$, and $\Delta=\Delta(G)$.

Assume first that $\delta\geq n/4+1$. By Corollary 2.3, keeping in mind that
$\delta\leq\Delta$, we get:

$\displaystyle\gamma_{g}(G)$
$\displaystyle\leq\frac{2}{3}\Big{(}n-\Delta\Big{)}+1\leq\frac{2}{3}\Big{(}n-n/4-1\Big{)}+1$
$\displaystyle=\frac{n}{2}+\frac{1}{3}\,.$

Since both $n$ and $\gamma_{g}(G)$ are integers, we may infer
$\gamma_{g}(G)\leq\lceil\frac{n}{2}\rceil$.

Assume next that $\delta<n/4+1$. By Lemma 2.1, $\gamma_{g}(G)<n/2+1$. Since
both $n$ and $\gamma_{g}(G)$ are integers, we get
$\gamma_{g}(G)\leq\lceil\frac{n}{2}\rceil$. This proves the inequality.

For the equality, we have first performed a computer search over all graphs of
diameter $2$ and order at most $10$, and found the graphs listed in the
statement of the theorem. It thus remains to prove that if $n\geq 11$, then
$\gamma_{g}(G)<\left\lceil n/2\right\rceil$.

First assume that $\delta\leq\lfloor\frac{n+1}{4}\rfloor$. Using Lemma 2.1
again we obtain

$\gamma_{g}(G)\leq 2\delta-1\leq
2\left\lfloor\frac{n+1}{4}\right\rfloor-1<2\,\frac{n+2}{4}-1=\frac{n}{2}\leq\left\lceil\frac{n}{2}\right\rceil.$

For the remaining cases, we now assume
$\delta\geq\lfloor\frac{n+1}{4}\rfloor+1=\lfloor\frac{n+5}{4}\rfloor$. Using
this bound on the results from Lemma 2.5, we have that

$u_{1}\leq n-\left\lfloor\frac{n+5}{4}\right\rfloor-1\,,$

and

$u_{i+1}\leq(u_{i}-1)\left(1-\frac{\lfloor\frac{n+9}{4}\rfloor}{n-2i}\right).$

Applying these formulas for small cases, we obtain the following conclusions.
If $n=11$, then $u_{2}\leq 2$ and so Staller’s move $s_{2}$ leaves at most one
vertex undominated. Therefore, under the greedy strategy of Dominator, the
game finishes within $5$ moves that is smaller than
$\lceil\frac{11}{2}\rceil$. If $n=12$ or $13$, then $u_{2}\leq 3$. This gives
$u_{2}^{\prime}\leq 2$. Since $G$ is of diameter $2$, any two vertices are
adjacent or share a neighbor, they can be dominated by one move. We conclude
$\gamma_{g}(G)\leq 5<\lceil\frac{12}{2}\rceil<\lceil\frac{13}{2}\rceil$, thus
establishing the statement for $n=12$ and $13$. In a similar way we may show
$u_{2}\leq 4$, $u_{2}^{\prime}\leq 3$ and $u_{3}\leq 1$ for $n=14$, thus
proving $\gamma_{g}(G)\leq 6<\lceil\frac{14}{2}\rceil$.

From now on, we assume that $n\geq 15$ and, instead of
$\delta\geq\lfloor\frac{n+5}{4}\rfloor$, we use the weaker estimation
$\delta\geq\frac{n+2}{4}$. Then, $u_{1}\leq n-(\delta+1)\leq\frac{3n-6}{4}$
and $u_{1}^{\prime}\leq\frac{3n-10}{4}$. By these inequalities and Lemma 2.5,
we get

$\displaystyle u_{2}$
$\displaystyle\leq\frac{3n-10}{4}\left(1-\frac{n+6}{4(n-2)}\right)=\frac{(3n-10)(3n-14)}{16(n-2)}.$

Lemma 2.2 implies that we need at most $1+2u_{2}/3$ further moves to dominate
all vertices from $U_{2}$. Thus, Dominator can ensure that the game finishes
in at most

$4+\frac{2}{3}\cdot\frac{(3n-10)(3n-14)}{16(n-2)}$

moves. Now it is enough to consider the strict inequality

$4+\frac{2}{3}\cdot\frac{(3n-10)(3n-14)}{16(n-2)}<\frac{n}{2}\,.$

Since it is equivalent to

$0<3n^{2}-48n+52\,,$

which is valid for all $n\geq 15$, we may conclude that $\gamma_{g}(G)<n/2$
holds also for every integer $n\geq 15$. $\square$

One can also think about an alternative approach for proving the upper bound
in Theorem 3.1 using the following two known results.

###### Theorem 3.2

[14, Theorem 3.4] If $G$ is a graph with ${\rm diam}(G)=2$, then
$\gamma(G)\leq\lfloor n/4\rfloor+1$.

###### Theorem 3.3

[20, Theorem 5] Let $G$ be a graph of order $n$ and diameter $2$. If $n=4p+r$
with integers $p\geq 1$ and $0\leq r\leq 3$, then $\gamma(G)\leq\lfloor
n/4\rfloor=p$, when $r=0$, $p\geq 4$ or $r=1$, $p\geq 5$, or $r\in\\{2,3\\}$,
$p\geq 6$.

Since $\gamma_{g}(G)\leq 2\gamma(G)-1$, see [3, Theorem 1], it follows from
Theorem 3.2 that for a graph $G$ on $n$ vertices, where $n\not\equiv
0\pmod{4}$, and with diameter $2$, we have $\gamma_{g}(G)\leq\lceil
n/2\rceil$. The same conclusion follows from Theorem 3.3 for $n\equiv
0\pmod{4}$ and $n\geq 16$. The remaining cases of graphs on $4$, $8$, and $12$
vertices could then be handled by computer. As stated in the proof of Theorem
3.1, we have done this for graphs of order at most $10$. However, the
computation for all diameter $2$ graphs on $12$ vertices would require a lot
of computer time, hence we did not do it.

##  4 A stronger upper bound

In this section we improve Theorem 3.1 as follows.

###### Theorem 4.1

If $G$ is a graph with ${\rm diam}(G)=2$, then

$\gamma_{g}(G)\leq\left\lceil\frac{n(G)}{2}\right\rceil-\left\lfloor\frac{n(G)}{11}\right\rfloor.$
(1)

Proof. Let $G$ be a graph of diameter $2$ and order $n=n(G)$. First recall
that, by Theorem 3.1, we have $\gamma_{g}(G)\leq\lceil n/2\rceil$ and
consequently, (1) holds if $n<11$. By the same theorem, the strict inequality
$\gamma_{g}(G)<\lceil n/2\rceil$ is valid whenever $n\geq 11$. The latter
implies that (1) is true for every graph $G$ with $11\leq n\leq 21$.
Therefore, in the following, we assume $n\geq 22$.

The general result [5, Theorem 4] directly implies that, in the case of
$\delta(G)\geq 11$, we have $\gamma_{g}(G)<0.404\,n$. Since

$0.404\,n<\frac{9}{22}\,n=\frac{n}{2}-\frac{n}{11}\leq\left\lceil\frac{n}{2}\right\rceil-\left\lfloor\frac{n}{11}\right\rfloor,$

we may infer that the theorem holds if $\delta(G)\geq 11$.

Assume now that $\delta(G)\leq 5$. As $G$ is a graph of diameter $2$, we have
$\gamma_{g}(G)\leq 2\delta(G)-1\leq 9$ by Lemma 2.1. On the other hand, $9\leq
9n/22\leq\lceil n/2\rceil-\lfloor n/11\rfloor$ holds under the condition
$n\geq 22$, thus proving the theorem for the case of $\delta(G)\leq 5$.

If $\delta(G)=6$ and $n\geq 27$, we apply the inequalities $\gamma_{g}(G)\leq
2\delta(G)-1$ and $9n/22>11$, which results in

$\gamma_{g}(G)\leq
2\delta(G)-1=11<\frac{9}{22}\,n\leq\left\lceil\frac{n}{2}\right\rceil-\left\lfloor\frac{n}{11}\right\rfloor.$

In addition, one can check that $11=\lceil n/2\rceil-\lfloor n/11\rfloor$
holds, and therefore (1) is valid for $n=25$ and $n=26$. The remaining cases
are $n=22$, $23$ and $24$. Now, Lemma 2.5 moves in. Namely, following the
greedy strategy, we observe that Dominator dominates at least $\delta(G)+1=7$
vertices with his first move and therefore, $u_{1}\leq n-7$ and
$u_{1}^{\prime}\leq n-8$. Before the second move of Dominator, there is a
vertex that dominates at least $7u_{1}^{\prime}/(n-2)$ vertices. By playing
such a vertex, he achieves

$u_{2}\leq
u_{1}^{\prime}\left(1-\frac{7}{n-2}\right)\leq\frac{(n-8)(n-9)}{n-2}.$

After the second move of Staller, we then have $u_{2}^{\prime}\leq u_{2}-1$
and may calculate that the number of remaining moves is at most
$\lfloor\frac{2}{3}u_{2}^{\prime}+\frac{1}{3}\rfloor$ by Lemma 2.2. Thus we
conclude

$\gamma_{g}(G)\leq
4+\left\lfloor\frac{2}{3}\left(\frac{(n-8)(n-9)}{n-2}-1\right)+\frac{1}{3}\right\rfloor.$

The right-hand side formula equals $9$, $10$, $10$, respectively, for $n=22$,
$23$, $24$, which are exactly the corresponding values of $\lceil
n/2\rceil-\lfloor n/11\rfloor$. This finishes the proof for $\delta(G)=6$.

Assuming that $\delta(G)=7$, we give a similar reasoning as for $\delta(G)=6$.
If $n\geq 32$, then

$\gamma_{g}(G)\leq
2\delta(G)-1=13<\frac{9}{22}\,n\leq\left\lceil\frac{n}{2}\right\rceil-\left\lfloor\frac{n}{11}\right\rfloor.$

If $29\leq n\leq 31$, the inequality $13\leq\lceil n/2\rceil-\lfloor
n/11\rfloor$ is still valid and so (1) is true. Assume finally that $22\leq
n\leq 28$. It is clear that $u_{1}\leq n-8$ and $u_{1}^{\prime}\leq n-9$.
Applying Lemma 2.5, we get

$u_{2}\leq
u_{1}^{\prime}\left(1-\frac{8}{n-2}\right)\leq\frac{(n-9)(n-10)}{n-2}.$

Then, by Lemma 2.2,

$\gamma_{g}(G)\leq
4+\left\lfloor\frac{2}{3}\left(\frac{(n-9)(n-10)}{n-2}-1\right)+\frac{1}{3}\right\rfloor\leq\left\lceil\frac{n}{2}\right\rceil-\left\lfloor\frac{n}{11}\right\rfloor,$

where the last estimation can be verified by calculating the values for each
integer $22\leq n\leq 28$. This completes the proof for $\delta(G)=7$.

For the next case, suppose $\delta(G)=8$. If $n\geq 37$, then

$\gamma_{g}(G)\leq
2\delta(G)-1=15<\frac{9}{22}\,n\leq\left\lceil\frac{n}{2}\right\rceil-\left\lfloor\frac{n}{11}\right\rfloor$

which proves (1). If $n=35$ or $n=36$, then $15=\lceil n/2\rceil-\lfloor
n/11\rfloor$ holds and (1) is true. Suppose now that $22\leq n\leq 33$. By
Lemma 2.5, $u_{1}\leq n-9$ and $u_{1}^{\prime}\leq n-10$ hold. Moreover,
Dominator can ensure that

$u_{2}\leq
u_{1}^{\prime}\left(1-\frac{9}{n-2}\right)\leq\frac{(n-10)(n-11)}{n-2}\,.$

Then, taking into account Lemma 2.2, we get

$\gamma_{g}(G)\leq
4+\left\lfloor\frac{2}{3}\left(\frac{(n-10)(n-11)}{n-2}-1\right)+\frac{1}{3}\right\rfloor\leq\left\lceil\frac{n}{2}\right\rceil-\left\lfloor\frac{n}{11}\right\rfloor$

by checking the last inequality for each integer between $22$ and $33$. The
only remaining case for $\delta(G)=8$ is thus $n=34$. Here, we get
$u_{2}^{\prime}\leq\left\lfloor\frac{24\cdot 23}{32}-1\right\rfloor=16$ and
continue the process with estimating $u_{3}$ by using Lemma 2.5 again. This
yields

$u_{3}\leq\left\lfloor
u_{2}^{\prime}\left(1-\frac{9}{30}\right)\right\rfloor\leq\left\lfloor\frac{16\cdot
21}{30}\right\rfloor=11$

and $u_{3}^{\prime}\leq 10$. From this point, by Lemma 2.2, Dominator can
ensure that the game finishes within seven moves. This establishes
$\gamma_{g}(G)\leq 13<\lceil 34/2\rceil-\lfloor 34/11\rfloor=14$ and completes
the proof for $\delta(G)=8$.

If $\delta(G)=9$ and $n\geq 42$, we have $\gamma_{g}(G)\leq
2\delta(G)-1=17<\frac{9}{22}\,n$, which implies inequality (1). For $n=39$,
$40$, $41$, simple calculation shows $17\leq\lceil n/2\rceil-\lfloor
n/11\rfloor$ and we infer $\gamma_{g}(G)\leq\lceil n/2\rceil-\lfloor
n/11\rfloor$ again. To prove the theorem for the remaining cases, $22\leq
n\leq 38$, we first observe that $u_{1}\leq n-10$ and $u_{1}^{\prime}\leq
n-11$. Then, by playing greedily, Dominator can ensure (Lemma 2.5)

$u_{2}\leq
u_{1}^{\prime}\left(1-\frac{10}{n-2}\right)\leq\frac{(n-11)(n-12)}{n-2}$

and, by Lemma 2.2, we get

$\gamma_{g}(G)\leq
4+\left\lfloor\frac{2}{3}\left(\frac{(n-11)(n-12)}{n-2}-1\right)+\frac{1}{3}\right\rfloor\,.$

For each integer $22\leq n\leq 38$, the value of the right-hand side formula
is bounded from above by
$\left\lceil\frac{n}{2}\right\rceil-\left\lfloor\frac{n}{11}\right\rfloor$.
This completes the proof of (1) for $\delta(G)=9$.

The last case we have to consider is $\delta(G)=10$. If $n\geq 47$, then
$\gamma_{g}(G)\leq 2\delta(G)-1=19<\frac{9}{22}\,n$ holds, thus proving (1).
For $n=45$ and $n=46$, the inequality $\gamma_{g}(G)\leq 19=\lceil
n/2\rceil-\lfloor n/11\rfloor$ holds, thus implying the statement. If $22\leq
n\leq 44$, we consider the greedy startegy of Dominator which, by Lemma 2.5,
results in $u_{1}\leq n-11$, $u_{1}^{\prime}\leq n-12$,

$u_{2}\leq
u_{1}^{\prime}\left(1-\frac{11}{n-2}\right)\leq\frac{(n-12)(n-13)}{n-2}\,.$

Then, for $22\leq n\leq 43$, we can estimate (Lemma 2.2) the length of the
game as

$\gamma_{g}(G)\leq
4+\left\lfloor\frac{2}{3}\left(\frac{(n-12)(n-13)}{n-2}-1\right)+\frac{1}{3}\right\rfloor\leq\left\lceil\frac{n}{2}\right\rceil-\left\lfloor\frac{n}{11}\right\rfloor,$

where the last inequality can be easily checked for each integer $n$ in the
interval $[22,43]$. If $n=44$, the previous argumentation gives $u_{2}\leq
32\cdot 31/42$. Since $u_{2}$ is an integer, we have $u_{2}\leq 23$ and
$u_{2}^{\prime}\leq 22$. It follows from Lemma 2.5 that

$u_{3}\leq\left\lfloor
u_{2}^{\prime}\left(1-\frac{11}{40}\right)\right\rfloor\leq\left\lfloor\frac{22\cdot
29}{40}\right\rfloor=15\,,$

and so, by Lemma 2.2, the game will be finished in at most $10$ additional
moves. Thus, we conclude $\gamma_{g}(G)\leq 15$, which implies
$\gamma_{g}(G)<\lceil 44/2\rceil-\lfloor 44/11\rfloor=18$. This completes the
proof of Theorem 4.1. $\square$

The bound in Theorem 4.1 is attained. In fact, there are exactly $10$ graphs
on $11$ vertices with the game domination number equal to $5$, see Figure 2.
They were obtained using a computer. Let $G$ be a graph with $n(G)=11$. If
$\delta(G)\ \leq 2$, then Lemma 2.1 implies $\gamma_{g}(G)\leq 3$. And if
$\Delta(G)\geq 6$, then Corollary 2.3 yields $\gamma_{g}(G)\leq 4$. Hence, in
our computer search we only had to check the connected graphs $G$ on $11$
vertices with $\delta(G)\geq 3$ and $\Delta(G)\leq 5$.

Figure 2: Graphs on $11$ vertices with diameter $2$ and game domination number
$5$.

##  5 Concluding remarks

Note also that the upper bound in Theorem 3.1 is asymptotically not tight, and
for big enough $n$ it follows from know upper bounds on (total) domination
number, see for example [1, 10, 12]. In particular, the strongest known result
asserts that $\gamma_{t}(G)<\sqrt{\frac{n\log{n}}{2}}+\sqrt{\frac{n}{2}}$ for
all graphs $G$ of diameter $2$ and $n\geq 3$ vertices [12, Theorem 1]. Using
the well-known bounds $\gamma_{\rm g}(G)\leq 2\gamma(G)-1$ and
$\gamma(G)\leq\gamma_{t}(G)$, this yields

$\gamma_{\rm g}(G)\leq
2\left\lfloor\sqrt{\frac{n\log{n}}{2}}+\sqrt{\frac{n}{2}}\right\rfloor-1.$

The latter value is smaller than $\lceil\frac{n}{2}\rceil$ for all $n\geq 65$,
and smaller than $\lceil\frac{n}{2}\rceil-\lfloor\frac{n}{11}\rfloor$ for all
$n\geq 111$.

Recall that for any fixed positive real number $p<1$ (which is the probability
with which the edges of a random graph are selected mutually independently),
almost all graphs are connected with diameter $2$, cf. [9, Theorem 13.6].
Hence Theorem 4.1 (or Theorem 3.1 for that matter) imply that

$\gamma_{g}(G)<\frac{n(G)}{2}$

holds for almost all graphs $G$.

Theorem 3.1 and/or Theorem 4.1 offer another support for Rall’s
$1/2$-conjecture. That is, the conjecture holds for all graphs with diameter
$2$ and consequently for almost all graphs. In this direction, we have tried a
different approach than in [8], and proved, using a computer, that the
$1/2$-conjecture holds for all Hamiltonian graphs on $n\leq 10$ vertices.
Here, we have made use of [5, Corollary 5(ii)] to avoid checking graphs with
$\delta(G)\geq 5$.

## Acknowledgements

We are grateful to Gašper Košmrlj for providing us with his software that
computes game domination invariants. We acknowledge the financial support from
the Slovenian Research Agency (research core funding No. P1-0297 and projects
J1-9109, J1-1693, N1-0095, N1-0108). Kexiang Xu is also supported by NNSF of
China (grant No. 11671202) and China-Slovene bilateral grant 12-9.

## References

  * [1] S.M. Al-Yakoob, Zs. Tuza, Domination number of graphs with bounded diameter, J. Combin. Math. Combin. Comput. 40 (2002) 183–191.
  * [2] M. Borowiecki, A. Fiedorowicz, E. Sidorowicz, Connected domination game, Appl. Anal. Discrete Math. 13 (2019) 261–289.
  * [3] B. Brešar, S. Klavžar, D.F. Rall, Domination game and an imagination strategy, SIAM J. Discrete Math. 24 (2010) 979–991.
  * [4] B. Brešar, Cs. Bujtás, T. Gologranc, S. Klavžar, G. Košmrlj, T. Marc, B. Patkós Zs. Tuza, M. Vizer, The variety of domination games, Aequationes Math. 93 (2019) 1085–1109.
  * [5] Cs. Bujtás, On the game domination number of graphs with given minimum degree, Electron. J. Combin. 22 (2015) Paper 3.29, 18 pp.
  * [6] Cs. Bujtás, Zs. Tuza, Fractional domination game, Electron. J. Combin. 26 (2019) Paper 4.3, 17 pp.
  * [7] Cs. Bujtás, General upper bounds on the game domination number, Discrete Appl. Math. 285 (2020) 530–538.
  * [8] Cs. Bujtás, V. Iršič, S. Klavžar, K. Xu, On Rall’s $1/2$-conjecture on the domination game, Quaest. Math. (2020) DOI: 10.2989/16073606.2020.1822945.
  * [9] G. Chartrand, L. Lesniak, Graphs & Digraphs. Fourth Edition, Chapman & Hall/CRC, Boca Raton, FL, 2005.
  * [10] W.J. Desormeaux, T.W. Haynes, M.A. Henning, A. Yeo, Total domination in graphs with diameter 2, J. Graph Theory 75 (2014) 91–103.
  * [11] P. Dorbec, G. Košmrlj, G. Renault, The domination game played on unions of graphs, Discrete Math. 338 (2015) 71–79.
  * [12] A. Dubickas, Graphs with Diameter 2 and Large Total Domination Number, Graphs Combin. 37 (2021) 271–279.
  * [13] D.C. Fisher, P.A. McKenna, E.D. Boyer, Biclique parameters of Mycielskians, Congr. Numer. 111 (1995) 136–142.
  * [14] A. Hellwig, L. Volkmann, Some upper bounds for the domination number, J. Combin. Math. Combin. Comput. 57 (2006) 187–209.
  * [15] M.A. Henning, W.B. Kinnersley, Domination game: a proof of the $3/5$-conjecture for graphs with minimum degree at least two, SIAM J. Discrete Math. 30 (2016) 20–35.
  * [16] M.A. Henning, S. Klavžar, D.F. Rall, The $4/5$ upper bound on the game total domination number, Combinatorica 37 (2017) 223–251.
  * [17] Y. Jiang, M. Lu, Game total domination for cyclic bipartite graphs, Discrete Appl. Math. 265 (2019) 120–127.
  * [18] T. James, S. Klavžar, A. Vijayakumar, The domination game on split graphs, Bull. Aust. Math. Soc. 99 (2019) 327–337.
  * [19] W.B. Kinnersley, D.B. West, R. Zamani, Extremal problems for game domination number, SIAM J. Discrete Math. 27 (2013) 2090–2107.
  * [20] D. Meierling, L. Volkmann, Upper bounds for the domination number in graphs of diameter two, Util. Math. 93 (2014) 267–277.
  * [21] J. Mycielski, Sur le coloriage des graphes, Colloq. Math. 3 (1955) 161–162.
  * [22] M. J. Nadjafi-Arani, M. Siggers, H. Soltani, Characterisation of forests with trivial game domination numbers, J. Comb. Optim. 32 (2016) 800–811.
  * [23] W. Ruksasakchai, K. Onphaeng, C. Worawannotai, Game domination numbers of a disjoint union of paths and cycles, Quaest. Math. 42 (2019) 1357–1372.
  * [24] D.B. West, Introduction to Graph Theory, 2nd ed., Prentice-Hall, NJ, 2001.
  * [25] K. Xu, X. Li, On domination game stable graphs and domination game edge-critical graphs, Discrete Appl. Math. 250 (2018) 47–56.
  * [26] K. Xu, X. Li, S. Klavžar, On graphs with largest possible game domination number, Discrete Math. 341 (2018) 1768–1777.