#  A String Theoretic Derivation of Gibbons-Hawking Entropy

Gia Dvali  Arnold Sommerfeld Center, Ludwig-Maximilians-University, Munich,
Germany,  Max-Planck-Institute for Physics, Munich, Germany

###### Abstract

We describe an attempt of string theoretic derivation of the Gibbons-Hawking
entropy. Despite not admitting a de Sitter vacuum, the string theory, by the
power of open-close correspondence, captures the Gibbons-Hawking entropy as
the entropy of Chan-Paton species on a de Sitter-like state obtained via
$D$-branes. Moreover, this derivation sheds a new light at the origin of the
area-form, since the equality takes place for a critical ’t Hooft coupling for
which the species entropy of open strings saturates the area-law unitarity
bound.

##  .1 Introduction

Some time ago Gibbons:1977mu  Gibbons and Hawking pointed out that de Sitter
space possesses a microstate entropy that scales as the area of the horizon,

$S_{GH}\,\sim\,(RM_{P})^{2}\,,$ (1)

where $R$ is the de Sitter curvature radius and $M_{P}$ is the Planck mass.
This expression is very similar to the Bekenstein-Hawking entropy of a black
hole of equal radius Bekenstein:1973ur ; Hawking:1974sw .

While there is a full consensus about the correctness of $S_{GH}$ entropy,
there exist no commonly accepted microscopic explanation for it. It is natural
to ask whether we can gain some insight within string theoretic framework.

In this respect the situation with de Sitter is rather peculiar and goes in
contrast with black holes. Namely, there exist a well-known string theoretic
derivation of Bekenstein entropy of an extremal black hole by Strominger and
Vafa Strominger:1996sh .

There also exist other stringy handles on black hole entropy. For example,
more recently, it became evident that the Bekenstein-Hawking entropy can be
read out from the $S$-matrix elements of multi-graviton and multi-closed
string scattering processes at trans-Planckian center of mass energies
Dvali:2014ila ; Addazi:2016ksu . Correspondingly, such processes can be
interpreted as the $S$-matrix processes describing a black hole formation at
trans-Planckian energies tHooft:1987vrq ; Amati:1987wq ; Gross:1987kza , in
which the black hole is resolved as a multi-graviton coherent state
Dvali:2011aa .

At the same time, we are not aware of any string theoretic derivation of
Gibbons-Hawking entropy. The goal of the present paper is to fill this
omission. We shall base our discussion on the arguments and the construction
already provided in Dvali:2021bsy , where it was shown that via open-closed
duality the string theory carries a non-trivial information about the Gibbons-
Hawking entropy of de Sitter.

Let us fist notice that there are some fundamental differences between the
ways in which black holes and de Sitter are treated by the string theory.
First, no de Sitter vacuum exist in string theory. Its absence can be
understood as a result of $S$-matrix on which the formulation of string theory
is intrinsically based Dvali:2020etd . Any eternally-inflating de Sitter-like
universe makes a definition of $S$-matrix impossible. To our opinion, this
feature is an intrinsic source of various issues with formulation of quantum
gravity in de Sitter discussed by Witten Witten:2001kn .

The absence of de Sitter $S$-matrix justifies the earlier proposals about
incompatibility of de Sitter with quantum gravity Dvali:2013eja ;
Dvali:2014gua ; Dvali:2017eba . It also fully resonates with the so-called de
Sitter conjecture Obied:2018sgi  and, in the present context, even more
closely with the trans-Planckian censorship conjecture Bedroya:2019snp .

In contrast, as already remarked, black holes are in no conflict with
$S$-matrix. For example, the unstable, non-extremal, black holes can be
described as intermediate finite-lifetime resonances formed in an $S$-matrix
process with trans-Planckian center of mass energies. Alternatively, the
stable black holes, such as the extremal ones, can be viewed as legitimate
asymptotic $S$-matrix states.

None of the above is possible for de Sitter. Unlike a black hole, the de
Sitter is an eternally-inflating state with no possibility of defining the
$S$-matrix Dvali:2020etd . This difference can also be understood from the
fact that black holes can be formed in a collision process of in-states
without any need of a vacuum energy. In contrast, de Sitter necessarily
requires an uniform classical source in form of a cosmological constant.

However, the urgency for string-theoretic understanding of Gibbons-Hawking
entropy transcends the question of the de Sitter vacuum. The reason is that
the Gibbons-Hawking entropy is expected to be an intrinsic property of any
slow-roll inflationary Hubble patch even with a moderate number of e-foldings,
not conflicting with the existence of an asymptotic $S$-matrix vacuum.

In the present note, refining the earlier work Dvali:2021bsy , we shall show
that, despite not supporting a de Sitter vacuum, the string theory
nevertheless captures the origin of Gibbons-Hawking entropy thanks to the
power of open-closed correspondence. In the above paper it was observed that
in the regime in which the system admits a de Sitter like state, the Gibbons-
Hawking entropy is accounted by the species entropy of the open-string Chan-
Paton modes. We shall essentially repeat the construction of Dvali:2021bsy
and attempt to give it a form of a full-fledged derivation.

##  .2  A String Theoretic Construct

Before moving to actual derivation, we make some preparatory remarks and
define some useful quantities. The two important parameters are: the species
scale $M_{sp}$ and the species entropy $S_{sp}$.

The species scale sets an absolute cutoff on any $d$-dimensional theory of
gravity propagating $N_{sp}\gg 1$ particle species and is given by
Dvali:2007hz ; Dvali:2007wp ; Dvali:2008fd ; Dvali:2008ec ; Dvali:2009ks ;
Dvali:2010vm ; Dvali:2012uq ; Dvali:2020wqi , Dvali:2021bsy ,

$M_{sp}=\frac{M_{d}}{N_{sp}^{\frac{1}{d-2}}}\,,$ (2)

where $M_{d}$ is the $d$-dimensional Planck mass. The scale $1/M_{ps}$ is the
lower bound on the radius of a black hole beyond which the extrapolation of
semi-classical features is impossible. For example, a would-be black hole of a
smaller size cannot maintain the thermal Hawking radiation, or else, such a
black hole would explode in less than the light-crossing time, which would-be
an absurd.

We must note that the species scale has perturbative manifestations
Dvali:2001gx ; Veneziano:2001ah , however the power of the above black hole
arguments is that they are fully non-perturbative and therefore are
insensitive to a possible fine-tuning or a resummation of the series. More
recent discussions of various non-perturbative manifestations of the species
scale were given in vandeHeisteeg:2022btw ; vandeHeisteeg:2023ubh ;
vandeHeisteeg:2023dlw ; Cribiori:2022nke .

Another important concept, on which we shall rely heavily, is the “species
entropy”, $S_{sp}$, which measures the capacity of the system to store
information in the microstates of species Dvali:2008ec ; Dvali:2010vm ;
Dvali:2020wqi , Dvali:2021bsy . For the species that are approximately
degenerate in mass, in a state with total occupation number $N$, the species
entropy is given by the log of the binomial coeficient Dvali:2020wqi :

$\displaystyle S_{sp}$ $\displaystyle=$
$\displaystyle\ln\begin{pmatrix}N_{sp}+N\\\ N_{sp}\end{pmatrix}\simeq$
$\displaystyle\simeq$ $\displaystyle
N_{sp}\ln((1+N_{sp}/N)^{N/N_{sp}}(1+N/N_{sp}))\,,$

where in the last expression we used Stirling’s approximation. As shown in
Dvali:2020wqi , the saturation of species entropy takes place for $N\sim
N_{sp}$, which gives,

$S_{sp}\sim N_{sp}\,.$ (4)

The species entropy gives an alternative justification to the statement that
the cutoff is given by the species scale (2). Indeed, it has been shown
Dvali:2008ec ; Dvali:2010vm ; Dvali:2020wqi  that for a would-be black hole
smaller than the species scale, $1/M_{sp}$, the species entropy would exceed
the Bekenstein-Hawking entropy, which is impossible.

In our derivation, via open-closed correspondence, the Gibbons-Hawking entropy
shall emerge as the species entropy of the open-strings Dvali:2021bsy .

We start with an attempt of producing a de Sitter like state in string theory.
We shall use the standard (anti)$D$-brane uplifting mechanism put forward in
Dvali:1998pa ; Dvali:1999tq ; Dvali:2001fw . In fact, we do not have much
alternatives since, as already realized in the above work, $D$-branes are the
only known negative pressure sources in string theory.

The construction can be given in various string dimensions. However, in order
to avoid the secondary issues with technicalities of compactification, we
shall work in type IIB in ten dimensions.

As usual, the two fundamental parameters are the string coupling, $g_{s}$, and
the string scale, $M_{s}$. The ten-dimensional Planck mass, $M_{10}$, is
expressed via $M_{s}$ and $g_{s}$ as,

$M_{10}^{8}=\frac{M_{s}^{8}}{g_{s}^{2}}\,.$ (5)

Throughout the paper we shall omit the irrelevant numerical factors which can
be easily restored.

Following Dvali:2021bsy , we shall prepare a space-filling background with $n$
coincident $D_{9}$-branes and $n$ anti-$\bar{D}_{9}$-branes. The world-volume
(open string) physics of this system is rather well-understood
Srednicki:1998mq . The open string zero modes produce $N_{sp}\sim n^{2}$ light
Chan-Paton species which transform under the $U(n)\times U(n)$ gauge symmetry.

As discussed in Dvali:2010vm , such a background has associated ten-
dimensional species scale

$M_{sp}\,=\,\frac{M_{10}}{n^{1/4}}\,=\frac{M_{s}}{(ng_{s})^{\frac{1}{4}}}\,,$
(6)

and the corresponding species entropy (.2), which at the saturation point
takes the value (4),

$S_{sp}=n^{2}\,.$ (7)

This entropy reflects the existence of microstates with different excitation
patterns of the Chan-Paton species.

We shall be working in the ’t Hooft limit tHooft:1973alw  of large $n$ and
weak string coupling:

$n\rightarrow\infty\,,~{}g_{s}\rightarrow 0\,,$ (8)

while keeping the ’t Hooft coupling, $(ng_{s})$, as well as the string scale,
$M_{s}$, finite. We shall use the ’t Hooft coupling as a control parameter,
and shall approach the critical value, $(ng_{s})=1$, from below.

Notice that this background generates a no-trivial scalar potential for the
dilaton, thereby, likely making it time-dependent. We shall not enter in the
discussion of dilaton-stabilization 111We thank Cumrun Vafa for raising the
question about dilaton stability.. Instead, we shall limit ourselves by
restricting the time-scale of its potential evolution. The curvature scale of
the dilaton effective potential is set by the quantity,

$M_{s}^{2}(ng_{s})\,.$ (9)

This makes the potential time-dependence of the dilaton sufficiently slow for
our arguments to go through. We thus assume that on the time-scales of our
interest, dilaton is approximately frozen.

However, the background contains an open-string tachyon, with negative mass2
of order $m^{2}_{t}\sim-M_{s}^{2}$. This reflects the instability towards
mutual annihilation of $D$-branes and anti-$D$-branes. This process can be
described as the tachyon condensation Sen:1999mg . The classification is given
in terms of $K$-theory Witten:1998cd .

When tachyon condenses, the Chan-Paton species become massive. A part of them
gains the mass via the Higgs effect. Others become massive non-perturbatively.
This is also obvious from the fact that the closed-string vacuum cannot
support the open string excitations without $D$-branes.

Now, the idea of “brane inflation” scenario Dvali:1998pa ; Dvali:1999tq ;
Dvali:2001fw  is that, prior to tachyon condensation, the energy density
coming from $D$-brane tensions acts as vacuum energy, creating a temporary de
Sitter-like inflationary state. The tachyon condensation then provides a
graceful exit from inflation. The duration of the inflationary state depends
on the details of constructions in various dimensions to which we shall not
enter.

We shall rather focus on the state prior to tachyon condensation in which the
tachyon is carefully tuned in the position of unstable equilibrium, similarly
to a Higgs field on top of a “Mexican hat” potential.

For a moment, let us mentally freeze the tachyon. Then, due to a positive
vacuum energy density,

$\Lambda_{10}=n\frac{M_{s}^{10}}{g_{s}}\,,$ (10)

coming from the collective tension of $D$-branes, classically, the system
would produce a ten-dimensional de Sitter metric. The corresponding de Sitter
curvature radius would be 222Comparing with (9), it is clear that dilaton does
not evolve faster that the Hubble time, which justifies the validity of our
assumption.

$R\,=\,\sqrt{M_{10}^{8}/\Lambda_{10}}=\frac{1}{\sqrt{ng_{s}}M_{s}}\,.$ (11)

Therefore, the Gibbons-Hawking entropy would be equal to,

$S_{GH}=(RM_{10})^{8}=\frac{1}{g_{s}^{2}(ng_{s})^{4}}\,.$ (12)

Thus, in a state with artificially frozen tachyon, the system would posses two
types of entropies: 1) The gravitational Gibbons-Hawking entropy (12), coming
from closed strings; and 2) The Chan-Paton species entropy (7), coming from
open strings. Their ratio scales as,

$\frac{S_{sp}}{S_{GH}}=(ng_{s})^{6}\,.$ (13)

This may look disappointing, since keeping in mind the open-closed
correspondence, one could have hoped that the two entropies would come out
equal. However, the situation is quite the contrary.

In reality, none of the entropies are real, since the system is unstable on
the time-scale less than the Hubble time. In order to talk about entropies, we
must first reach the state in which the system is stabilized, at least for one
Hubble time. Only in such a state it makes sense to compare the two entropies.

Now, following Dvali:2021bsy , we can try to self-consistently stabilize the
tachyon using a general mechanism discussed earlier in Dvali:1999tq . We
proceed in the following way. Instead of Chan-Paton vacuum, we consider a
state in which the species are excited. Such excitations generate a positive
contribution into the mass2 of the tachyon field and can potentially stabilize
it.

In fact, in a would-be de Sitter, the Chan-Paton species would be
automatically excited due to the Gibbons-Hawking temperature of de Sitter,

$T_{GH}=\frac{1}{R}\,.$ (14)

Thus, we can proceed in the following manner. We can assume that tachyon has
been stabilized and check the self-consistency of this assumption by verifying
the thermal contribution to its mass from the Chan-Paton species.

In a would-be de Sitter, the effective mass-square of the tachyon would
receive the following positive contribution from the coupling to the thermal
bath of Chan-Paton species at temperature $T_{GH}$ 333Notice that a one-loop
correction from stringy version of Coleman-Weinberg potential shall not
overpower the thermal correction, if we use as a rough estimate the
calculation of Dvali:1994ms  with multiplicity of species $n^{2}$ and the
coupling $g_{s}^{2}$.

$\Delta m^{2}_{t}=\frac{(ng_{s})^{2}}{R^{2}}=(ng_{s})^{3}M_{s}^{2}\,.$ (15)

This contribution would balance the zero-temperature negative mass-square of
the tachyon, provided the parameters satisfy,

$(ng_{s})\sim 1\,.$ (16)

In this case the stack of branes could be stabilized.

This mechanism of potential stabilization of $D$-branes on top of each other
was previously considered in Dvali:1999tq  and can be viewed as the effect of
restoration of $U(n)\times U(n)$ symmetry at non-zero temperature.

The remarkable thing is that at the critical point (16) the Gibbons-Hawking
entropy becomes equal to the entropy of species (13), as this would be
expected from the open-closed correspondence.

The presented reasoning can be viewed as the microscopic understanding of
Gibbons-Hawking entropy in terms of the entropy of Chan-Paton species.

One may complain that there is a potential loophole because one could
seemingly violate the equality between the two entropies by taking

$(ng_{s})\gg 1\,.$ (17)

This is however not possible, since it would put our calculation out of the
domain of validity. This is signalled by several factors.

First, it was already noticed in Dvali:2010vm  that for (17), the ten-
dimensional species scale (6) which sets the absolute cutoff of effective low
energy theory, would drop below the string scale $M_{s}$. This is not
possible, since the cutoff in string theory is the string scale.

Simultaneously, the de Sitter curvature radius $R$ (11) would become shorter
than the string length $1/M_{s}$. This would signal that any geometric notion
of de Sitter becomes non-existent.

In particular, the Gibbons-Hawking temperature (14) of a would-be de Sitter
state exceeds the string scale and the Hagedorn effects Hagedorn:1965st  must
be taken into account Bowick:1992qu . At this point various stringy effects,
such as Atick-Witten phase transition Atick:1988si , also enter 444Various
discussion can be found in Alvarez:1986sj , Dienes:2012dc , and references
therein..

The important message that we deduce from our analysis is that in the unique
regime (16), in which the system can potentially deliver a de Sitter-like
state, the Gibbons-Hawking entropy (12) is understood as the species entropy
(.2) of the Chan-Paton species. At the critical point (16), the two entropies
are equal and they satisfy:

$S_{GH}=S_{sp}=n^{2}=\frac{1}{g_{s}^{2}}\,.$ (18)

Thus, by the power of open-closed correspondence, string theory offers a
microscopic understanding of Gibbons-Hawking entropy in terms of species
entropy of open strings.

##  .3 Species Origin of the Area-Law

With the equation (18) our task of string theoretic derivation of Gibbons-
Hawking entropy is complete. What comes next is the interpretational part.
Although this interpretation changes nothing in the above derivation, it is
nevertheless physically important, as it opens up a new view on open-closed
correspondence.

Namely, we would like to give some physical intuition to a “miracle” of
obtaining an intrinsically-geometric area-form of Gibbons-Hawking entropy
(12), from a seemingly-non-geometric concept of open string species entropy
(.2).

In fact, the story goes beyond the usual view of “holography” in which a
geometric area-count of the entropy is an exclusive feature of the
gravitational part of the theory (for a review, see Bousso:2002ju ).

Instead, as we shall see, both entropies, $S_{sp}$ and $S_{GH}$, independently
have very clear geometric area-forms. This feature is fundamentally linked
with the criticality of the ’t Hooft coupling (16). Moreover, at the same
time, for the critical coupling the two entropies are equal (18). That is, in
certain sense, the open-closed correspondence is responsible not for the area-
forms of the two entropies per se, but for their equalities at the critical ’t
Hooft coupling (16).

The key point is that, irrespective of gravity, the species microstate entropy
does have a geometric meaning in form of the following universal bound on the
microstate degeneracy Dvali:2020wqi :

$S_{max}=(Rf)^{d-2}\,.$ (19)

This bound implies that, within the validity of a given description, the
maximal microstate entropy attained by a $d$-dimensional system of a radius
$R$ is equal to its surface area in units of the scale of a spontaneously
broken Poincare symmetry, $f$.

The validity domain is defined in the usual quantum field theoretic (or string
theoretic) sense as the requirement of a weak coupling of the relevant degrees
of freedom. In particular, the saturation of the bound (19) is correlated with
the saturation of unitarity by a set of scattering amplitudes Dvali:2020wqi .

The bound (19) is universal and is independent of gravity, as long as the
system can be defined as a state on an asymptotic vacuum of Minkowski. In the
present case, this condition is satisfied, since our de Sitter-like state is
not eternal and is going to asymptote into a ten-dimensional Minkowski vacuum.
We can therefore classify the states according to the Poincare symmetry of
that vacuum.

Here, we shall not enter in the justification of the bound (19) for generic
systems, which can be found in Dvali:2020wqi  and in many related papers (for
an incomplete list, see, Dvali:2019jjw ; Dvali:2019ulr ; Dvali:2021ooc ;
Dvali:2021jto ; Dvali:2021rlf ; Dvali:2021tez ; Dvali:2021ofp ). Instead, we
shall limit ourselves by providing an intuition for the formula (19)
specifically for the species entropy, again following Dvali:2020wqi .

Let us imagine a $d$-dimensional system of radius $R$ with a total occupation
number $N$ of massless particle species. Such a system breaks the Poincare
symmetry at the scale

$f=\frac{N^{\frac{1}{d-2}}}{R}\,.$ (20)

This is easy to understand from the fact that the quantity $1/N$ is the
dimensionless coupling of the corresponding Goldstone mode.

At the same time, the species entropy (.2) at the saturation point is given by
$N=N_{sp}$. This immediately shows that (4) is given by (19). Thus, even in
the flat space, the species entropy, at its saturation point, carries a very
clear area-law meaning.

Applied to our $D$-brane construction, it is easy to see that at the critical
point (16) the scale of spontaneous breaking of the ten-dimensional Poincare
invariance is the ten-dimensional Planck scale,

$f=\frac{n^{\frac{1}{4}}}{R}=M_{10}\,.$ (21)

Correspondingly, the entropy of Chan-Paton species (7), which was already
shown to be equal to Gibbons-Hawking entropy (18), at the same time, saturates
the area-law bound (19) with $f=M_{10}$. Obviously, for $f=M_{10}$, the
equation (19) matches the general Gibbons-Hawking expression (12).

We thus see that the open-closed correspondence allows to understand the
Gibbons-Hawking entropy, and most importantly its area-form, as the saturation
of the universal bound (19) by the Chan-Paton species entropy (7) at the
critical ’t Hooft coupling (16).

##  .4 Some Implications

Here we briefly discuss some implications of our results.

###  .4.1 Glimpses of de Sitter Memory Burden

The above construction also allows us to catch glimpses of a de Sitter
“memory-burden” effect Dvali:2018ytn . The essence of the memory burden
phenomenon Dvali:2018xpy ; Dvali:2018ytn ; Dvali:2020wft ; Dvali:2024hsb  is
that the load of information tends to stabilize the system. The effect is
especially prominent in systems of maximal capacity of information (memory)
storage, in particular, the systems that saturate the bound (19) on the
microstate degeneracy, so-called “saturons”.

In such a system the information is stored in a set of degrees of freedom
called “memory modes”. Lower is the excitation energy cost of the memory mode,
more efficient is the information storage capacity of the system.

The special feature of enhanced memory systems is that they possess a critical
state in which many species of nearly-gapless memory modes emerge. This
criticality can be parameterized by a control order parameter called a “master
mode”.

The load of information corresponds to an excitation pattern of the memory
modes. This stabilizes the system in the state in which these modes are least
costly in energy.

Since the effect is universally present in systems of high microstate
degeneracy, it is expected to be operative in black holes Dvali:2018xpy ;
Dvali:2020wft ; Alexandre:2024nuo ; Thoss:2024hsr  and in de Sitter
Dvali:2018ytn .

In case of a black hole, the memory burden is expected to slow down the decay
after emission of about a half of the mass. The localized objects such as
black holes Dvali:2018xpy ; Dvali:2020wft ; Dvali:2024hsb  or solitons
Dvali:2021tez ; Dvali:2024hsb , when burdened by memory, are relatively
straightforward to be visualized.

However, the analogous question for de Sitter is more profound Dvali:2018ytn .
In particular, this is the case due to absence of an external observer.

In the present construction the meaning of the memory burden effect in a de
Sitter-like state becomes rather explicit. Indeed, the memory modes are the
Chan-Paton species, whereas tachyon is a master mode. When tachyon is on top
of the Mexican hat, the memory modes are gapless. If tachyon condenses, system
moves to the closed-string vacuum and the memory modes gain large mass gaps.
For excited memory modes, this would be very costly in energy.
Correspondingly, the excitations of Chan-Paton modes tend to create an energy
barrier and stabilize the tachyon on top of the hill.

In this way, the string theory allows us to catch a glimpse of a de Sitter
burdened by memory: it is a state at critical ’t Hooft coupling (16) with
quantum stringy effects becoming as important as the classical ones.

###  .4.2 Quantum Breaking of de Sitter

From the $S$-matrix perspective Dvali:2020etd , the de Sitter is expected to
be describable as a coherent state of gravitons constructed on top of an
asymptotic $S$-matrix vacuum of Minkowski Dvali:2013eja ; Dvali:2014gua ;
Dvali:2017eba  (for a BRST-invariant construction, see Berezhiani:2021zst )
555 Interestingly, this picture passes an immediate consistency test of
reproducing the Gibbons-Hawking entropy (12) as a particular case of
saturation of the bound (19). Indeed, since the asymptotic vacuum is
Minkowski, the notion of spontaneous breaking of Poincare symmetry by the de
Sitter coherent state is well-defined and the scale of breaking is the Planck
mass $f=M_{d}$, which again reproduces (12) from (19).. This picture comes
with an accompanying phenomenon of “quantum-breaking”. Its essence is that the
quantum evolution of the coherent state of gravitons, after a so-called
quantum break-time, $t_{Q}$, fully departs from the classical one.

In Dvali:2013eja  the quantum break-time from the inner entanglement of the
graviton state was suggested to be $t_{Q}\sim R\ln(S_{GH})$. This is very
similar to the time-scale given by the trans-Planckian censorship conjecture
Bedroya:2019snp . For the present stringy construction $t_{Q}$ translates as
Dvali:2020etd  $t_{Q}\sim R\ln(1/g_{s}^{2})$. Needless to say, a more precise
stringy computation of the log-factor would be highly informative.

##  .5 Outlook

In this note we offered a string theoretic view at the microscopic origin of
the Gibbons-Hawking entropy. In the limit of critical ’t Hooft coupling in
which a set of $D-\bar{D}$-branes delivers a de Sitter-like state, the entropy
of open string Chan-Paton species reproduces the gravitational Gibbons-Hawking
entropy. The crux of it all is in universal features of species entropy as
well as in open-close correspondence of string theory. This allows for
understanding of intrinsically gravitational entropy of closed strings in
terms of non-gravitational entropy of the Chan-Patton species.

Remarkably, the underlying physics of this connection goes beyond the ordinary
view on “holography” in which the geometric area-form is the exceptional
property of only one side of the description. Instead, the non-gravitational
species entropy, $S_{sp}$, at the saturation of unitarity, independently, has
the area-form (19) controlled by the strength of spontaneous breaking of the
Poincare symmetry. At the critical value (16) of the stringy ’t Hooft
coupling, the two entropies become equal (18).

The following comments are in order. First, of course, we expect corrections
from higher order operators CV . It is important to understand how they
correct the equation (18).

Secondly, the fact that our construction is valid up to a critical coupling
(16), prompts the question whether an analog of Horowitz-Polchinski string-
black hole correspondence Horowitz:1996nw  can be defined for the de Sitter
case CV . In certain sense, the presented construction indicates a path in
this direction via providing a correspondence between the entropies of open-
strings and Gibbons-Hawking.

Finally, it would be proper to understand a potential connection with AdS/CFT
correspondence Maldacena:1997re ; Gubser:1998bc ; Witten:1998qj .

Acknowledgements

We thank organizers of Lemaitre Conference 2024 where this work was presented.
It is pleasure to thank Cumrun Vafa for discussions.

This work was supported in part by the Humboldt Foundation under the Humboldt
Professorship Award, by the European Research Council Gravities Horizon Grant
AO number: 850 173-6, by the Deutsche Forschungsgemeinschaft (DFG, German
Research Foundation) under Germany’s Excellence Strategy - EXC-2111 -
390814868, Germany’s Excellence Strategy under Excellence Cluster Origins EXC
2094 – 390783311. The work of AK and OS was partially supported by the
Australian Research Council under the Discovery Projects grants DP210101636
and DP220101721.

Disclaimer: Funded by the European Union. Views and opinions expressed are
however those of the authors only and do not necessarily reflect those of the
European Union or European Research Council. Neither the European Union nor
the granting authority can be held responsible for them.

## References

  * (1) G. W. Gibbons and S. W. Hawking, “Cosmological Event Horizons, Thermodynamics, and Particle Creation,” Phys. Rev. D 15, 2738-2751 (1977) doi:10.1103/PhysRevD.15.2738
  * (2) J. D. Bekenstein, “Black holes and entropy,” Phys. Rev. D 7, 2333-2346 (1973) doi:10.1103/PhysRevD.7.2333
  * (3) S. W. Hawking, “Particle Creation by Black Holes,” Commun. Math. Phys. 43, 199-220 (1975) [erratum: Commun. Math. Phys. 46, 206 (1976)] doi:10.1007/BF02345020.
  * (4) A. Strominger and C. Vafa, “Microscopic origin of the Bekenstein-Hawking entropy,” Phys. Lett. B 379, 99-104 (1996) doi:10.1016/0370-2693(96)00345-0 [arXiv:hep-th/9601029 [hep-th]].
  * (5) G. Dvali, C. Gomez, R. S. Isermann, D. Lüst and S. Stieberger, “Black hole formation and classicalization in ultra-Planckian $2\rightarrow N$ scattering,” Nucl. Phys. B 893, 187-235 (2015) doi:10.1016/j.nuclphysb.2015.02.004 [arXiv:1409.7405 [hep-th]].
  * (6) A. Addazi, M. Bianchi and G. Veneziano, “Glimpses of black hole formation/evaporation in highly inelastic, ultra-planckian string collisions,” JHEP 02, 111 (2017) doi:10.1007/JHEP02(2017)111 [arXiv:1611.03643 [hep-th]].
  * (7) G. ’t Hooft, “Graviton Dominance in Ultrahigh-Energy Scattering,” Phys. Lett. B 198, 61-63 (1987) doi:10.1016/0370-2693(87)90159-6
  * (8) D. Amati, M. Ciafaloni and G. Veneziano, “Superstring Collisions at Planckian Energies,” Phys. Lett. B 197, 81 (1987) doi:10.1016/0370-2693(87)90346-7
  * (9) D. J. Gross and P. F. Mende, “The High-Energy Behavior of String Scattering Amplitudes,” Phys. Lett. B 197, 129-134 (1987) doi:10.1016/0370-2693(87)90355-8
  * (10) G. Dvali and C. Gomez, “Black Hole’s Quantum N-Portrait,” Fortsch. Phys. 61, 742-767 (2013) doi:10.1002/prop.201300001 [arXiv:1112.3359 [hep-th]].
  * (11) G. Dvali, “Quantum Gravity in Species Regime,” [arXiv:2103.15668 [hep-th]].
  * (12) E. Witten, “Quantum gravity in de Sitter space,” [arXiv:hep-th/0106109 [hep-th]].
  * (13) G. Dvali and C. Gomez, “Quantum Compositeness of Gravity: Black Holes, AdS and Inflation,” JCAP 01, 023 (2014) doi:10.1088/1475-7516/2014/01/023 [arXiv:1312.4795 [hep-th]].
  * (14) G. Dvali and C. Gomez, “Quantum Exclusion of Positive Cosmological Constant?,” Annalen Phys. 528, 68-73 (2016) doi:10.1002/andp.201500216 [arXiv:1412.8077 [hep-th]].
  * (15) G. Dvali, C. Gomez and S. Zell, “Quantum Break-Time of de Sitter,” JCAP 06, 028 (2017) doi:10.1088/1475-7516/2017/06/028 [arXiv:1701.08776 [hep-th]].
  * (16) G. Dvali, “$S$-Matrix and Anomaly of de Sitter,” Symmetry 13, no.1, 3 (2020) doi:10.3390/sym13010003 [arXiv:2012.02133 [hep-th]].
  * (17) G. Obied, H. Ooguri, L. Spodyneiko and C. Vafa, “De Sitter Space and the Swampland,” [arXiv:1806.08362 [hep-th]].
  * (18) A. Bedroya and C. Vafa, “Trans-Planckian Censorship and the Swampland,” JHEP 09, 123 (2020) doi:10.1007/JHEP09(2020)123 [arXiv:1909.11063 [hep-th]].
  * (19) G. Dvali, “Black Holes and Large N Species Solution to the Hierarchy Problem,” Fortsch. Phys. 58, 528-536 (2010) doi:10.1002/prop.201000009 [arXiv:0706.2050 [hep-th]].
  * (20) G. Dvali and M. Redi, “Black Hole Bound on the Number of Species and Quantum Gravity at LHC,” Phys. Rev. D 77, 045027 (2008) doi:10.1103/PhysRevD.77.045027 [arXiv:0710.4344 [hep-th]].
  * (21) G. Dvali, “Nature of Microscopic Black Holes and Gravity in Theories with Particle Species,” Int. J. Mod. Phys. A 25, 602-615 (2010) doi:10.1142/S0217751X10048895 [arXiv:0806.3801 [hep-th]].
  * (22) G. Dvali and C. Gomez, “Quantum Information and Gravity Cutoff in Theories with Species,” Phys. Lett. B 674, 303-307 (2009) doi:10.1016/j.physletb.2009.03.024 [arXiv:0812.1940 [hep-th]].
  * (23) G. Dvali and D. Lust, “Evaporation of Microscopic Black Holes in String Theory and the Bound on Species,” Fortsch. Phys. 58, 505-527 (2010) doi:10.1002/prop.201000008 [arXiv:0912.3167 [hep-th]].
  * (24) G. Dvali and C. Gomez, “Species and Strings,” [arXiv:1004.3744 [hep-th]].
  * (25) G. Dvali, C. Gomez and D. Lust, “Black Hole Quantum Mechanics in the Presence of Species,” Fortsch. Phys. 61, 768-778 (2013) doi:10.1002/prop.201300002 [arXiv:1206.2365 [hep-th]].
  * (26) G. Dvali, “Entropy Bound and Unitarity of Scattering Amplitudes,” J. High Energ. Phys. 2021, 126 (2021). https://doi.org/10.1007/JHEP03(2021)126 [arXiv:2003.05546 [hep-th]].
  * (27) G. R. Dvali, G. Gabadadze, M. Kolanović and F. Nitti, “Scales of gravity,” Phys. Rev. D 65, 024031 (2002) doi:10.1103/PhysRevD.65.024031 [arXiv:hep-th/0106058 [hep-th]].
  * (28) G. Veneziano, “Large N bounds on, and compositeness limit of, gauge and gravitational interactions,” JHEP 06, 051 (2002) doi:10.1088/1126-6708/2002/06/051 [arXiv:hep-th/0110129 [hep-th]];
  * (29) D. van de Heisteeg, C. Vafa, M. Wiesner and D. H. Wu, “Moduli-dependent Species Scale,” doi:10.4310/BPAM.2024.v1.n1.a1 [arXiv:2212.06841 [hep-th]].
  * (30) D. van de Heisteeg, C. Vafa and M. Wiesner, “Bounds on Species Scale and the Distance Conjecture,” Fortsch. Phys. 71, no.10-11, 2300143 (2023) doi:10.1002/prop.202300143 [arXiv:2303.13580 [hep-th]].
  * (31) D. van de Heisteeg, C. Vafa, M. Wiesner and D. H. Wu, “Species scale in diverse dimensions,” JHEP 05, 112 (2024) doi:10.1007/JHEP05(2024)112
  * (32) N. Cribiori, D. Lüst and G. Staudt, “Black hole entropy and moduli-dependent species scale,” Phys. Lett. B 844, 138113 (2023) doi:10.1016/j.physletb.2023.138113 [arXiv:2212.10286 [hep-th]].
  * (33) G. R. Dvali and S. H. H. Tye, “Brane inflation,” Phys. Lett. B 450, 72-82 (1999) doi:10.1016/S0370-2693(99)00132-X [arXiv:hep-ph/9812483 [hep-ph]]. For various implementations of this mechanism, see,
  * (34) G. R. Dvali, “Infrared hierarchy, thermal brane inflation and superstrings as superheavy dark matter,” Phys. Lett. B 459, 489-496 (1999) doi:10.1016/S0370-2693(99)00726-1 [arXiv:hep-ph/9905204 [hep-ph]].
  * (35) G. R. Dvali, Q. Shafi and S. Solganik, “D-brane inflation,” [arXiv:hep-th/0105203 [hep-th]].
  * (36) G. ’t Hooft, “A Planar Diagram Theory for Strong Interactions,” Nucl. Phys. B 72, 461 (1974) doi:10.1016/0550-3213(74)90154-0
  * (37) R. Hagedorn, “Statistical thermodynamics of strong interactions at high-energies,” Nuovo Cim. Suppl. 3, 147-186 (1965) CERN-TH-520.
  * (38) M. J. Bowick, “Finite temperature strings,” [arXiv:hep-th/9210016 [hep-th]].
  * (39) M. Srednicki, “IIB or not IIB,” JHEP 08, 005 (1998) doi:10.1088/1126-6708/1998/08/005 [arXiv:hep-th/9807138 [hep-th]].
  * (40) See, e.g., A. Sen, “NonBPS states and Branes in string theory,” [arXiv:hep-th/9904207 [hep-th]].
  * (41) G. R. Dvali, Q. Shafi and R. K. Schaefer, “Large scale structure and supersymmetric inflation without fine tuning,” Phys. Rev. Lett. 73, 1886-1889 (1994) doi:10.1103/PhysRevLett.73.1886 [arXiv:hep-ph/9406319 [hep-ph]].
  * (42) J. J. Atick and E. Witten, “The Hagedorn Transition and the Number of Degrees of Freedom of String Theory,” Nucl. Phys. B 310, 291-334 (1988) doi:10.1016/0550-3213(88)90151-4
  * (43) E. Alvarez and M. A. R. Osorio, “Superstrings at Finite Temperature,” Phys. Rev. D 36, 1175 (1987) doi:10.1103/PhysRevD.36.1175
  * (44) K. R. Dienes, M. Lennek and M. Sharma, “Strings at Finite Temperature: Wilson Lines, Free Energies, and the Thermal Landscape,” Phys. Rev. D 86, 066007 (2012) doi:10.1103/PhysRevD.86.066007 [arXiv:1205.5752 [hep-th]].
  * (45) E. Witten, “D-branes and K-theory,” JHEP 12, 019 (1998) doi:10.1088/1126-6708/1998/12/019 [arXiv:hep-th/9810188 [hep-th]].
  * (46) R. Bousso, “The Holographic principle,” Rev. Mod. Phys. 74, 825-874 (2002) doi:10.1103/RevModPhys.74.825 [arXiv:hep-th/0203101 [hep-th]].
  * (47) G. Dvali, “Area Law Saturation of Entropy Bound from Perturbative Unitarity in Renormalizable Theories,” Fortsch. Phys. 69, no.1, 2000090 (2021) doi:10.1002/prop.202000090 [arXiv:1906.03530 [hep-th]];
  * (48) G. Dvali, “Unitarity Entropy Bound: Solitons and Instantons,” Fortsch. Phys. 69, no.1, 2000091 (2021) doi:10.1002/prop.202000091 [arXiv:1907.07332 [hep-th]].
  * (49) G. Dvali and R. Venugopalan, “Classicalization and unitarization of wee partons in QCD and gravity: The CGC-black hole correspondence,” Phys. Rev. D 105, no.5, 056026 (2022) doi:10.1103/PhysRevD.105.056026 [arXiv:2106.11989 [hep-th]].
  * (50) G. Dvali, “Bounds on quantum information storage and retrieval,” Phil. Trans. A. Math. Phys. Eng. Sci. 380, no.2216, 20210071 (2021) doi:10.1098/rsta.2021.0071 [arXiv:2107.10616 [hep-th]].
  * (51) G. Dvali and O. Sakhelashvili, “Black-hole-like saturons in Gross-Neveu,” Phys. Rev. D 105, no.6, 065014 (2022) doi:10.1103/PhysRevD.105.065014 [arXiv:2111.03620 [hep-th]].
  * (52) G. Dvali, O. Kaikov and J. S. V. Bermúdez, “How special are black holes? Correspondence with objects saturating unitarity bounds in generic theories,” Phys. Rev. D 105, no.5, 056013 (2022) doi:10.1103/PhysRevD.105.056013 [arXiv:2112.00551 [hep-th]].
  * (53) G. Dvali, F. Kühnel and M. Zantedeschi, “Vortices in Black Holes,” Phys. Rev. Lett. 129, no.6, 061302 (2022) doi:10.1103/PhysRevLett.129.061302 [arXiv:2112.08354 [hep-th]].
  * (54) G. Dvali, “A Microscopic Model of Holography: Survival by the Burden of Memory,” [arXiv:1810.02336 [hep-th]].
  * (55) G. Dvali, L. Eisemann, M. Michel and S. Zell, “Universe’s Primordial Quantum Memories,” JCAP 03, 010 (2019) doi:10.1088/1475-7516/2019/03/010 [arXiv:1812.08749 [hep-th]].
  * (56) G. Dvali, L. Eisemann, M. Michel and S. Zell, “Black hole metamorphosis and stabilization by memory burden,” Phys. Rev. D 102, no.10, 103523 (2020) doi:10.1103/PhysRevD.102.103523 [arXiv:2006.00011 [hep-th]].
  * (57) A. Alexandre, G. Dvali and E. Koutsangelas, “New Mass Window for Primordial Black Holes as Dark Matter from Memory Burden Effect,” [arXiv:2402.14069 [hep-ph]].
  * (58) V. Thoss, A. Burkert and K. Kohri, “Breakdown of Hawking Evaporation opens new Mass Window for Primordial Black Holes as Dark Matter Candidate,” [arXiv:2402.17823 [astro-ph.CO]].
  * (59) G. Dvali, J. S. Valbuena-Bermúdez and M. Zantedeschi, “Memory Burden Effect in Black Holes and Solitons: Implications for PBH,” [arXiv:2405.13117 [hep-th]].
  * (60) L. Berezhiani, G. Dvali and O. Sakhelashvili, “de Sitter space as a BRST invariant coherent state of gravitons,” Phys. Rev. D 105, no.2, 025022 (2022) doi:10.1103/PhysRevD.105.025022 [arXiv:2111.12022 [hep-th]].
  * (61) Cumrun Vafa, private communications.
  * (62) G. T. Horowitz and J. Polchinski, “A Correspondence principle for black holes and strings,” Phys. Rev. D 55, 6189-6197 (1997) doi:10.1103/PhysRevD.55.6189 [arXiv:hep-th/9612146 [hep-th]].
  * (63) J. M. Maldacena, “The Large N limit of superconformal field theories and supergravity,” Adv. Theor. Math. Phys. 2, 231-252 (1998) doi:10.1023/A:1026654312961 [arXiv:hep-th/9711200 [hep-th]].
  * (64) S. S. Gubser, I. R. Klebanov and A. M. Polyakov, “Gauge theory correlators from noncritical string theory,” Phys. Lett. B 428, 105-114 (1998) doi:10.1016/S0370-2693(98)00377-3 [arXiv:hep-th/9802109 [hep-th]].
  * (65) E. Witten, “Anti-de Sitter space and holography,” Adv. Theor. Math. Phys. 2, 253-291 (1998) doi:10.4310/ATMP.1998.v2.n2.a2 [arXiv:hep-th/9802150 [hep-th]].


# Completeness-resolvable graphs

Min Feng1 Xuanlong Ma2††Corresponding author. Huiling Xu1
1School of Science, Nanjing University of Science and Technology, Nanjing,
210094, China
2School of Science, Xi’an Shiyou University, Xi’an, 710065, China

###### Abstract

Given a connected graph $G=(V(G),E(G))$, the length of a shortest path from a
vertex $u$ to a vertex $v$ is denoted by $d(u,v)$. For a proper subset $W$ of
$V(G)$, let $m(W)$ be the maximum value of $d(u,v)$ as $u$ ranging over $W$
and $v$ ranging over $V(G)\setminus W$. The proper subset
$W=\\{w_{1},\ldots,w_{|W|}\\}$ is a completeness-resolving set of $G$ if

$\Psi_{W}:V(G)\setminus W\longrightarrow[m(W)]^{|W|},\qquad
u\longmapsto(d(w_{1},u),\ldots,d(w_{|W|},u))$

is a bijection, where

$[m(W)]^{|W|}=\\{(a_{(1)},\ldots,a_{(|W|)})\mid 1\leq a_{(i)}\leq m(W)\text{
for each }i=1,\ldots,|W|\\}.$

A graph is completeness-resolvable if it admits a completeness-resolving set.
In this paper, we first construct the set of all completeness-resolvable
graphs by using the edge coverings of some vertices in given bipartite graphs,
and then establish posets on some subsets of this set by the spanning subgraph
relationship. Based on each poset, we find the maximum graph and give the
lower and upper bounds for the number of edges in a minimal graph.
Furthermore, minimal graphs satisfying the lower or upper bound are
characterized.

Key words: completeness-resolvable, resolving sets, distance, edge coverings,
bipartite graphs

2010 MSC: 05C12, 05C35, 05C70, 05C75

††E-mail address<EMAIL_ADDRESS>(M. Feng<EMAIL_ADDRESS>(X.
Ma),
<EMAIL_ADDRESS>(H. Xu).

##  1 Introduction

For a positive integer $m$, denote by $[m]$ the set of positive integers at
most $m$, and for a positive integer $k$, write

$[m]^{k}=\\{(a_{(1)},\ldots,a_{(k)})\mid a_{(i)}\in[m]\text{ for all
}i\in[k]\\}.$

Throughout of this paper, a graph means a finite and simple graph with at
least two vertices. Given a graph $G$, we always use $V(G)$ and $E(G)$ to
denote the vertex and edge sets of $G$, respectively. The order and size of
$G$ are the cardinalities of $V(G)$ and $E(G)$, respectively. We say that $G$
is connected if for any vertices $x,y\in V(G)$, there is a path from $x$ to
$y$ in $G$. The distance between $x$ and $y$, denoted by $d(x,y)$, is the
length of a shortest path from $x$ to $y$. For a proper subset $W$ of $V(G)$,
write

$m(W)=\max\\{d(w,u)\mid w\in W,u\in V(G)\setminus W\\}.$

The proper subset $W=\\{w_{1},\ldots,w_{|W|}\\}$ of $V(G)$ is a resolving set
of $G$ if

$\Psi_{W}:V(G)\setminus W\longrightarrow[m(W)]^{|W|},\qquad
u\longmapsto(d(w_{1},u),\ldots,d(w_{|W|},u))$

is an injection.

Resolving sets of a graph were first introduced, by Slater [10] and
independently, by Harary and Melter [6] in the 1970s. Subsequently, various
applications of resolving sets have appeared in the literature, as diverse as
network discovery and verification [2], robot navigation [8], pharmaceutical
chemistry[4], strategies for the Mastermind game [5], combinatorial
optimization [9] and so on. For an overview of resolving sets and related
topics, we refer to [1], [3] and [7].

A resolving set $W$ of a connected graph $G$ is a completeness-resolving set
if $\Psi_{W}$ is a bijection. We say that $G$ is completeness-resolvable if
$G$ admits a completeness-resolving set. Note that every connected graph has a
resolving set.

Problem 1. Which graphs are completeness-resolvable?

A vertex $x$ of a graph $G$ is universal if $x$ is adjacent to every other
vertices in $G$. Denote by $\mathcal{K}$ the set of graphs which have a
universal vertex. Let $\mathcal{P}$ be the set of all paths. In this paper, we
study completeness-resolvable graphs and obtain the following result.

###### Theorem 1.1

Let $G$ be a connected graph. Then $G$ is completeness-resolvable if and only
if $G$ is isomorphic to a graph in
$\mathcal{P}\cup\mathcal{K}\cup\mathcal{B}\cup\mathcal{C}$, where
$\mathcal{B}$ and $\mathcal{C}$ are as refer to Constructions 2.1 and 2.3,
respectively.

The rest of this paper is organized as follows.

In Section 2, we first give some notions and notations, and then construct
families $\mathcal{B}_{k}$ and $\mathcal{C}_{k}$ of graphs for each $k\geq 2$.
The constructions depends on edge coverings of some vertices in given
bipartite graphs. Actually, the sets $\mathcal{B}$ and $\mathcal{C}$ in
Theorem 1.1 are equal to $\bigcup_{k=2}^{+\infty}\mathcal{B}_{k}$ and
$\bigcup_{k=2}^{+\infty}\mathcal{C}_{k}$, respectively.

In Section 3, Theorem 1.1 is proved.

In Section 4, using the spanning subgraph relationship, we establish
respective posets on $\mathcal{B}_{k}$ and $\mathcal{C}_{k}$. Based on each
poset, we find the maximum graph and give the lower and upper bounds for the
size of a minimal graph. Furthermore, we characterize the minimal graphs
satisfying the lower or upper bound.

In Section 5, we first obtain the respective ranges for diameters of graphs in
$\mathcal{B}_{k}$ and $\mathcal{C}_{k}$. Then we introduce the concept of
perfectness-resolvable graphs, which are closely related to completeness-
resolvable graphs. Finally, we give sufficient conditions to determine a
perfectness-resolvable graph, and conclude this paper by raising a problem
which graphs are perfectness-resolvable.

##  2 Constructions

We first give some notions and notations that will be used throughout of this
paper. Let $G$ be a graph. For $x\in V(G)$ and $e\in E(G)$, we say that $e$
covers $x$, or $x$ is covered by $e$, if $e$ is incident to $x$ in $G$. For
$S\subseteq V(G)$, an edge covering of $S$, or $S$-covering, is a family $E$
of edges in $G$ such that each vertex in $S$ is covered by at least one edge
in $E$.

###### Notation 1

Given a graph $G$ and a subset $S\subseteq V(G)$, denote by $\mathcal{E}(G,S)$
the set of all $S$-coverings in $G$.

###### Notation 2

Let $k$ and $m$ be positive integers.

(i) For any vector $x\in[m]^{k}$, denote by $x_{(i)}$ the $i$th component of
$x$.

(ii) For $I\subseteq[k]$ and $J\subseteq[m]$, write

$[m]^{k}_{I}(J)=\\{x\in[m]^{k}\mid x_{(i)}\in J\text{ for all }i\in I\\}.$

For simplify, we write $[m]^{k}_{i}(J)$, $[m]^{k}_{I}(j)$ and $[m]^{k}_{i}(j)$
instead of $[m]^{k}_{\\{i\\}}(J)$, $[m]^{k}_{I}(\\{j\\})$ and
$[m]^{k}_{\\{i\\}}(\\{j\\})$, respectively.

(iii) For $S\subseteq[k]\cup[m]^{k}$, let $K_{S}$ and $\overline{K}_{S}$
denote the complete and null graphs on $S$, respectively.

(iv) Denote by $\mathcal{G}([k])$ and $\mathcal{G}([m]^{k})$ the sets of all
graphs with the vertex sets $[k]$ and $[m]^{k}$, respectively.

Let $G$ be a graph. A graph $H$ is a subgraph of $G$ if $V(H)\subseteq V(G)$
and $E(H)\subseteq E(G)$. Furthermore, the subgraph $H$ is a spanning subgraph
of $G$ if $V(H)=V(G)$. For $S\subseteq V(G)$, the induced subgraph of $G$ on
$S$ is the graph with the vertex set $S$ such that two vertices are adjacent
if and only if they are adjacent in $G$.

###### Notation 3

Let $k$ and $m$ be positive integers. For $E\subseteq E(K_{[m]^{k}})$, denote
by $span(E)$ the spanning subgraph of $K_{[m]^{k}}$ with the edge set $E$.

###### Notation 4

Let $k$ and $m$ be positive integers. For $H_{1}\in\mathcal{G}([k])$ and
$H_{2}\in\mathcal{G}([m]^{k})$, define $H_{1}\circ H_{2}$ as the graph on the
disjoined union $[k]\sqcup[m]^{k}$ with the edge set $E(H_{1})\cup
E(H_{2})\cup E(H_{1},H_{2})$, where

$E(H_{1},H_{2})=\\{\\{i,x\\}\mid i\in[k],x\in[m]^{k},x_{(i)}=1\\}.$

###### Remark 1

For $H_{1}\in\mathcal{G}([k])$ and $H_{2}\in\mathcal{G}([m]^{k})$, we have

$|E(H_{1}\circ H_{2})|=|E(H_{1})|+|E(H_{2})|+k\cdot m^{k-1}.$ (1)

Next, we construct a family $\mathcal{B}$ of graphs.

###### Construction 2.1

Let $\mathcal{B}=\bigcup_{k=2}^{+\infty}\mathcal{B}_{k}$, where
$\mathcal{B}_{k}$ is defined by the following steps.

(i) For each $i\in[k]$, denote by $B^{k}_{i}$ the complete bipartite graph
with two parts $[2]^{k}_{i}(1)$ and $[2]^{k}_{i}(2)$.

(ii) Define

$\mathcal{B}_{k}=\\{H_{1}\circ span(\bigcup_{i\in[k]}E_{i})\mid
H_{1}\in\mathcal{G}([k]),\;E_{i}\in\mathcal{E}(B_{i}^{k},[2]^{k}_{H_{1}(i)}(2))\\},$

where $H_{1}(i)$ is the union of $\\{i\\}$ and the set of vertices adjacent to
$i$ in $H_{1}$.

Observing that $\bigcup_{i\in[k]}E(B^{k}_{i})=E(K_{[2]^{m}})$, we have the
following result immediately from Construction 2.1.

###### Proposition 2.2

For $k\geq 2$, pick $H_{1}\in\mathcal{G}([k])$ and
$H_{2}\in\mathcal{G}([2]^{k})$. Then $H_{1}\circ H_{2}\in\mathcal{B}_{k}$ if
and only if the edge subset $L_{i}(H_{2})$ is a
$[2]^{k}_{H_{1}(i)}(2)$-covering for each $i\in[k]$, where

$L_{i}(H_{2})=E(H_{2})\cap E(B^{k}_{i}).$ (2)

We now construct another family $\mathcal{C}$ of graphs.

###### Construction 2.3

Let $\mathcal{C}=\bigcup_{k=2}^{+\infty}\mathcal{C}_{k}$, where
$\mathcal{C}_{k}$ is constructed by the following steps.

(i) For $i\in[k]$, let $C^{k}_{i}$ be the bipartite graph with two parts
$[3]^{k}_{i}(1)$ and $[3]^{k}_{i}(2)$, where the edge set is

$\\{\\{x,y\\}\mid
x\in[3]^{k}_{i}(1),y\in[3]^{k}_{i}(2),\;|x_{(t)}-y_{(t)}|\leq 1\text{ for each
}t\in[k]\setminus\\{i\\}\\}.$

(ii) For $i\in[k]$, let $D^{k}_{i}$ be the bipartite graph with two parts
$[3]^{k}_{i}(2)$ and $[3]^{k}_{i}(3)$, where the edge set is

$\\{\\{x,y\\}\mid
x\in[3]^{k}_{i}(2),y\in[3]^{k}_{i}(3),\;|x_{(t)}-y_{(t)}|\leq 1\text{ for each
}t\in[k]\setminus\\{i\\}\\}.$

(iii) Define

$\mathcal{C}_{k}=\\{\overline{K}_{[k]}\circ span(\bigcup_{i\in[k]}(E_{i}\cup
F_{i}))\mid
E_{i}\in\mathcal{E}(C_{i}^{k},[3]^{k}_{i}(2)),\;F_{i}\in\mathcal{E}(D_{i}^{k},S_{i}^{k})\\},$

where $S_{i}^{k}=[3]^{k}_{[k]}(\\{2,3\\})\cap[3]^{k}_{i}(3).$

We get the following result immediately from the construction of
$\mathcal{C}_{k}$.

###### Proposition 2.4

For $k\geq 2$, choose $H_{2}\in\mathcal{G}([3]^{k})$. Then
$\overline{K}_{[k]}\circ H_{2}\in\mathcal{C}_{k}$ if and only if the following
conditions hold.

(i) $E(H_{2})\subseteq\bigcup_{i\in[k]}(E(C^{k}_{i})\cup E(D^{k}_{i}))$.

(ii) For each $i\in[k]$, the edge subset $M_{i}(H_{2})$ is a
$[3]^{k}_{i}(2)$-covering, where

$M_{i}(H_{2})=E(H_{2})\cap E(C^{k}_{i}).$ (3)

(iii) For each $i\in[k]$, the edge subset $N_{i}(H_{2})$ is an
$S^{k}_{i}$-covering, where

$N_{i}(H_{2})=E(H_{2})\cap E(D^{k}_{i}).$ (4)

##  3 Proof of Theorem 1.1

In this section, we always suppose that $G$ is a connected graph. If $W$ is a
completeness-resolving set of $G$ with $|W|=k$ and $m(W)=m$, we say that $W$
is a $(k,m)$-completeness-resolving set, or $(k,m)$-CRS for simplify, and $G$
is a $(k,m)$-completeness-resolvable graph, or $(k,m)$-CRG for simplify. The
proof of Theorem 1.1 is divided in three subsections.

###  3.1 $k\geq 2$ and $m=2$

In this subsection, we determine the set of all $(k,2)$-CRGs for $k\geq 2$.

###### Lemma 3.1

With references to Construction 2.1, let $H$ be a graph in $\mathcal{B}_{k}$.

(i) For $i\in[k]$ and $x\in[2]^{k}$, we have $d(i,x)=x_{(i)}$.

(ii) The graph $H$ is a $(k,2)$-CRG.

Proof. (i) Write $H=H_{1}\circ H_{2}$, where $H_{1}\in\mathcal{G}([k])$ and
$H_{2}\in\mathcal{G}([2]^{k})$. If $x_{(i)}=1$, then $d(i,x)=1=x_{(i)}$. Now
suppose $x_{(i)}=2$. On one hand, since $i$ and $x$ are not adjacent in $H$,
we have $d(i,x)\geq 2$. On the other hand, if $x\in[2]^{k}_{H_{1}(i)}(2)$, by
Proposition 2.2, there is an edge $\\{x,y\\}\in L_{i}(H_{2})$, then
$y_{(i)}=1$, and so we get a path $(i,y,x)$ in $H$, which implies that
$d(i,x)\leq 2$. If $x\notin[2]^{k}_{H_{1}(i)}(2)$, then there exists a vertex
$t\in H_{1}(i)\setminus\\{i\\}$ such that $x_{(t)}=1$, and so we get a path
$(i,t,x)$ in $H$, which implies that $d(i,x)\leq 2$. Consequently, one has
$d(i,x)=2=x_{(i)}$.

(ii) It follows from (i) that $\Phi_{[k]}(x)=x$ for each $x\in[2]^{k}$.
Therefore, we have derived that $\Phi_{[k]}$ is a bijection, which implies
that $[k]$ is a $(k,2)$-CRS, and so $H$ is a $(k,2)$-CRG, as desired.
$\hfill\Box\vskip 6.0pt plus 2.0pt minus 2.0pt$

###### Proposition 3.2

For $k\geq 2$, a graph $G$ is a $(k,2)$-CRG if and only if $G$ is isomorphic
to a graph in $\mathcal{B}_{k}$.

Proof. The sufficiency holds by Lemma 3.1 (ii). To prove the necessity,
suppose that $G$ is a $(k,2)$-CRG and let $W=\\{w_{1},\ldots,w_{k}\\}$ be a
$(k,2)$-CRS of $G$. Then

$\Psi_{W}:V(G)\setminus W\longrightarrow[2]^{k},\qquad
u\longmapsto(d(w_{1},u),\ldots,d(w_{k},u))$

is a bijection. Define a graph $H$ on the set $[k]\cup[2]^{k}$ with the edge
set $E_{[k]}\cup E_{[2]^{k}}\cup E_{[k],[2]^{k}}$, where

$\displaystyle E_{[k]}$ $\displaystyle=$ $\displaystyle\\{\\{i,j\\}\mid
i,j\in[k],\;\\{w_{i},w_{j}\\}\in E(G)\\},$ $\displaystyle E_{[2]^{k}}$
$\displaystyle=$ $\displaystyle\\{\\{x,y\\}\mid
x,y\in[2]^{k},\;\\{\Psi_{W}^{-1}(x),\Psi_{W}^{-1}(y)\\}\in E(G)\\},$
$\displaystyle E_{[k],[2]^{k}}$ $\displaystyle=$
$\displaystyle\\{\\{i,x\\}\mid i\in[k],\;x\in[2]^{k},\;x_{(i)}=1\\}.$ (5)

Note that $x_{(i)}=d(w_{i},\Psi_{W}^{-1}(x))$. It is routine to verify that

$\Psi:V(G)\longrightarrow[k]\cup[2]^{k},\qquad
u\longmapsto\left\\{\begin{array}[]{ll}i,&\text{if }u=w_{i},\\\
\Psi_{W}(u),&\text{if }u\in V(G)\setminus W\end{array}\right.$

is an isomorphism from $G$ to $H$. Hence, graphs $G$ and $H$ are isomorphic.
Now it suffices to prove $H\in\mathcal{B}_{k}$.

Let $H_{1}$ and $H_{2}$ be the induced subgraphs of $H$ on $[k]$ and
$[2]^{k}$, respectively. Then $H=H_{1}\circ H_{2}$ by (5). Let $i\in[k]$. Pick
any vertex $x\in[2]^{k}_{H_{1}(i)}(2)$. For each $t\in H_{1}(i)$, we have
$d(w_{t},\Psi_{W}^{-1}(x))=x_{(t)}=2$. Particularly, one gets
$d(w_{i},\Psi_{W}^{-1}(x))=2$. Hence, there is $u\in V(G)\setminus W$ such
that $(w_{i},u,\Psi_{W}^{-1}(x))$ is a path in $G$, which implies that
$(i,\Psi_{W}(u),x)$ is a path in $H$, and so $\\{\Psi_{W}(u),x\\}\in
L_{i}(H_{2})$, where $L_{i}(H_{2})$ is as refer to (2). From the arbitrary
choice of $x$ in $[2]^{k}_{H_{1}(i)}(2)$, we have
$L_{i}(H_{2})\in\mathcal{E}(B_{i}^{k},[2]^{k}_{H_{1}(i)}(2))$. It follows from
Proposition 2.2 that $H\in\mathcal{B}_{k}$, as desired. $\hfill\Box\vskip
6.0pt plus 2.0pt minus 2.0pt$

###  3.2 $k\geq 2$ and $m=3$

In this subsection, we determine the set of all $(k,3)$-CRGs for $k\geq 2$.

###### Lemma 3.3

With references to Construction 2.3, let $H$ be a graph in $\mathcal{C}_{k}$.

(i) For $i\in[k]$ and $x\in[3]^{k}$, we have $d(i,x)=x_{(i)}$.

(ii) The graph $H$ is a $(k,3)$-CRG.

Proof. (i) Write $H=\overline{K}_{[k]}\circ H_{2}$, where
$H_{2}\in\mathcal{G}([3]^{k})$. Note that $x_{(i)}\in\\{1,2,3\\}$.

Case 1. $x_{(i)}=1$. Then $d(i,x)=1=x_{(i)}$.

Case 2. $x_{(i)}=2$. Since $x\in[3]^{k}_{i}(2)$, from Proposition 2.4 (ii),
there is an edge $\\{x,y\\}\in M_{i}(H_{2})$ for $y\in[3]^{k}_{i}(1)$, and so
we obtain a path $(i,y,x)$ in $H$, which implies that $d(i,x)=2=x_{(i)}$.

Case 3. $x_{i}=3$. Then $x\in[3]^{k}_{i}(3)$. On one hand, for any
$x^{\prime}\in[3]^{k}_{i}(1)$, since $|x_{(i)}-x^{\prime}_{(i)}|=2>1$,
according to Proposition 2.4 (i), vertices $x$ and $x^{\prime}$ are not
adjacent in $H_{2}$, which implies that $d(x^{\prime},x)\geq 2$. Hence, we get
$d(i,x)\geq 3$. On the other hand, if $x\in S^{k}_{i}$, then by Proposition
2.4 (iii), there is an edge $\\{x,z\\}\in N_{i}(H_{2})$ for
$z\in[3]^{k}_{i}(2)$, and further by Proposition 2.4 (ii), there is an edge
$\\{z,v\\}\in M_{i}(H_{2})$ for $v\in[3]^{k}_{i}(1)$, which implies that there
is a path $(i,v,z,x)$ in $H$, and so $d(i,x)\leq 3$; If $x\not\in S^{k}_{i}$,
then there is $t\in[k]$ with $x_{(t)}=1$, which indicates that
$(i,(1,\ldots,1),t,x)$ is a path in $H$, and so $d(i,x)\leq 3$. Consequently,
we get $d(i,x)=3=x_{(i)}$.

Combining all these three cases, we obtain (i).

(ii) It follows from (i) that $\Phi_{[k]}(x)=x$ for each $x\in[3]^{k}$. This
indicates that $\Phi_{[k]}$ is a bijection, and so $H$ is a $(k,3)$-CRG, as
desired. $\hfill\Box\vskip 6.0pt plus 2.0pt minus 2.0pt$

###### Lemma 3.4

Let $W$ be a $(k,3)$-CRS of a graph $G$.

(i) Then the induced subgraph of $G$ on $W$ is a null graph.

(ii) For $u,v\in V(G)\setminus W$, write $x=\Phi_{W}(u)$ and $y=\Phi_{W}(v)$.
If $u$ and $v$ are adjacent in $G$, then $|x_{(i)}-y_{(i)}|\leq 1$ for each
$i\in[k]$.

Proof. Let $W=\\{w_{1},w_{2},\ldots,w_{k}\\}$.

(i) Suppose for the contrary that there are vertices $w_{i},w_{j}\in W$ such
that $\\{w_{i},w_{j}\\}$ is an edge in $G$. Without loss of generality, assume
that $\\{w_{i},w_{j}\\}=\\{w_{1},w_{2}\\}$. Since $\Phi_{W}$ is an bijection,
there is a vertex $u_{0}\in V(G)\setminus W$ such that
$\Phi_{W}(u_{0})=(3,1,\ldots,1)$, which implies that

$3=d(w_{1},u_{0})\leq d(w_{1},w_{2})+d(w_{2},u_{0})=1+1,$

a contradiction.

(ii) By contradiction, suppose that there exists $i\in[k]$ such that
$|x_{(i)}-y_{(i)}|\geq 2$. Noting that $x,y\in[3]^{k}$, we have
$\\{x_{(i)},y_{(i)}\\}=\\{1,3\\}$. Without loss of generality, assume that
$x_{(i)}=1$ and $y_{(i)}=3$. Then

$3=y_{(i)}=d(w_{i},v)\leq d(w_{i},u)+d(u,v)=x_{(i)}+1=2,$

a contradiction. $\hfill\Box\vskip 6.0pt plus 2.0pt minus 2.0pt$

###### Proposition 3.5

For $k\geq 2$, a graph $G$ is a $(k,3)$-CRG if and only if $G$ is isomorphic
to a graph in $\mathcal{C}_{k}$.

Proof. The sufficiency holds by Lemma 3.3 (ii). Substituting $[3]^{k}$ for
$[2]^{k}$ in the proof of Proposition 3.2, we can obtain a graph $H=H_{1}\circ
H_{2}$ and an isomorphism $\Phi$ from $G$ to $H$, where $H_{1}$ and $H_{2}$
are graphs defined on the set $[k]$ and $[3]^{k}$, respectively. To get the
necessity, it is enough to prove $H\in\mathcal{C}_{k}$.

Noting that $\Phi^{-1}([k])$ is a $(k,3)$-CRS of $G$, we infer from Lemma 3.4
(i) that $H_{1}=\overline{K}_{[k]}$. Combining Lemma 3.4 (ii) and Proposition
2.4, we only need to show that
$M_{i}(H_{2})\in\mathcal{E}(C_{i}^{k},[3]^{k}_{i}(2))$ and
$N_{i}(H_{2})\in\mathcal{E}(D_{i}^{k},S_{i}^{k})$ for each $i\in[k]$.

Pick any vertex $x\in[3]^{k}_{i}(2)$. Then $d(i,x)=x_{(i)}=2$ by Lemma 3.3
(i). Since $H_{1}$ is null, there is a vertex $x^{\prime}\in[3]^{k}$ such that
$(i,x^{\prime},x)$ is a path in $H$, which implies that $x^{\prime}_{(i)}=1$,
and so $\\{x^{\prime},x\\}\in M_{i}(H_{2})$ by Lemma 3.4 (ii). From the
arbitrary choice of $x$ in $[3]^{k}_{i}(2)$, we have
$M_{i}(H_{2})\in\mathcal{E}(C_{i}^{k},[3]^{k}_{i}(2))$.

Pick any vertex $y\in S_{i}^{k}$. Then $d(i,y)=y_{(i)}=3$ by Lemma 3.3 (i).
Hence, there exist vertices $y^{\prime},y^{\prime\prime}\in[k]\cup[3]^{k}$
such that $(i,y^{\prime\prime},y^{\prime},y)$ is a path in $H$. Since
$d(t,y)=y_{(t)}\geq 2$ for each $t\in[k]$, one gets $y^{\prime}\in[3]^{k}$.
Noting that $H_{1}=\overline{K}_{[k]}$, we have $y^{\prime\prime}\in[3]^{k}$
and furthermore $y^{\prime\prime}_{(i)}=1$. It follows from Lemma 3.4 (ii)
that $|y^{\prime\prime}_{(i)}-y^{\prime}_{(i)}|\leq 1$ and
$|y^{\prime}_{(i)}-y_{(i)}|\leq 1$, and so $y^{\prime}_{(i)}=2$, which implies
that $\\{y^{\prime},y\\}\in N_{i}(H_{2})$. By the arbitrary choice of $y$ in
$S_{i}^{k}$, we have $N_{i}(H_{2})\in\mathcal{E}(D_{i}^{k},S_{i}^{k})$.

The proof is completed. $\hfill\Box\vskip 6.0pt plus 2.0pt minus 2.0pt$

###  3.3 Proof of Theorem 1.1

###### Proposition 3.6

A graph $G$ is a $(1,m)$-CRG if and only if $G$ is a path.

Proof. If $G$ is a $(1,m)$-CRG, then $G$ has a resolving set of cardinality
$1$, and so $G$ is a path. Conversely, if $G$ is a path
$(u_{0},u_{1},\ldots,u_{m})$, then $\Phi_{\\{u_{0}\\}}(u_{i})=(i)$ for
$i\in[m]$, which implies that $\\{u_{0}\\}$ is a $(1,m)$-CRS, and so $G$ is a
$(1,m)$-CRG, as desired. $\hfill\Box\vskip 6.0pt plus 2.0pt minus 2.0pt$

###### Proposition 3.7

A graph $G$ is a $(k,1)$-CRG if and only if the order of $G$ is $k+1$ and $G$
has a universal vertex.

Proof. Note that a vertex $u$ of $G$ is universal if and only if

$\Phi_{V(G)\setminus\\{u\\}}(u)=(1,\ldots,1).$

Hence, the desired result follows. $\hfill\Box\vskip 6.0pt plus 2.0pt minus
2.0pt$

###### Lemma 3.8

If $G$ is a $(k,m)$-CRG with $k\geq 2$ and $m\geq 2$, then $m=2$ or $3$.

Proof. By contradiction, suppose $m\geq 4$. Let
$W=\\{w_{1},w_{2},\ldots,w_{k}\\}$ be a $(k,m)$-CRS of $G$. Since $\Phi_{W}$
is a bijection, there exist vertices $u$ and $v$ in $V(G)\setminus W$ such
that $\Phi_{W}(u)=(1,1,\ldots,1)$ and $\Phi_{W}(v)=(4,1,\ldots,1)$, which
implies that

$4=d(w_{1},v)\leq d(w_{1},u)+d(u,w_{2})+d(w_{2},v)=1+1+1,$

a contradiction. $\hfill\Box\vskip 6.0pt plus 2.0pt minus 2.0pt$

Theorem 1.1 follows from Lemma 3.8 and Propositions 3.2, 3.5, 3.6 and 3.7.

##  4 Partially ordered sets

In Theorem 1.1, graphs in $\mathcal{P}\cup\mathcal{K}$ are well-understood,
however, graphs in $\mathcal{B}\cup\mathcal{C}$ are non-intuitive. Now the
letter $k$ is always used to denote a given positive integer at least $2$.
Note that graphs in $\mathcal{B}_{k}$ (resp. $\mathcal{C}_{k}$) have the same
vertex set $[2]^{k}$ (resp. $[3]^{k}$).

###### Notation 5

For graphs $G_{1}$ and $G_{2}$ with the same vertex set, define $G_{1}\preceq
G_{2}$ if $G_{1}$ is a spanning subgraph of $G_{2}$. Write $G_{1}\prec G_{2}$
if $G_{1}\preceq G_{2}$ and $G_{1}\neq G_{2}$.

A partially ordered set, or poset, is an ordered pair $(A,\leq)$ such that
$\leq$ is a reflexive, antisymmetric and transitive binary relation on the set
$A$. An element $x$ is maximum in $A$ if $a\leq x$ for each $a\in A$. An
element $y$ is minimal in $A$ if $a\leq y$ implies $a=y$. Observe that
$(\mathcal{B}_{k},\preceq)$ and $(\mathcal{C}_{k},\preceq)$ are posets on
graphs.

In Subsection 4.1 (resp. 4.2), based on the poset $(\mathcal{B}_{k},\preceq)$
(resp. $(\mathcal{C}_{k},\preceq)$), we first obtain the maximum graph in
$\mathcal{B}_{k}$ (resp. $\mathcal{C}_{k}$), and turn the problem of
characterizing graphs in $\mathcal{B}_{k}$ (resp. $\mathcal{C}_{k}$) into
characterizing minimal graphs in $\mathcal{B}_{k}$ (resp. $\mathcal{C}_{k}$).
Then we investigate minimal graphs in $\mathcal{B}_{k}$ (resp.
$\mathcal{C}_{k}$).

In Subsection 4.1, noting from Construction 2.1 that the first factor of a
graph in $\mathcal{B}_{k}$ is an arbitrary graph in $\mathcal{G}([k])$, we fix
$H_{1}\in\mathcal{G}([k])$ and give a definition of an $H_{1}$-minimal graph.
Then the size of an $H_{1}$-minimal graph is bounded by using the degrees of
vertices in $H_{1}$, and furthermore, we describe the $H_{1}$-minimal graphs
satisfying the lower or upper bound. As examples, we apply the results to
study $K_{[k]}$-minimal graphs and $\overline{K}_{[k]}$-minimal graphs.

In Subsection 4.2, noting from Construction 2.3 that the first factor of a
graph in $\mathcal{C}_{k}$ is the null graph in $\mathcal{G}([k])$, we say
that $H_{2}$ is $k$-minimal if $\overline{K}_{[k]}\circ H_{2}$ is a minimal
graph in $\mathcal{C}_{k}$. We establish the lower and upper bounds for the
size of a $k$-minimal graph, and characterize all $k$-minimal graphs
satisfying the lower or upper bound.

###  4.1 A poset on $\mathcal{B}_{k}$

In this subsection, we focus on the poset $(\mathcal{B}_{k},\preceq)$, and
always suppose that $H_{1}\in\mathcal{G}([k])$ and
$H_{2}\in\mathcal{G}([2]^{k})$.

###### Theorem 4.1

Suppose that $H_{1}\circ H_{2}\in\mathcal{B}_{k}$. If $H_{1}\preceq
H_{1}^{\prime}\preceq K_{[k]}$ and $H_{2}\preceq H_{2}^{\prime}\preceq
K_{[2]^{k}}$, then $H_{1}^{\prime}\circ H_{2}^{\prime}\in\mathcal{B}_{k}$.

Proof. For each $i\in[k]$, we get
$[2]^{k}_{H_{1}^{\prime}(i)}(2)\subseteq[2]^{k}_{H_{1}(i)}(2)$ and
$L_{i}(H_{2})\subseteq L_{i}(H_{2}^{\prime})$, where $L_{i}(H_{2})$ is as
refer to (2). Hence, the desired result follows by Proposition 2.2.
$\hfill\Box\vskip 6.0pt plus 2.0pt minus 2.0pt$

Let $G_{1}$ and $G_{2}$ be graphs with the same vertex set $V$. The union
$G_{1}\cup G_{2}$ is the graph with the vertex set $V$ and the edge set
$E(G_{1})\cup E(G_{2})$.

###### Corollary 4.2

For $G_{1},G_{2}\in\mathcal{B}_{k}$, we have $G_{1}\cup
G_{2}\in\mathcal{B}_{k}$. Particularly, we have

$\bigcup_{G\in\mathcal{B}_{k}}G=K_{[k]}\circ K_{[2]^{k}}\in\mathcal{B}_{k}.$

Proof. Let $G_{1}=H_{1}\circ H_{2}$ and $G_{2}=H_{1}^{\prime}\circ
H_{2}^{\prime}$. Then $G_{1}\cup G_{2}=(H_{1}\cup
H_{1}^{\prime})\circ(H_{2}\cup H_{2}^{\prime})$. Hence, the desired result
follows from Theorem 4.1. $\hfill\Box\vskip 6.0pt plus 2.0pt minus 2.0pt$

A join-semilattice is a poset in which any pair of elements has the least
upper bound. Note that each finite join-semilattice has a unique maximum
element. The following result is immediate from Corollary 4.2.

###### Proposition 4.3

The poset $(\mathcal{B}_{k},\preceq)$ is a finite join-semilattice with the
maximum graph $K_{[k]}\circ K_{[2]^{k}}$.

From Theorem 4.1, it is nature to put forward the following notion. We say
that $H_{2}$ is $H_{1}$-minimal if $H_{1}\circ H_{2}\in\mathcal{B}_{k}$ and
$H_{1}\circ H_{2}^{\prime}\not\in\mathcal{B}_{k}$ for $H^{\prime}_{2}\prec
H_{2}$.

###### Remark 2

If $H_{1}\circ H_{2}$ is a minimal graph in $\mathcal{B}_{k}$, then $H_{2}$ is
$H_{1}$-minimal. However, the converse is not true.

We get the following result from Proposition 2.2.

###### Lemma 4.4

A graph $H_{2}$ is $H_{1}$-minimal if and only if the following conditions
hold.

(i) For each $i\in[k]$, the edge subset $L_{i}(H_{2})$, as refer to (2), is a
$[2]^{k}_{H_{1}(i)}$-covering.

(ii) For each $e\in E(H_{2})$, there exists a vertex $i\in[k]$ such that
$L_{i}(H_{2})\setminus\\{e\\}$ is not a $[2]^{k}_{H_{1}(i)}$-covering.

###### Notation 6

Let $H_{1}\in\mathcal{G}([k])$ and $H_{2}\in\mathcal{G}([2]^{k})$.

(i) For $x\in[2]^{k}$, let $J_{x}=\\{i\in[k]\mid
x\in[2]^{k}_{H_{1}(i)}(2)\\}.$

(ii) For $x\in[2]^{k}$ and $e\in E(H_{2})$, write

$I_{x}(e)=\\{i\in[k]\mid x\in[2]^{k}_{H_{1}(i)}(2),\;e\in
L_{i}(H_{2}),\;e\text{ covers }x\\},$

and furthermore, let

$I_{x}=\bigcup_{f\in E(H_{2})}I_{x}(f)\qquad\text{ and
}\qquad\tilde{I}_{x}(e)=I_{x}\setminus(\bigcup_{f\in
E(H_{2})\setminus\\{e\\}}I_{x}(f)).$

###### Lemma 4.5

A graph $H_{2}$ is $H_{1}$-minimal if and only if the following conditions
hold.

(i) For each $x\in[2]^{k}$, we have $I_{x}=J_{x}$.

(ii) For each $e\in E(H_{2})$, there is a vertex $x\in[2]^{k}$ such that
$\tilde{I}_{x}(e)\neq\emptyset$.

Proof. Note that $I_{x}\subseteq J_{x}$. Observing that $i\in J_{x}$ if and
only if $x\in[2]^{k}_{H_{1}(i)}(2)$, we obtain (i) if and only if the
condition (i) in Lemma 4.4 holds.

Now suppose that the condition (i) in Lemma 4.4 holds. Then
$i\in\tilde{I}_{x}(e)$ if and only if any edge in
$L_{i}(H_{2})\setminus\\{e\\}$ does not cover $x$. Hence, we obtain (ii) if
and only if the condition (ii) in Lemma 4.4 holds.

Consequently, the desired result follows from Lemma 4.4. $\hfill\Box\vskip
6.0pt plus 2.0pt minus 2.0pt$

Actually, given a graph $H_{1}$, the $H_{1}$-minimal graph $H_{2}$ is not
unique. We give lower and upper bounds for the size of $H_{2}$. The degree of
a vertex in a graph is the number of edges covering this vertex in the graph.

###### Theorem 4.6

If $H_{2}$ is $H_{1}$-minimal, then

$2^{k-\min\\{d_{i}\mid
i\in[k]\\}-1}\leq|E(H_{2})|\leq\sum_{i=1}^{k}2^{k-d_{i}-1},$

where $d_{i}$ is the degree of the vertex $i$ in $H_{1}$.

Proof. For each $i\in[k]$, write $E_{i}=L_{i}(H_{2})$ and denote by
$E_{i}^{\prime}$ the set of edges $e$ such that $L_{i}(H_{2})\setminus\\{e\\}$
is not a $[2]^{k}_{H_{1}(i)}$-covering. By Lemma 4.4 (ii), we have

$\max\\{|E_{i}|\mid
i\in[k]\\}\leq|\bigcup_{i\in[k]}E_{i}|=|E(H_{2})|=|\bigcup_{i\in[k]}E_{i}^{\prime}|\leq\sum_{i\in[k]}|E^{\prime}_{i}|.$

Noting that $|E_{i}^{\prime}|\leq 2^{k-|H_{1}(i)|}=2^{k-d_{i}-1}\leq|E_{i}|$,
we get the desired result. $\hfill\Box\vskip 6.0pt plus 2.0pt minus 2.0pt$

###### Remark 3

If $H_{1}\circ H_{2}$ is a minimal graph in $\mathcal{B}_{k}$, then combining
the equation (1), Remark 2 and Theorem 4.6, we get

$k\cdot 2^{k-1}+\frac{1}{2}\sum_{i=1}^{k}d_{i}+2^{k-\min\\{d_{i}\mid
i\in[k]\\}-1}\leq|E(H_{1}\circ H_{2})|\leq k\cdot
2^{k-1}+\frac{1}{2}\sum_{i=1}^{k}(2^{k-d_{i}}+d_{i}).$

The minimum degree of a graph is the minimum value of degrees of all vertices
in this graph. We use the following result to characterize the bounds in
Theorem 4.6.

###### Corollary 4.7

Suppose that $H_{2}$ is $H_{1}$-minimal.

(i) The lower bound in Theorem 4.6 is attained if and only if there exists a
vertex $i$ with minimum degree in $H_{1}$ such that $L_{i}(H_{2})=E(H_{2})$.

(ii) The upper bound in Theorem 4.6 is attained if and only if for any
distinct vertices $x,y\in[2]^{k}$ and any distinct edges $e,f\in E(H_{2})$, we
have (a) $|I_{x}(e)|\leq 1$, (b) either $I_{x}(e)=\emptyset$ or
$I_{y}(e)=\emptyset$, (c) $I_{x}(e)\cap I_{x}(f)=\emptyset$.

Proof. (i) It is immediate from the proof of the lower bound in Theorem 4.6.

(ii) Suppose that (a), (b) and (c) hold. Observing that
$\tilde{I}_{x}(e)\subseteq I_{x}(e)$, we infer from Lemma 4.5 (ii) that

$\displaystyle E(H_{2})$ $\displaystyle=$
$\displaystyle\bigcup_{x\in[2]^{k}}\\{e\in
E(H_{2})\mid\tilde{I}_{x}(e)\neq\emptyset\\}=\bigcup_{i\in[k]}\;\bigcup_{x\in[2]^{k}_{H_{1}(i)}(2)}\\{e\in
E(H_{2})\mid i\in I_{x}(e)\\}$ $\displaystyle=$
$\displaystyle\bigcup_{i\in[k]}\\{e\in E(H_{2})\mid i\in I_{x}(e)\text{ for a
certain vertex }x\in[2]^{k}_{H_{1}(i)}(2)\\},$

and so $|E(H_{2})|=\sum_{i\in[k]}|[2]^{k}_{H_{1}(i)}(2)|$, attaining the upper
bound in Theorem 4.6.

In the following, suppose that $|E(H_{2})|$ attains the upper bound in Theorem
4.6. With references to the proof of Theorem 4.6, the following conditions
hold.

(C1) $|E_{i}^{\prime}|=2^{k-d_{i}-1}$ for each $i\in[k]$.

(C2) $E_{i}^{\prime}\cap E_{j}^{\prime}=\emptyset$ for any distinct vertices
$i$ and $j$ in $[k]$.

By (C1), the following condition holds for each $i\in[k]$.

(C1′) For each $x\in[2]^{k}_{H_{1}(i)}(2)$, there is a unique edge $e\in
E_{i}^{\prime}$ such that $e$ covers $x$.

Now we divide the proof in three steps.

We first prove (c). By contradiction, suppose $I_{x}(e)\cap
I_{x}(f)\neq\emptyset$. Pick $i\in I_{x}(e)\cap I_{x}(f)$. Then
$x\in[2]^{k}_{H_{1}(i)}(2)$, $\\{e,f\\}\subseteq L_{i}(H_{2})$ and both $e$
and $f$ cover $x$, which implies that there is no edge in $E_{i}^{\prime}$
covering $x$, contrary to (C1′).

The next thing is to prove (a). Suppose for the contrary that $|I_{x}(e)|\geq
2$. Pick distinct vertices $i,j\in I_{x}(e)$. Note that
$E_{i}^{\prime}\subseteq L_{i}(H_{2})$ and $E_{j}^{\prime}\subseteq
L_{j}(H_{2})$. Combining (C1′) and (c), we get $e\in E_{i}^{\prime}\cap
E_{j}^{\prime}$, contrary to (C2).

Finally, we prove (b). By contradiction, suppose that $I_{x}(e)\neq\emptyset$
and $I_{y}(e)\neq\emptyset$. Then $e=\\{x,y\\}$. Taking $i\in I_{x}(e)$ and
$j\in I_{y}(e)$, we have $(y_{(i)},x_{(i)})=(1,2)$ and
$(x_{(j)},y_{(j)})=(1,2)$, which implies that $i\neq j$. An argument similar
to the one used in the previous step shows that $e\in E_{i}^{\prime}\cap
E_{j}^{\prime}$, contrary to (C2).

The proof is complete. $\hfill\Box\vskip 6.0pt plus 2.0pt minus 2.0pt$

As applications, we study $K_{[k]}$-minimal graphs and
$\overline{K}_{[k]}$-minimal graphs in the rest of this subsection. To
inverstigate $K_{[k]}$-minimal graphs, we observe that

$[2]^{k}_{K_{[k]}(i)}(2)=\\{(2,\ldots,2)\\},$ (6)

and then get the following example from Lemma 4.5.

###### Example 4.8

(i) Define $\mathbb{U}_{k}$ as the graph with the vertex set $[2]^{k}$ and the
edge set

$E(\mathbb{U}_{k})=\\{(1,\ldots,1),(2,\ldots,2)\\}.$

Then $\mathbb{U}_{k}$ is a $K_{[k]}$-minimal graph with size $1$.

(ii) Define $\mathbb{V}_{k}$ as the graph with the vertex set $[2]^{k}$ and
the edge set

$E(\mathbb{V}_{k})=\bigcup_{i\in[k]}\\{\\{x,(2,\ldots,2)\\}\mid
x_{(i)}=1,x_{(t)}=2\text{ for each }t\in[k]\setminus\\{i\\}\\}.$

Then $\mathbb{V}_{k}$ is a $K_{[k]}$-minimal graph with size $k$.

###### Corollary 4.9

If $H_{2}$ is $K_{[k]}$-minimal, then $1\leq|E(H_{2})|\leq k$,

(i) with the lower bound if and only if $H_{2}=\mathbb{U}_{k}$.

(ii) with the upper bound if and only if $H_{2}=\mathbb{V}_{k}$.

Proof. Noting that the degree of each vertex $i$ in $K_{[k]}$ is $k-1$, we
have $1\leq|E(H_{2})|\leq k$ by Theorem 4.6.

(i) The “if” implication follows immediately from Example 4.8 (i), while the
“only if” implication follows from (6) and Lemma 4.5 (i).

(ii) We get the sufficiency from Example 4.8 (ii). To prove the necessity,
suppose $|E(H_{2})|=k$. Write $y=(2,\ldots,2)$. By (6), we have $J_{y}=[k]$
and $J_{z}=\emptyset$ for $z\in[2]^{k}\setminus\\{y\\}$. Noting that
$|E(H_{2})|$ attains the upper bound in Theorem 4.6, we deduced from Corollary
4.7 (ii) and Lemma 4.5 that $|I_{y}(e)|=1$ for $e\in E(H_{2})$ and
$\\{I_{y}(e)\mid e\in E(H_{2})\\}$ is a partition of $[k]$. For any $e\in
E(H_{2})$, write $e=\\{x,y\\}$. Choosing the unique vertex $i\in I_{y}(e)$, we
have $x_{(i)}=1$ and $x_{(t)}=2$ for each $t\in[k]\setminus\\{i\\}$, as
desired. $\hfill\Box\vskip 6.0pt plus 2.0pt minus 2.0pt$

To investigate $\overline{K}_{[k]}$-minimal graphs, we observe that

$[2]^{k}_{\overline{K}_{[k]}(i)}(2)=[2]^{k}_{i}(2),$ (7)

and for each $x\in[2]^{k}$, we have

$J_{x}=\\{i\in[k]\mid x_{(i)}=2\\}.$ (8)

###### Example 4.10

Define $\mathbb{R}_{k}$ as the graph with the vertex set $[2]^{k}$ and the
edge set

$E(\mathbb{R}_{k})=\\{\\{x,y\\}\mid x,y\in[2]^{k},x_{(i)}\neq y_{(i)}\text{
for each }i\in[k]\\}.$

Then $\mathbb{R}_{k}$ is a $\overline{K}_{[k]}$-minimal graph with size
$2^{k-1}$.

Proof. Noting that $E(\mathbb{R}_{k})$ is a matching, we infer that
$\mathbb{R}_{k}$ has size $2^{k-1}$ and each vertex is covered by a unique
edge in $\mathbb{R}_{k}$. Observing that
$L_{i}(\mathbb{R}_{k})=E(\mathbb{R}_{k})$ for each $i\in[k]$, we conclude that
$\mathbb{R}_{k}$ is $\overline{K}_{[k]}$-minimal from Lemma 4.4 and (7).
$\hfill\Box\vskip 6.0pt plus 2.0pt minus 2.0pt$

###### Remark 4

Actually, if $H_{1}$ has an isolated vertex, then $\mathbb{R}_{k}$ is
$H_{1}$-minimal. However, if $\overline{K}_{[k]}\prec H_{1}$, then
$H_{1}\circ\mathbb{R}_{k}$ is not a minimal graph in $\mathcal{B}_{k}$.

Given a graph $G$, the Cartesian product of $s$ copies of $G$ is the graph
$G^{\Box s}$ with the vertex set

$V(G^{\Box s})=\\{(x_{(1)},\ldots,x_{(s)})\mid x_{(i)}\in V(G)\text{ for
}i\in[s]\\},$

where two vertices $x$ and $y$ are adjacent if and only if there exists an
index $i\in[s]$ such that $\\{x_{(i)},y_{(i)}\\}\in E(G)$ and
$x_{(j)}=y_{(j)}$ for all indices $j\in[s]\setminus\\{i\\}$.

###### Example 4.11

Let $P_{2}$ be the graph with the vertex set $\\{1,2\\}$ and the edge set
$\\{\\{1,2\\}\\}$. Then $P_{2}^{\Box k}$ is a $\overline{K}_{[k]}$-minimal
graph with size $k\cdot 2^{k-1}$.

Proof. It is routine to verify that $|E(P_{2}^{\Box k})|=k\cdot 2^{k-1}$. For
an edge $\\{x,y\\}$ in $P_{2}^{\Box k}$ with $(x_{(i)},y_{(i)})=(1,2)$, by
(7), we have $I_{x}(\\{x,y\\})=\emptyset$ and $I_{y}(\\{x,y\\})=\\{i\\}$, and
so $\tilde{I}_{y}(\\{x,y\\})=\\{i\\}$. By Lemma 4.5 and (8), we conclude that
$P_{2}^{\Box k}$ is $\overline{K}_{[k]}$-minimal. $\hfill\Box\vskip 6.0pt plus
2.0pt minus 2.0pt$

###### Corollary 4.12

If $H_{2}$ is $\overline{K}_{[k]}$-minimal, then $2^{k-1}\leq|E(H_{2})|\leq
k\cdot 2^{k-1}$,

(i) with the lower bound if and only if $H_{2}=\mathbb{R}_{k}$.

(ii) with the upper bound if and only if $H_{2}=P_{2}^{\Box k}$.

Proof. Since the degree of each vertex $i$ in $\overline{K}_{[k]}$ is $0$, by
Theorem 4.6, we have $2^{k-1}\leq|E(H_{2})|\leq k\cdot 2^{k-1}$.

(i) The “if” implication follows immediately from Example 4.10, while the
“only if” implication follows from (7) and Corollary 4.7 (i).

(ii) We get the sufficiency from Example 4.11. To prove the necessity, suppose
that the size of $H_{2}$ is $k\cdot 2^{k-1}$, as well as the upper bound in
Theorem 4.6 for $H_{1}=\overline{K}_{[k]}$. For $x\in[2]^{k}$, write
$\varepsilon(x)=\\{e\in E(H_{2})\mid I_{x}(e)\neq\emptyset\\}$. It follows
from (8) and Lemma 4.5 (i) that $\varepsilon(x)=\emptyset$ if and only if
$x=(1,\ldots,1)$. Observing that $\tilde{I}_{x}(e)\subseteq I_{x}(e)$, we have
derived from Lemma 4.5 (ii) that

$E(H_{2})=\bigcup_{x\in[2]^{k}}\\{e\in E(H_{2})\mid
I_{x}(e)\neq\emptyset\\}=\bigcup_{x\in[2]^{k}\setminus\\{(1,\ldots,1)\\}}\varepsilon(x).$

Pick any vertex $x\in[2]^{k}\setminus\\{(1,\ldots,1)\\}$. Combining Corollary
4.7 (ii) and Lemma 4.5 (i), we get $|I_{x}(e)|=1$ for any $e\in\varepsilon(x)$
and $\\{I_{x}(e)\mid e\in\varepsilon(x)\\}$ is a partition of $J_{x}$. For any
edge $e=\\{y,x\\}\in\varepsilon(x)$, taking the unique vertex $i\in I_{x}(e)$,
one has $(y_{(i)},x_{(i)})=(1,2)$ and $(y_{(t)},x_{(t)})=(2,2)$ for $t\in
J_{x}\setminus\\{i\\}$, and further by Corollary 4.7 (ii), we get
$I_{y}(e)=\emptyset$, and so $(y_{(t)},x_{(t)})=(1,1)$ for $t\in[k]\setminus
J_{x}$. Hence, we have $\varepsilon(x)\in E(P_{2}^{\Box k})$, and so
$E(H_{2})\subseteq E(P_{2}^{\Box k})$. It follows from
$|E(H_{2})|=|E(P_{2}^{\Box k})|$ that $H_{2}=P_{2}^{\Box k}$, as desired.
$\hfill\Box\vskip 6.0pt plus 2.0pt minus 2.0pt$

###  4.2 A poset on $\mathcal{C}_{k}$

In this subsection, we focus on the poset $(\mathcal{C}_{k},\preceq)$, and
always suppose that $H_{2}$ is a graph with the vertex set $[3]^{k}$. We begin
by constructing a graph on the set $[3]^{k}$. Let $\Gamma_{k}$ be the graph
with the vertex set $[3]^{k}$ and the edge set

$E(\Gamma_{k})=\\{\\{x,y\\}\mid x,y\in[3]^{k},\;x\neq
y,\;|x_{(i)}-y_{(i)}|\leq 1\text{ for each }i\in[k]\\}.$

###### Observation 4.13

$\Gamma_{k}=span(\bigcup_{i\in[k]}(E(C^{k}_{i})\cup E(D^{k}_{i})))$.

###### Theorem 4.14

Suppose that $\overline{K}_{[k]}\circ H_{2}\in\mathcal{C}_{k}$.

(i) Then $H_{2}\preceq\Gamma_{k}$.

(ii) If $H_{2}\preceq H_{2}^{\prime}\preceq\Gamma_{k}$, then
$\overline{K}_{[k]}\circ H_{2}^{\prime}\in\mathcal{C}_{k}$.

Proof. (i) Combining Proposition 2.4 (i) and Observation 4.13, we have
$E(H_{2})\subseteq E(\Gamma_{k})$, and so $H_{2}\preceq\Gamma_{k}$.

(ii) Observe that $E(H_{2}^{\prime})\subseteq E(\Gamma_{k})$,
$M_{i}(H_{2})\subseteq M_{i}(H_{2}^{\prime})$ and $N_{i}(H_{2})\subseteq
N_{i}(H_{2}^{\prime})$, where $M_{i}(H_{2})$ and $N_{i}(H_{2})$ are as refer
to (3) and (4), respectively. For each $i\in[k]$, by Observation 4.13, we have
$M_{i}(\Gamma_{k})=E(C^{k}_{i})$ and $N_{i}(\Gamma_{k})=E(D^{k}_{i})$, which
are $[3]^{k}_{i}(2)$-covering and $S^{k}_{i}$-covering, respectively. Hence,
the desired result follows from Proposition 2.4. $\hfill\Box\vskip 6.0pt plus
2.0pt minus 2.0pt$

###### Corollary 4.15

For any graph $\overline{K}_{[k]}\circ H_{2}\in\mathcal{C}_{k}$, we have
$|E(H_{2})|\leq\frac{7^{k}-3^{k}}{2},$ with equality if and only if
$H_{2}=\Gamma_{k}$.

Proof. Noting that $|x_{(i)}-y_{(i)}|\leq 1$ if and only if

$(x_{(i)},y_{(i)})\in\\{(1,1),(1,2),(2,1),(2,2),(2,3),(3,2),(3,3)\\},$

we have $|\\{(x,y)\mid x,y\in[3]^{k},|x_{(i)}-y_{(i)}|\leq 1\text{ for each
}i\in[k]\\}|=7^{k},$ which implies that
$|E(\Gamma_{k})|=\frac{7^{k}-3^{k}}{2}$. Hence, by Theorem 4.14, we get the
desired result. $\hfill\Box\vskip 6.0pt plus 2.0pt minus 2.0pt$

###### Corollary 4.16

For $G_{1},G_{2}\in\mathcal{C}_{k}$, we have $G_{1}\cup
G_{2}\in\mathcal{C}_{k}$. In particular, we have

$\bigcup\limits_{G\in\mathcal{C}_{k}}G=\overline{K}_{[k]}\circ\Gamma_{k}\in\mathcal{C}_{k}.$

Proof. Write $G_{1}=\overline{K}_{[k]}\circ H_{2}$ and
$G_{2}=\overline{K}_{[k]}\circ H_{2}^{\prime}$. Then $G_{1}\cup
G_{2}=\overline{K}_{[k]}\circ(H_{2}\cup H_{2}^{\prime})$. Hence, the desired
result follows from Theorem 4.14. $\hfill\Box\vskip 6.0pt plus 2.0pt minus
2.0pt$

The following result is immediate from Corollary 4.16.

###### Proposition 4.17

The poset $(\mathcal{C}_{k},\preceq)$ is a finite join-semilattice with the
maximum graph $\overline{K}_{[k]}\circ\Gamma_{k}$.

A graph $H_{2}$ is $k$-minimal if $\overline{K}_{[k]}\circ
H_{2}\in\mathcal{C}_{k}$ and $\overline{K}_{[k]}\circ
H_{2}^{\prime}\not\in\mathcal{C}_{k}$ for $H_{2}^{\prime}\prec H_{2}$.

###### Remark 5

A graph $H_{2}$ is $k$-minimal if and only if $\overline{K}_{[k]}\circ H_{2}$
is minimal in $\mathcal{C}_{k}$.

To study $k$-minimal graph, we give the following notation for convenience.

###### Notation 7

Write $X=[3]^{k}_{[k]}(\\{2,3\\})$, $Y=[3]^{k}_{[k]}(\\{1,3\\})$ and

$\overline{X}=[3]^{k}\setminus X,\qquad\overline{Y}=[3]^{k}\setminus Y,\qquad
Z=[3]^{k}\setminus(X\cup Y).$

We establish the bounds for the size of a $k$-minimal graph.

###### Theorem 4.18

If $H_{2}$ is $k$-minimal, then

$\displaystyle\frac{3^{k}+1}{2}\leq|E(H_{2})|\leq k\cdot(3^{k-1}+2^{k-1}).$

Proof. For $i\in[k]$, denote by $M^{\prime}_{i}$ (resp. $N^{\prime}_{i}$) the
set of edges $e$ in $M_{i}(H_{2})$ (resp. $N_{i}(H_{2})$) such that
$M_{i}(H_{2})\setminus\\{e\\}$ (resp. $N_{i}(H_{2})\setminus\\{e\\}$) is not a
$[3]^{k}_{i}(2)$-covering (resp. an $S^{k}_{i}$-covering), where
$M_{i}(H_{2})$ (resp. $N_{i}(H_{2})$) is as refer to (3) (resp. (4)). Then
$|M_{i}^{\prime}|\leq|[3]^{k}_{i}(2)|=3^{k-1}$ and
$|N^{\prime}_{i}|\leq|S^{k}_{i}|=2^{k-1}$. Since $H_{2}$ is $k$-minimal, it
follows from Proposition 2.4 that
$E(H_{2})=\bigcup_{i\in[k]}(M_{i}^{\prime}\cup N_{i}^{\prime}),$ and so

$|E(H_{2})|=|\bigcup_{i\in[k]}(M_{i}^{\prime}\cup
N_{i}^{\prime})|\leq\sum_{i\in[k]}(|M_{i}^{\prime}|+|N_{i}^{\prime}|)\leq
k\cdot(3^{k-1}+2^{k-1}).$ (9)

In the following, we prove the lower bound. Pick any vertex $x\in[3]^{k}$. We
shall find an edge $e_{x}$ in $H_{2}$ covering $x$ for the following two
cases.

Case 1. $x=(3,\ldots,3)$. Then $x\in S^{k}_{1}$. Note that
$\overline{K}_{[k]}\circ H_{2}\in\mathcal{C}_{k}$. By Proposition 2.4 (iii),
there exists at least one edge $e_{x}$ in $H_{2}$ covering $x$.

Case 2. $x\in\overline{Y}$. Then there is an index $i\in[k]$ with $x_{(i)}=2$.
By Proposition 2.4 (ii), there is an edge $e_{x}=\\{x,y\\}$ in $H_{2}$ such
that $y_{(i)}=1$, and so $y\in\overline{X}$.

Observing that $X=(X\cap\overline{Y})\cup\\{(3,\ldots,3)\\}$ and
$Z\subseteq\overline{Y}$, we choose two families of edges from the above two
cases:

$F_{X}=\\{e_{x}\mid x\in X\\}\qquad\text{and}\qquad F_{Z}=\\{e_{x}\mid x\in
Z\\}.$

By Case 2, the edge $e_{x}$ for $x\in X\cap\overline{Y}$ does not cover any
other vertices in $X$ except $x$, and so $|F_{X}|=|X|=2^{k}$. Noting that
$Z\subseteq\overline{X}$, we have derived that all of the vertices covered by
edges in $F_{Z}$ are in $\overline{X}$, which implies that $F_{X}\cap
F_{Z}=\emptyset$. Since each edge covers two vertices, one gets
$2|F_{Z}|\geq|Z|=3^{k}-2^{k+1}+1$ by a short calculation. Consequently, we
have

$|E(H_{2})|\geq|F_{X}\cup F_{Z}|=|F_{X}|+|F_{Z}|\geq
2^{k}+\frac{3^{k}-2^{k+1}+1}{2}=\frac{3^{k}+1}{2},$ (10)

as desired. $\hfill\Box\vskip 6.0pt plus 2.0pt minus 2.0pt$

###### Remark 6

If $\overline{K}_{[k]}\circ H_{2}$ is minimal in $\mathcal{C}_{k}$, then by
the equation (1), Remark 5 and Theorem 4.18, we have

$\frac{(2k+3)\cdot 3^{k-1}+1}{2}\leq|E(\overline{K}_{[k]}\circ H_{2})|\leq
2k\cdot(3^{k-1}+2^{k-2}).$

To characterize the lower bound in Theorem 4.18, we define a graph on
$[3]^{k}$.

###### Example 4.19

Define $\mathbb{T}_{k}$ as the graph with the vertex set $[3]^{k}$ and the
edge set $E(\mathbb{T}_{k})=E_{X}\cup E_{Z}$, where

$\begin{array}[]{rcl}E_{X}&=&\\{\\{x,y\\}\mid x\in
X,y\in[3]^{k},\;x_{(i)}-y_{(i)}=1\text{ for each }i\in[k]\\},\\\
E_{Z}&=&\\{\\{x,y\\}\mid x,y\in Z,\;x_{(i)}=y_{(i)}=3\text{ or
}\\{x_{(i)},y_{(i)}\\}=\\{1,2\\}\text{ for each }i\in[k]\\}.\end{array}$

Then $\mathbb{T}_{k}$ is a $k$-minimal graph with size $\frac{3^{k}+1}{2}$.

Proof. We first compute $|E(\mathbb{T}_{k})|$. Since there is a bijection from
$X$ to $E_{X}$, one has $|E_{X}|=|X|=2^{k}$. Each vertex in $Z$ is covered by
a unique edge in $E_{Z}$, so $E_{Z}$ is a matching in $Z$, which implies that

$|E_{Z}|=\frac{|Z|}{2}=\frac{3^{k}-2^{k+1}+1}{2}.$

Noting that $E_{Z}$ does not cover any vertex in $X$, we have $E_{X}\cap
E_{Z}=\emptyset$. Hence, we get
$|E(\mathbb{T}_{k})|=|E_{X}|+|E_{Z}|=\frac{3^{k}+1}{2}$.

The next thing is to prove
$\overline{K}_{[k]}\circ\mathbb{T}_{k}\in\mathcal{C}_{k}$. Take any index
$i\in[k]$ and then pick any vertex $x\in[3]^{k}_{i}(2)\cup S_{i}^{k}$. If
$x\in X$, let $y$ be a vertex in $[3]^{k}$ such that $y_{(t)}=x_{(t)}-1$ for
each $t\in[k]$, then $\\{x,y\\}\in E_{X}\cap E(C^{k}_{i})$ or $E_{X}\cap
E(D^{k}_{i})$ according to $x\in[3]^{k}_{i}(2)$ or $S_{i}^{k}$. If
$x\in\overline{X}$, then $x\in Z$, and so $\\{x,y\\}\in E_{Z}\cap
E(C^{k}_{i})$, where $y$ is a vertex in $Z$ such that

$y_{(t)}=\left\\{\begin{array}[]{ll}2,&\text{if }x_{(t)}=1,\\\ 1,&\text{if
}x_{(t)}=2,\\\ 3,&\text{if }x_{(t)}=3.\end{array}\right.$

Therefore, we have derived that $M_{i}(H_{2})$, as refer to (3), is a
$[3]^{k}_{i}(2)$-covering and $N_{i}(H_{2})$, as refer to (4), is an
$S^{k}_{i}$-covering. Observing that $E_{X}\cup
E_{Z}\subseteq\bigcup_{i\in[k]}(E(C^{k}_{i})\cup E(D^{k}_{i}))$, we get
$\overline{K}_{[k]}\circ H_{2}\in\mathcal{C}_{k}$ from Proposition 2.4.

Finally, we show that $\mathbb{T}_{k}$ is $k$-minimal. By contradiction, if
$\mathbb{T}_{k}$ is not $k$-minimal, then there is a graph
$H_{2}\prec\mathbb{T}_{k}$ such that $\overline{K}_{[k]}\circ
H_{2}\in\mathcal{C}_{k}$, and so
$|E(H_{2})|<|E(\mathbb{T}_{k})|=\frac{3^{k}+1}{2}$, contrary to Theorem 4.18.
This contradiction implies that $\mathbb{T}_{k}$ is minimal.

The proof is complete. $\hfill\Box\vskip 6.0pt plus 2.0pt minus 2.0pt$

We use the following result to characterize the lower bound in Theorem 4.18.

###### Corollary 4.20

The lower bound in Theorem 4.18 is attained if and only if
$H_{2}=\mathbb{T}_{k}$.

Proof. The “if” implication follows from Example 4.19. To obtain the “only if”
implication, let $H_{2}$ be a $k$-minimal graph with size $\frac{3^{k}+1}{2}$.
With references to the proof of Theorem 4.18, we have derived from (10) that

$E(H_{2})=F_{X}\cup
F_{Z},\quad|F_{X}|=2^{k}=|E_{X}|\quad\text{and}\quad|F_{Z}|=\frac{|Z|}{2}=|E_{Z}|.$

It follows from Proposition 2.4 that $F_{X}=E_{X}$ and $F_{Z}=E_{Z}$, as
desired. $\hfill\Box\vskip 6.0pt plus 2.0pt minus 2.0pt$

To characterize the upper bound in Theorem 4.18, we give the following
notation.

###### Notation 8

For $i\in[k]$ and $x\in[3]_{i}^{k}(2)\cup S_{i}^{k}$, denote by
$\epsilon_{i}(x)$ the set of edges $e=\\{x,x^{\prime}\\}$ such that
$x^{\prime}_{(i)}=x_{(i)}-1$ and for each $t\in[k]\setminus\\{i\\}$, one of
the following conditions holds.

(i) If $x\in S_{i}^{k}$, then $x^{\prime}_{(t)}=x_{(t)}$.

(ii) If $x\in X\cap[3]_{i}^{k}(2)$, then

$x^{\prime}_{(t)}=\left\\{\begin{array}[]{ll}2\text{ or }3,&\text{if
}x_{(t)}=2,\\\ 3,&\text{if }x_{(t)}=3.\end{array}\right.$

(iii) If $x\in\overline{X}\cap[3]_{i}^{k}(2)$, then

$x^{\prime}_{(t)}=\left\\{\begin{array}[]{ll}1,&\text{if }x_{(t)}=1,\\\
2\text{ or }3,&\text{if }x_{(t)}=2\text{ or }3.\end{array}\right.$

###### Lemma 4.21

Let $i,j\in[k]$. Pick $x\in[3]_{i}^{k}(2)\cup S_{i}^{k}$ and
$y\in[3]_{j}^{k}(2)\cup S_{j}^{k}$. If $(i,x)\neq(j,y)$, then
$\epsilon_{i}(x)\cap\epsilon_{j}(y)=\emptyset$.

Proof. Suppose for the contrary that
$\epsilon_{i}(x)\cap\epsilon_{j}(y)\neq\emptyset$. Take
$e\in\epsilon_{i}(x)\cap\epsilon_{j}(y)$.

Case 1. $i=j$. Then $x\neq y$ and $e=\\{x,y\\}$, which implies that
$y_{(i)}=x_{(i)}-1$ and $x_{(i)}=y_{(i)}-1$, a contradiction.

Case 2. $i\neq j$ and $x=y$. Write $e=\\{x,x^{\prime}\\}$. Then

$x^{\prime}_{(i)}=x_{(i)}-1\quad\text{and}\quad x^{\prime}_{(j)}=x_{(j)}-1.$

Note that $e\in\epsilon_{i}(x)$. If $x\in S_{i}^{k}$ or $X\cap[3]_{i}^{k}(2)$,
then $x^{\prime}_{j}\geq x_{j}$, a contradiction. If
$x\in\overline{X}\cap[3]_{i}^{k}(2)$, then $(x^{\prime}_{(j)},x_{(j)})=(2,3)$,
which implies that $x\in S^{k}_{j}$, and so $x\in X$, a contradiction.

Case 3. $i\neq j$ and $x\neq y$. Then $e=\\{x,y\\}$, and so

$y_{(i)}=x_{(i)}-1\quad\text{and}\quad y_{(j)}=x_{(j)}+1.$

If $x\in S_{i}^{k}$, then $y_{(j)}=x_{(j)}$, a contradiction. Now suppose
$x\in[3]_{i}^{k}(2)$. Then $y_{(i)}=1$ and $(x_{(j)},y_{(j)})=(2,3)$. Noting
that $\\{x,y\\}\in\epsilon_{j}(y)$, we have $y\in S^{k}_{j}$, and so
$x_{(i)}=y_{(i)}$, a contradiction.

We accomplish the proof. $\hfill\Box\vskip 6.0pt plus 2.0pt minus 2.0pt$

###### Example 4.22

Define

$\mathcal{Q}_{k}=\\{span(\bigcup_{i\in[k]}\;\bigcup_{x\in[3]_{i}^{k}(2)\cup
S_{i}^{k}}\\{e_{i}(x)\\})\mid e_{i}(x)\in\epsilon_{i}(x)\\}.$

Then each graph in $\mathcal{Q}_{k}$ is a $k$-minimal graph with size
$k\cdot(3^{k-1}+2^{k-1})$.

Proof. Choose any graph $H_{2}\in\mathcal{Q}_{k}$. Observe that
$\epsilon_{i}(x)\subseteq E(C^{k}_{i})\cup E(D^{k}_{i})$. Noting that
$E(H_{2})\cap\epsilon_{i}(x)$ has exactly one edge, as well as the unique edge
covering $x$ in $M_{i}(H_{2})$ or $N_{i}(H_{2})$ according to
$x\in[3]^{k}_{i}(2)$ or $S^{k}_{i}$, we deduce that $H_{2}$ is $k$-minimal
from Proposition 2.4 and Lemma 4.21. By Lemma 4.21 again, one has

$|E(H_{2})|=k\cdot(|[3]^{k}_{i}(2)|+|S^{k}_{i}|)=k\cdot(3^{k-1}+2^{k-1}),$

as desired. $\hfill\Box\vskip 6.0pt plus 2.0pt minus 2.0pt$

###### Remark 7

Let $P_{3}$ be the graph with the vertex set $\\{1,2,3\\}$ and the edge set
$\\{\\{1,2\\},\\{2,3\\}\\}$. Let $\mathbb{Q}_{k}$ be the graph obtained from
the Cartesian product $P_{3}^{\Box k}$ by deleting the edges
$\\{x,x^{\prime}\\}$ such that there exist indices $i$ and $j$ in $[k]$ with
$(x_{i},x^{\prime}_{i})=(2,3)$ and $x_{j}=x^{\prime}_{j}=1$. Then
$\mathbb{Q}_{k}\in\mathcal{Q}_{k}$.

We use the following result to characterize the upper bound in Theorem 4.18.

###### Corollary 4.23

The upper bound in Theorem 4.18 is attained if and only if
$H_{2}\in\mathcal{Q}_{k}$.

Proof. We get the sufficiency from Example 4.22. To prove the necessity, let
$H_{2}$ be a $k$-minimal graph with size $k\cdot(3^{k-1}+2^{k-1})$. With
references to the proof of Theorem 4.18, we have derived from (9) that

$|M^{\prime}_{i}|=3^{k-1}=|[3]^{k}_{i}(2)|,\qquad|N^{\prime}_{i}|=2^{k-1}=|S^{k}_{i}|,$
(11)

and the following condition.

(A) All sets $M_{i}^{\prime}$’s and $N_{i}^{\prime}$’s are pairwise non-
intersecting.

Take any $x\in[3]^{k}_{i}(2)\cup S_{i}^{k}$. By (11), there is a unique edge
$f_{i}(x)$ covering $x$ in $M^{\prime}_{i}$ or $N^{\prime}_{i}$ according to
$x\in[3]^{k}_{i}(2)$ or $S_{i}^{k}$. Note that
$E(H_{2})=\bigcup_{i\in[k]}(M_{i}^{\prime}\cup N^{\prime}_{i})$. To get the
desired result, we only need to prove $f_{i}(x)\in\epsilon_{i}(x)$.

Suppose for the contrary that $f_{i}(x)\not\in\epsilon_{i}(x)$. It is routine
to verify that there is an index $t\in[k]\setminus\\{i\\}$ such that either
$(x,f_{i}(x))\in[3]^{k}_{t}(2)\times E(C^{k}_{t})$ or $(x,f_{i}(x))\in
S^{k}_{t}\times E(D^{k}_{t})$. Then $f_{i}(x)\in M_{t}(H_{2})$ or
$N_{t}(H_{2})$ according to $x\in[3]^{k}_{t}(2)$ or $S^{k}_{t}$. Noting that
$M_{t}^{\prime}\subseteq M_{t}(H_{2})$ and $N_{t}^{\prime}\subseteq
N_{t}(H_{2})$, by the definitions of $M_{t}^{\prime}$ and $N_{t}^{\prime}$ in
Theorem 4.18, we get $f_{t}(x)=f_{i}(x)$, which contradicts (A). This
contradiction completes the proof. $\hfill\Box\vskip 6.0pt plus 2.0pt minus
2.0pt$

##  5 Perfectness-resolvable

We begin this section by computing the diameters of graphs in
$\mathcal{B}_{k}$ or $\mathcal{C}_{k}$.

###### Proposition 5.1

(i) The diameter of any graph in $\mathcal{B}_{k}$ is $2$ or $3$.

(ii) The diameter of any graph in $\mathcal{C}_{k}$ is $3$, $4$ or $5$.

Proof. (i) Choose any graph $H\in\mathcal{B}_{k}$. Pick $i,j\in[k]$. By Lemma
3.1 (i), we have $d(i,z)=z_{(i)}$ for each $z\in[2]^{k}$, and so

$d(i,j)\leq d(i,(1,\ldots,1))+d(j,(1,\ldots,1))=1+1=2.$

For distinct vertices $x,y\in[2]^{k}$, there exists a vertex $t\in[k]$ such
that $x_{(t)}=1$ or $y_{(t)}=1$. Hence, we have

$d(x,y)\leq d(t,x)+d(t,y)\leq 1+2=3.$

Since $d(i,(2,\ldots,2))=2$, the diameter of $H$ is $2$ or $3$.

(ii) An argument similar to the proof of (i) shows that (ii) holds.
$\hfill\Box\vskip 6.0pt plus 2.0pt minus 2.0pt$

###### Remark 8

(i) The diameters of $K_{[k]}\circ K_{[2]^{k}}$ and
$K_{[k]}\circ\mathbb{U}_{2}$ are $2$ and $3$, respectively.

(ii) The diameters of $\overline{K}_{[k]}\circ\Gamma_{k}$,
$\overline{K}_{[k]}\circ\mathbb{Q}_{2}$ and
$\overline{K}_{[k]}\circ\mathbb{T}_{2}$ are $3$, $4$ and $5$, respectively.

Given a graph $G$, the metric dimension of $G$, denoted by $\dim(G)$, is the
minimum cardinality of a resolving set of $G$. A metric basis of $G$ is a
resolving set of $G$ with cardinality $\dim(G)$. A metric basis of $G$ is
perfect if it is a completeness-resolving set. We say that $G$ is perfectness-
resolvable if it admits a perfect metric basis. Clearly, a perfectness-
resolvable graph is completeness-resolvable.

###### Observation 5.2

(i) All paths are perfectness-resolvable.

(ii) A graph in $\mathcal{K}$ is perfectness-resolvable if and only if it is
complete.

###### Proposition 5.3

(i) Let $G$ be a graph in $\mathcal{B}_{k}$. If the diameter of $G$ is $2$,
then $G$ is perfectness-resolvable.

(ii) Let $G$ be a graph in $\mathcal{C}_{k}$. If the diameter of $G$ is $3$,
then $G$ is perfectness-resolvable.

Proof. By [4, Theorem 1], we have $|V(G)|\leq\dim(G)+d^{\dim(G)}$, where $d$
is the diameter of $G$. Note that $|V(G)|$ is equal to $k+2^{k}$ or $k+3^{k}$
according to $G\in\mathcal{B}_{k}$ or $\mathcal{C}_{k}$. Hence, one has
$k\leq\dim(G)$ if the condition in (i) or (ii) holds. Since $[k]$ is a
completeness-resolving set of graphs in $\mathcal{B}_{k}\cup\mathcal{C}_{k}$,
the two desired results follow. $\hfill\Box\vskip 6.0pt plus 2.0pt minus
2.0pt$

We conclude the paper by raising the following problem.

Problem 2. Which graphs are perfectness-resolvable?

## Acknowledgements

Feng was supported by the National Natural Science Foundation of China
(11701281), the Natural Science Foundation of Jiangsu Province (BK20170817)
and the Grant of China Postdoctoral Science Foundation. Ma was supported by
the National Natural Science Foundation of China (11801441) and the Young
Talent fund of University Association for Science and Technology in Shanxi,
China (20190507). Xu was supported by the National Natural Science Foundation
of China (61673218) and the Postgraduate Research & Practice Innovation
Program of Jiangsu Province (KYCX18_0376 and KYCX19_0253).

## References

  * [1] R.F. Bailey and P.J. Cameron, Base size, metric dimension and other invariants of groups and graphs, Bull. Lond. Math. Soc. 43 (2011) 209–242.
  * [2] Z. Beerliova, F. Eberhard, T. Erlebach, A. Hall, M. Hoffmann, M. Mihal’ák and L.S. Ram, Network discovery and verification, IEEE J. on Selected Areas in Communications 24 (2006) 2168–2181.
  * [3] J. Cáceres, C. Hernando, M. Mora, I.M. Pelayo, M.L. Puertas, C. Seara and D.R. Wood, On the metric dimension of Cartesian products of graphs, SIAM J. Discrete Math. 21 (2007) 423–441.
  * [4] G. Chartrand, L. Eroh, M. A. Johnson and O. R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105 (2000) 99–113.
  * [5] V. Chvátal, Mastermind, Combinatorica 3 (1983) 325–329.
  * [6] F. Harary and R.A. Melter, On the metric dimension of a graph, Ars Combinatoria 2 (1976) 191–195.
  * [7] Z. Jiang and N. Polyanskii, On the metric dimension of Cartesian powers of a graph, J. Combin. Theory Ser. A 165 (2019) 1–14.
  * [8] S. Khuller, B. Raghavachari and A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math. 70 (1996) 217–229.
  * [9] A. Sebő and E. Tannier, On metric generators of graphs, Math. Oper. Res. 29 (2004) 383–393.
  * [10] P.J. Slater, Leaves of trees, Congr. Numerantium 14 (1975) 549–559.