# Quantum Keyless Privacy vs. Quantum Key Distribution for Space Links

A. Vázquez-Castro1 D. Rusca2 H. Zbinden2 1Autonomous University of Barcelona
and Center of Space Studies and Research, CERES (IEEC-UAB). Campus de
Bellaterra, 08290 Barcelona, Spain
2Group of Applied Physics, Univ. of Geneva, Chemin de Pinchat 22, CH-1211
Geneva 4, Switzerland

###### Abstract

We study information theoretical security for space links between a satellite
and a ground-station. Quantum key distribution (QKD) is a well established
method for information theoretical secure communication, giving the
eavesdropper unlimited access to the channel and technological resources only
limited by the laws of quantum physics. But QKD for space links is extremely
challenging, the achieved key rates are extremely low, and day-time operating
impossible. However, eavesdropping on a channel in free-space without being
noticed seems complicated, given the constraints imposed by orbital mechanics.
If we also exclude eavesdropper’s presence in a given area around the emitter
and receiver, we can guarantee that he has only access to a fraction of the
optical signal. In this setting, quantum keyless private (direct)
communication based on the wiretap channel model is a valid alternative to
provide information theoretical security. Like for QKD, we assume the
legitimate users to be limited by state-of-the-art technology, while the
potential eavesdropper is only limited by physical laws: physical measurement
(Helstrom detector) and quantum electrodynamics (Holevo bound). Nevertheless,
we demonstrate information theoretical secure communication rates (positive
keyless private capacity) over a classical-quantum wiretap channel using on-
off-keying of coherent states. We present numerical results for a setting
equivalent to the recent experiments with the Micius satellite and compare
them to the fundamental limit for the secret key rate of QKD. We obtain much
higher rates compared with QKD with exclusion area of less than 13 meters for
Low Earth Orbit (LEO) satellites. Moreover, we show that the wiretap channel
quantum keyless privacy is much less sensitive to noise and signal dynamics
and daytime operation is possible.

††preprint: APS/123-QED

##  I Introduction

The first protocol of Quantum Key Distribution (QKD) was proposed in 1984 by
Bennet and Brassard BB1984 . Today, commercial fiber-based systems are
available with operational distances steadily increasing Zbinden2018 Fang2020
. Recently, QKD has also been realized between the Chinese satellite Micius
and ground-stations Micius2017 Micius2020 . Currently, there are several
national initiatives to deploy a QKD network, including terrestrial and space
links. In particular, there is an increasing and unprecedented interest in
space telecommunication networks; our scenarios of interest as illustrated in
Fig. 1, (this work focuses on the blue link).

A QKD protocol assumes that two distant legitimate parties, Alice and Bob have
at their disposal the following resources: Secure offices, access to an
untrusted quantum channel and an authenticated classical public channel, and
perfectly random numbers. A potential eavesdropper, Eve, has the complete
control of the quantum channel. In particular, she can intercept all quantum
states and perform any measurement allowed by quantum mechanics, including
entangling the states with some auxiliary system and store them in perfect
quantum memories. Moreover, she can send signals to Bob over a lossless
channel. Despite this extreme power only limited by the laws of quantum
physics, QKD protocols are now well established and furnished with security
proofs Shor2000 Mayers2001 Kato2016 Curty2019 . So the generated keys
guarantee together with the encoding using the one-time-pad information
theoretically secure communication Renner2005 Scarani2009 .

Figure 1: Our scenarios of interest: celestial mechanics dictates orbit
dynamics for legitimate parties and eavesdroppers.

Alternatively, physical-layer-security relies also on information theoretical
principles in the sense that Eve has unlimited computing power. However, she
has a physical disadvantage with respect to the legitimate users. In
particular, Eve can intercept only a fraction of the signal sent by Alice. In
1975, Wyner first proposed a protocol based on a so-called degraded wiretap
channel (for a classical channel)Wyner1975 WynerPoisson WynerPoisson-1 . The
information leakage to the eavesdropper is determined with an information
theoretical measure, which has been strengthened from Wyner’s (weak) security
to the so called strong security criterion by I. Csiszár and J. Körner,
Csiszar1978  and Maurer Maurer1993  until achieving cryptographic semantic
security Bellare2012 . In a quantum setting, where Alice and Bob use an
authenticated quantum channel for (keyless) secure direct communication, the
asymptotically achievable rate, the private capacity, subject to the strong
security criterion, was determined by Cai, Winter and Yeung in Cai2004  and
Devetak in Devetak2005 Devetak2005-1 .

On the one hand, QKD with satellites is extremely challenging due to the small
signal strength of the order of one photon per pulse, the high channel loss,
delays due to the iterative protocol, and the sensitivity to background noise,
which does not allow key exchanges during daytime. On the other hand,
eavesdropping without being noticed seems to be very complicated as well in a
free-space scenario. So it makes a lot of sense to consider a few reasonable
assumptions which limit the power of Eve. Indeed, due to the laws of celestial
mechanics a satellite cannot be parked in the line of sight between Alice’s
satellite and Bob’s ground-station (or satellite), which prevents intercept
and resend attacks. Eve could position her satellite very close or eventually
attach it to Alice’s satellite. This would allow Eve to exploit side channels
(e.g. monitoring electronic signals), but this scenario is excluded in QKD
which relies by definition on secure offices. Similarly, Eve could place a
telescope close to Bob’s but again we may introduce an exclusion region under
control of Bob, within which Eve cannot install a big telescope.

There is some initial work investigating the consequences of restricted power
for Eve on the performance of QKD links Shapiro2019 Shapiro2019-1 Ling2019
Fujiwara2018 . However, given their additional, reasonable assumptions, we
find exactly the scenario where keyless private communication is possible.
This type of secret transmission and its practical comparison with QKD have
been studied in Endo2015 Endo2016 , however, without assuming a quantum
channel.

In this paper, we show that physical layer encryption is a reasonable choice
for satellite communication over the quantum space channel. In Section II, we
introduce the one-way wiretap protocol and identify its asymptotic
information-theoretical secure and reliable rate: the private capacity. In
Section III, we propose a simple yet accurate channel model using binary
modulated coherent states (on-off keying, OOK) and derive and analyze the
private capacity for Bob using realistic, state-of-the-art photon counting
detectors while the signal reception by Eve being only limited by the laws of
physics. Finally, we present numerical results for a realistic scenario taking
the performance of the Micius system as a reference and compare it to the
fundamental limit for the secret key rate of QKD PLOB2017 .

##  II Description of the protocol

Our protocol is based on the one-way wiretap protocol Wyner1975 Csiszar1978
where secret bits are channel encoded and sent over $n$ uses of the optical
channel. We assume OOK for lighter analytical treatment, but other binary
modulations can be used e.g. Binary Phase Shift Keying (BPSK).

The protocol contains the following steps.

  1. 1.

Encoding. Alice, the legitimate information transmitter, sends a stream of
secret information bits (any data, video, pictures, etc.) to a stochastic
wiretap encoder. Information-theoretically, this encoding is described as
Alice selects a codeword $X^{n}$ to send her secret message $M$. The signal is
meant for Bob, but part of it is leaked to the environment represented by the
omnipresent Eve. The secrecy depends on the structure of this encoder, which
is characterized by the rate $R=k/n$ (where $k$ is the number of secret bits),
the error probability, $\epsilon_{n}$, and a security measure, $\delta_{n}$.

  2. 2.

State Preparation. For each use of the channel, the legitimate information
transmitter (Alice), prepares a coherent state modulated by the random
variable $X\in\mathcal{X}=\\{0,1\\}$, where $X=0$ with probability $q$ and
$X=1$ with probability $1-q$. The OOK states transmitted by Alice are the
vacuum state, $\ket{\alpha_{0}}=\ket{0}$, and

$\displaystyle\ket{\alpha_{1}}$
$\displaystyle=e^{-\frac{1}{2}|\alpha_{1}|^{2}}\sum_{n=0}^{\infty}\frac{\alpha_{1}^{n}}{(n!)^{1/2}}\ket{n}.$
(1)

The probability $q$ is not decided _a priori_ as part of the protocol, it
needs to be optimized depending on the assumptions at the detection and the
physical propagation channel (Section III).

  3. 3.

Measurement. After $n$ transmissions over the quantized propagating field, Bob
receives $B^{n}$ and Eve $E^{n}$. Bob estimates his received coherent state
after measuring the arriving light and obtains $Y^{n}$. He disposes of state-
of-the-art detectors. Eve may apply the best quantum detection strategy to
obtain $Z^{n}$.

  4. 4.

Decoding. Bob and Eve send their estimated received states to the decoder. The
concrete construction of encoder and decoder are assumed to be publicly known.
The values of $\epsilon_{n}$ and $\delta_{n}$ depend on the choice of this
code.

According to the wiretap theory, even if the eavesdropper is computationally
unbounded, the wiretap code ensures that if $R$ is an achievable rate, both
$\epsilon_{n}$ and $\delta_{n}$ (after decoding) tend to zero for large $n$,

$\displaystyle\lim_{n\rightarrow\infty}\epsilon_{n}=\lim_{n\rightarrow\infty}\delta_{n}$
$\displaystyle=0,$ (2)

which means that the error probability and the information leakage towards Eve
can be made arbitrarily low. Upper bounds are also known for the speed of
convergence rate of leaked information Hayashi2015 . Hence, the protocol
jointly provides information-theoretical reliable and secure communication.
The supremum of all such rates is called the private capacity and for the
classical-quantum wiretap channel subject to the strong security criterion,
has been determined in Cai2004 Devetak2005 . The meaning of strong security is
that, given a uniform distribution of the message to be transmitted through
the channel, the eavesdropper shall obtain no information about it Maurer1994
. This criterion is the most common security criterion in classical and
quantum information theory. The metric of strong security is the amount of
mutual information leaked to Eve.

When Bob’s channel is degradable, the private capacity of the quantum wiretap
protocol (with quantum channel and information) is Devetak2005-1 Smith2008
Wilde2018

$\displaystyle
C_{P}(\mathcal{N})=\sup_{\rho_{in}}I_{c}(\rho_{in},\mathcal{N}),$ (3)

where $\rho_{in}$ is the input density matrix and
$I_{c}(\rho_{in},\mathcal{N})$ is the coherent information defined as

$\displaystyle
I_{c}(\rho_{in},\mathcal{N})=S(\mathcal{N}_{B}(\rho_{in})-S(\mathcal{N}_{E}(\rho_{in})),$
(4)

with $S$ the von Neumann entropy. In the next sections we characterize the
degradable channel of our practical (energy-constrained) protocol over space
links, which we use to derive the private capacity.

Figure 2: The main channel and the wiretap channel (top) and the information-
theoretical representation of the degraded classical-quantum channel (bottom).

The (physical) description of our protocol is illustrated in Fig. 2 (top). The
figure shows encoded bits modulating coherent states, the quantum channel
$\mathcal{N}=(\mathcal{N}_{B},\mathcal{N}_{E})$, the resulting classical
channel after detection $N=(N_{B},N_{E})$ as well as the information
theoretical representation (bottom).

##  III Calculation of the private capacity $C_{P}$

First, we build a model for the classical-quantum channel of our protocol. The
legitimate transmitter, Alice, is on a satellite while the legitimate
receiver, Bob, is on Earth. We assume a single-mode free-space quantum bosonic
channel (for the wiretap channel in the semi-classical regime see Hayashi2020
). The overall efficiency of Bob’s channel is $\eta$. The coefficient
$\gamma\in(0,1)$ characterizes the channel degradation. Hence, the efficiency
of Eve’s channel is $\gamma\eta$.

According to step 2 of our protocol, the received states are simply the
vacuum, or $\ket{\sqrt{\eta}\alpha_{1}}$ and
$\ket{\sqrt{\eta\gamma}\alpha_{1}}$ for Bob and Eve respectively. The wiretap
channel transition probabilities depend on the coherent states received by Bob
and Eve and by their detection strategies. For practical purposes, we assume
Bob uses standard single photon detectors, i.e. a threshold detector. For Bob,
we also take into account limited detection efficiency (included in $\eta$,
see Appendix D) and noise (dark counts probability $p_{dark}$ and stray light
with a Poisson photon number distribution and average $\eta_{0}\Delta$). The
conditional probabilities that Bob detects $y$ given that Alice sent $x$ are
illustrated in Fig. 3 with $\epsilon_{0}=(1-p_{dark})e^{-\eta_{o}\Delta}$ and
$\epsilon_{1}=(1-p_{dark})e^{-(\eta\mu+\eta_{o}\Delta)}$, where we have
denoted $\mu=|\alpha_{1}|^{2}$.

Eve instead performs an optimal quantum detection. For the single observation,
this leads to the optimal error probability $\epsilon^{*}$, which can be
calculated as (Hayashi2006, , Lemma 3.1)Audenaert2007 Audenaert2008 ,

$\displaystyle\epsilon^{*}$
$\displaystyle=\min_{0\leq\Pi\leq\mathbf{1}}[q\Tr(\mathbf{1}-\Pi)\rho_{1}+(1-q)\Tr\Pi\rho_{0})]$
(5) $\displaystyle=\frac{1}{2}-\frac{1}{2}\norm{q\rho_{1}-(1-q)\rho_{0}}_{1},$
(6)

where $\norm{}_{1}$ stands for trace norm. In the binary source scenario, this
bound is achieved by the Holevo-Helstrom projector Helstrom1976 Holevo1978 ,
for which several practical implemetations have been proposed such as the
Kennedy receiver Kennedy1973 , the Dolinar receiver Dolinar1973  or the
Sasaki-Hirota receiver Takeoka2008 Tsujino2011 . The optimal error probability
of Eve resulting from (5), becomes

$\displaystyle\epsilon^{*}(\gamma)=(1-\sqrt{1-4q(1-q)e^{-\eta\gamma\mu}})/2.$
(7)

Figure 3: Probabilistic detection models assumed for Bob and Eve to obtain $Y$
and $Z$, respectively.

The private capacity for our wiretap channel model coincides with the
classical secrecy capacity and is defined as

$\displaystyle C_{P}(\gamma)$
$\displaystyle=\max_{q}\\{I(X;Y)-I(X;Z|\gamma)\\},$ (8)

where $I(X,Y)$ is the Shannon mutual information of Alice using a state-of-
the-art photon counting detector and $I(X;Z|\gamma)$ is the maximum Shannon
mutual information that Eve can physically detect. For our setting as
presented in Section IV, a uniform input probability (i.e. $q=0.5$) is very
close to optimum (see Appendix A), and we have

$\displaystyle C_{P}(\gamma)$
$\displaystyle=\left[h(\epsilon^{*}(\gamma))+h\left(\frac{\epsilon_{0}+\epsilon_{1}}{2}\right)-\frac{h(\epsilon_{1})+h(\epsilon_{0})}{2}-1\right]_{+},$
(9)

where $[]_{+}$ means the positive part and we have used the notation $h()$ as
the binary Shannon entropy. If we now restrict Eve only by the laws of quantum
electrodynamics, we obtain the Devetak-Winters rate DW2005  for our protocol

$\displaystyle R_{DW}(\gamma)$
$\displaystyle=I(X,Y)-\mathcal{\chi}(X;E|\gamma),$ (10)

where $I(X;Y)$ is the Shannon mutual information of Alice’s choice for input
probability and measured by a state-of-the-art photon counting detector. The
quantity $\mathcal{\chi}(X;E|\gamma)$ is the Holevo bound for the
eavesdropper. Denoting
$\epsilon(\gamma)=\bra{0}\ket{\sqrt{\eta\gamma}\alpha_{1}}$, for uniform
priors (i.e. $q=0.5$) it is easy to show

$\displaystyle R_{DW}(\gamma)$
$\displaystyle=\left[h\left(\frac{\epsilon_{0}+\epsilon_{1}}{2}\right)-\frac{h(\epsilon_{1})+h(\epsilon_{0})}{2}-h\left(\frac{1+\epsilon(\gamma)}{2}\right)\right]_{+},$
(11)

The numerical calculation is shown in Fig. 4. We observe that the private rate
in (8) is as high as 0.68 for $\gamma=0.1$ (with little sensitivity to noise,
see Appendix B). And even for adverse channel conditions ($\gamma$ close to 1)
there is a positive secrecy rate for reasonable noise (e.g.up to $\gamma=0.6$
for $\Delta=10^{-4}$), however we will show below that in practice is best to
aim for $\gamma<0.1$. For comparison, we have also plotted (11) for
$\gamma=0.1$. We observe a substantial decrease, which is also affected by
noise, however, we still get significant positive rates. In the following, we
assume the realistic setting of Eve using Helstrom detection.

Figure 4: Private capacity of OOK for $\gamma=0.1$ and $\gamma=0.6$
($p_{dark}\approx 0$, $\eta_{o}=1$ $\Delta=10^{-4}.$) For comparison, also the
numerical values of $R_{DW}$ for $\gamma=0.1$.

##  IV The Micius satellite: a concrete example of an orbit-earth optical link

As a realistic physical scenario, we use as a reference the recent experiment
of QKD with the Chinese LEO satellite Micius Micius2017 Micius2020 . The
geometry is shown in Fig. 5. The satellite has an orbit of about 500 km above
the earth surface and exchanges keys over distances up to 1200 km if the
satellite is close to the horizon. The transmitter is equipped with 300 mm
Cassegrain telescope featuring a far field divergence $\theta_{div}$ of 10
$\mu$rad (full angle at $1/e^{2}$). The receiver at groundstation has a
telescope with a diameter $D_{R}$ of 1m.

Figure 5: Geometry for the secure and reliable communication of our wiretap
protocol showing the exclusion radius $r_{E}$.

We can approximate the fraction of the light collected by Bob, the free space
loss $\eta^{B}_{f}$, as the ratio of the telescope area and the footprint area

$\eta^{B}_{f}=\frac{A_{R}}{A_{F}}=\dfrac{\pi(D_{R}/2)^{2}}{\pi(D_{F}/2)^{2}}=\frac{D_{R}^{2}}{\theta_{div}^{2}d^{2}_{B}},$
(12)

with

$D_{F}\approx\theta_{div}d$

where $d_{B}$ is the distance between transmitter and receiver.

The number of photons detected by Bob is given by
$\eta\mu=\eta^{B}_{f}\eta_{b}\mu,$ where $\eta_{b}$ is the total additional
loss of Bob depending on the experimental situation. In the Micius experiment
those are atmospheric turbulence 3-8 dB ($\eta_{atm}$), pointing errors
($\eta_{p}$) $<$ 3 dB, overall optical loss ($\eta_{o}$) from telescope input
lens to detector 7.4 dB detector, detector efficiency $\eta_{det}$ 50 % (3 dB)
(see Appendix D). In the following we calculate with a loss $\eta_{b}$ of 20
dB (1%).

For Eve we calculate $\eta^{E}_{f}$ as in (12) but we add a factor taking into
account the light intensity outside the exclusion angle supposing a Gaussian
angular distribution of the beam as

$\eta^{E}_{f}=\frac{(D^{E}_{R})^{2}}{\theta_{div}^{2}d_{E}^{2}}e^{-2(\frac{2\theta_{E}}{\theta_{div}})^{2}}.$
(13)

Then, the number of photons detected by Eve becomes simply
$\eta^{E}_{f}\mu=\gamma\eta\mu$, as we assume no additional loss for Eve.
Hence, for fixed antenna sizes we can easily calculate $\gamma$ as

$\displaystyle\gamma(d_{B},d_{E},\eta_{b},\theta_{E},\theta_{div})$
$\displaystyle=\dfrac{1}{\eta_{b}}\Big{(}\frac{d_{B}}{d_{E}}\Big{)}^{2}\Big{(}\frac{D^{E}_{R}}{D^{B}_{R}}\Big{)}^{2}e^{-2(\frac{2\theta_{E}}{\theta_{div}})^{2}}.$
(14)

For $d_{B}=d_{E}=1200~{}km$ and $\theta_{E}=r_{E}/d$, for the Micius system
parameters and assuming a very large eavesdropper’s receiving antenna
$D^{E}_{R}$ of 2 m and a small exclusion radius $r_{E}=12.5$m we obtain:

$\gamma=0.07<0.1$

For the reminder, we fix the exclusion radius such that $\gamma<0.1$. Indeed,
this value seems to be a good choice as it leads to high secret capacities $>$
0.6 (see Fig. 4), little sensitivity to noise and signal fluctuations for
reasonable exclusion radii as discussed in Appendix B. This sensitivity is
driven by the distinguishability of the coherent states at Eve’s Holevo-
Helstrom detector as shown in Appendix E, the lower the $\gamma$ the less
sensitivity of the distinguishability to signal dynamics.

##  V Private rates for different practical settings and comparison with QKD

Configuration | Distance [km] | Channel loss ($\eta^{B}_{f}$) | QKD (night) $\Delta=10^{-7}$ | Wiretap channel (day) $\Delta=10^{-4}$
---|---|---|---|---
Micius | PLOB ($\eta_{b}=1$) | exlusion radius $r_{E}$ [m] | gamma | private rate
LEO | 500 - 1200 | 22dB |  $<$ 10kHz | 10MHz | 12.5 | 0.1 | 700MHz
MEO | 10000 | 40dB | - | 100kHz | 100 | 0.1 | 700MHz
GEO | 36000 | 52dB | - | 6kHz | 340 | 0.1 | 700MHz

Table 1: Comparison of the achievable secret key rates for QKD and the private
rates for the wiretap channel presented in this work. The values are
extrapolated from experimental data from the Micius satellite [4] for
$\eta^{B}_{f}=22dB$ (@1200 km) and $\eta_{b}=20dB$ (except for the theoretical
PLOB bound with $\eta_{b}=1$). The exclusion radii $r_{E}$ for $\gamma=0.1$
are calculated based on the Micius beam parameters. Note that for Micius and
PLOB we consider nighttime operation, in contrast to the case of the wiretap
channel where daytime operation is possible.

We can now calculate the private capacity for different geometrical
configuration, supposing that Alice and Bob have a satellite and a ground
station equivalent to the Micius experiment. We consider OOK with a clock rate
of 1GHz. With a time window of 1 ns, state of the art single photon detectors
feature a $p_{dark}<10^{-7}$, so detector noise has no significant effect on
the secret capacity. Table 1 in Er-lon2005  indicates the expected number of
noise photons for different collection angles, filter bandwidths and temporal
windows. Based on that an average number $\Delta$ of $10^{-4}$ and $10^{-7}$
is an achievable value for clear daytime sky, and a full moon clear night,
respectively. During a cloudy day, one could expect a $\Delta$ of $10^{-2}$,
and still positive private rates (this is under the assumption that
transmission of the channel is affected in the same way for Bob and Eve). See
Figure B.3 for the sensitivity to noise.

Given the clock rate and the maximum private capacity from Fig. 4, we obtain a
private rate of $680Mb/s$ for a $\gamma=0.1$. This value is the same for any
channel efficiency $\eta$ as long as the received power $\eta\mu$ is
optimized. We can compare these rates with the key rates obtained by QKD in
the Micius experiment and a potential perfect quantum communication scheme.
Indeed, Pirandola et. al. showed recently PLOB2017  that there is an upper
bound of the achievable secret key rate of a QKD protocol for a given channel
transmission $\eta$

$\displaystyle R_{QKD,\infty}(\eta)=-\log_{2}(1-\eta).$ (15)

Table I presents all these rates for LEO, MEO and GEO satellites. As expected,
the private capacity of a wiretap channel outperforms QKD dramatically in
terms of rate and most importantly in terms of resistance against noise.

Certainly, if the eavesdropper is restricted also the performance of QKD can
be improved substantially. As a comparison, we estimate the theoretically
achievable secret key rate for QKD following Appendix B in Shapiro2019 ,
choosing the parameters such that they are equivalent to our assumptions,
notably $\Delta=10^{-4}$ and $\gamma=0.1$. We obtain a similar rate of 360
Mbits/s. However, keyless private communication is arguably easier to
implement in practice, in particular it doesn’t need two way communication for
reconciliation.

There is also a scheme called Quantum Secure Direct Communication Qi2019 ,
which combines quantum communication and the possibility to detect the
presence of an eavesdropper with encoding like for the wiretap channel.
However, since this scheme is impractical, we don’t consider it in this
comparison.

Finally, some practical remarks. The necessary lasers power in order to reach
the optimal signal strength of about 4 photons in average is about 15 mW and
15$\mu$W for the GEO and the LEO setting, respectively, and therefore it is no
limitation. However, due to the high signal strength, a GHz repetition rate
implies high detection rates at Bob’s, which are still a challenge for single
photon detectors matthieu20 .

##  VI Discussion and Conclusions

We have shown the feasibility, practicality and performance of unconditionally
secure links for space and show the required exclusion radius. A protection
area is needed for any kind of secure communication, including QKD. In this
paper, we discussed a downlink, however, similarly, we could also consider an
uplink and estimate the channel degradation $\gamma$ for reasonable
assumptions on Eve’s satellites.

Our protocol is certainly susceptible of jamming attacks, but so are QKD
protocols. However, while our protocol cannot protect the communication from
jamming and active attacks, it can be used in coordination with security
mechanisms in communication layers above the physical layer to provide the
satellite system availability, integrity and confidentiality.

Given these boundary conditions, we have demonstrated that physical layer
encryption can provide information theoretically secure communication also in
the presence of Eve only limited by the laws of quantum physics. As for the
wiretap codes, explicit constructions are available that can provide the
strong security. Well known constructions are based either on coset codes with
random codeword choice within a coset Thangaraj2007 Klinc2011  or
concatenation of encryption functions (e.g. hashing) with conventional
capacity-achieving codes Tyagi2015 Hayashi2020  (e.g. low-density parity code
(LDPC), polar code or Reed Muller codes).

The achievable private rates are considerably higher than the QKD rates for an
unrestricted Eve. Moreover, direct private communication is also possible
close to illuminated cities and even during daytime in contrast to QKD.
Moreover, given the low rates, the secret keys generated by QKD will in
practice not be used in combination with the one-time-pad but with symmetric
encryption systems like Advanced Encryption Standard (AES). This means that
the legitimate users have to choose between trusting physical security
including exclusion areas around Alice and Bob (which is arguably needed for
QKD as well) or the computational security of encryption algorithms.

Overall, physical layer encryption seems to be a reasonable choice for
satellite communication.

###### Acknowledgements.

We would like to acknowledge Antonio Acín, Andreas Winter, Masahito Hayashi,
Christoph Wildfeuer and Mikael Afzelius for useful discussions. D.R.
acknowledges the support of European Union’s Horizon 2020 program under the
Marie Skłodowska-Curie project QCALL (No. GA 675662).

##  Appendix A  Optimized input probabilty

The optimization of the private capacity given in (8) also provides the
optimal input probability that Alice should choose to transmit the OOK
symbols. Fig. A.1 shows the optimized input probability as a function of the
received average number of photons and intensity of stray light. It is
interesting to observe that our wiretap channel can be considered nearly
symmetric. However, optimal private rates require small deviations from the
symmetric channel.

Figure A.1: Optimal value of input probability, $q$, as a function of the
average number of photons received by Bob $\eta\mu$ and the intensity of the
stray-light $\Delta$ ($\gamma=0.1$).

##  Appendix B  The appropriate value of $\gamma$ and the corresponding
exclusion radius

In this section we give a justification for the value for $\gamma=0.1$ as a
good trade-off between, on the one hand, a high secrecy capacity, and on the
other hand, the required exclusion area and resilience to experimental
fluctuations.

Figure B.1: Exclusion radius vs. the satellite distance for different $\gamma$
and eavesdropper model. ”Partial” stands for a telescope of $2m$ of diameter,
”total” for an eavesdropper collecting all light outside the exclusion region.

We consider the situation in which the adversary Eve is going to collect the
light with a telescope from a location close to Bob, hence at the same
distance $d$ from the satellite, Alice. In this case, if $\gamma$ is fixed,
the value of the exclusion ratio is given by the formula:

$r_{ex}=\frac{1}{2}\theta_{div}d\sqrt{\left(\frac{1}{2}log\left(\frac{1}{\gamma}\frac{1}{\eta_{b}}\left(\frac{D^{E}_{R}}{D^{B}_{R}}\right)^{2}\right)\right)}$
(16)

where $\theta_{div}$ is the far field divergence angle for the Gaussian beam,
$\eta_{b}$ is the efficiency of the detection system of Bob and $D^{E}_{R}$
and $D^{B}_{R}$ are respectively the radius of the antennas of Eve and Bob
respectively.

As it can be seen from Fig. B.1 the requested exclusion radius depends
linearly on the satellite to ground distance and it amounts to about $350~{}m$
for a geostationary orbit (around $35000~{}km$) for a $\gamma=0.1$. It can be
also seen that increasing the value of $\gamma$, e.g. $\gamma=0.9$, doesn’t
allow us to reduce the exclusion radius significantly.

A more restrictive approach consist in giving Eve all the optical power
outside the exclusion radius. This correspond to assuming that Eve can collect
all the light outside the cone from the satellite to the secure area. In this
case the exclusion ratio can be extrapolated from the following implicit
function once $\gamma$ is fixed:

$e^{-2\left(\frac{r_{ex}}{\theta_{div}d}\right)^{2}}=\gamma\left(1-e^{-2\left(\frac{D^{B}_{R}}{\theta_{div}d}\right)^{2}}\right)$
(17)

Figure B.2: The exclusion radius needed to achieve a given value of $\gamma$.

Also in this case the relation between the exclusion radius and the satellite
to ground distance is almost linear. However, the value is two to three times
higher than in the previous scenario. Still, the exclusion radius for the
geostationary orbit remains below $1~{}km$.

Fig. B.2 shows the dependence of the exclusion radius on the parameter
$\gamma$ when the distance satellite to ground is fixed to the value of 1200
km (distance similar to the Micius satellite). It illustrates that indeed (for
a finite detection area as well as for the unlimited case) the required
exclusion radius is almost constant with respect of $\gamma$ for values higher
than $0.1$. This means that going for value for $\gamma$ higher than $0.1$
brings only a little advantage in terms of exclusion radius, but at the cost
of a significant reduction of the secrecy rate, detrimental for the
performance of the protocol. Moreover, in this range, a small uncertainty in
the radius, or a bad pointing stability, may lead to a large variation in
$\gamma$ and threaten the security of the protocol. Therefore, going for
values of $\gamma<0.1$ seems to be pertinent, in the case of optical
communication with well defined Gaussian beams.

Figure B.3: Private capacity $C_{p}$ for $\gamma=0.1$ as a function of the
average number of photons received by Bob and the intensity of the stray-
light.

Finally in Fig. B.3 we show the behaviour of the private capacity $C_{p}$ for
$\gamma$ equal to $0.1$, with respect to stray light $\Delta$ and the received
light by Bob $\eta\mu$ (both in units of average number of photons per time
and frequency bin). We note that if we fix a secret capacity of say 0.5, the
protocol can resist to high fluctuations in the received light intensity and a
high amount of stray light (remember, we expect a $\Delta$ of $0.0001$ for a
clear sky during daytime). This security margin would be considerably reduced
for a $\gamma$ of 0.6 for instance.

##  Appendix C : Basic celestial mechanics

Figure C.1: Sketch of the orbits of Alice and Eve with respect to Bob.

Since, as discussed above, Eve can get only limited information by positioning
a receiver station on the ground next to Bob’s telescope, the natural question
would be what happens if Eve tries to attack Alice satellite instead? In this
section we give some arguments that, similarly to the previous case, it is
sufficient to assume a reasonable exclusion radius around Alice satellite in
order to assure the security of our protocol. A complete treatment of the
question is out of the scope of this paper, we just present some simple,
general considerations. (see for e.g. Tapley2004  for more information )

(a)

(b)

Figure C.2: Instantaneous channel efficiencies of Bob (a) and Eve (b) vs time
for a single passage of Alice

For simplicity, we assume that Bob’s station is positioned on the equator and
Alice’s and Eve’s satellites have two circular orbits in the equator plane
(see Fig. C.1). This is an extreme simplification of Eve’s task, since this
guarantees that at some time Eve will be exactly in the line of sight of Alice
and Bob. Indeed, if the two orbits and Bob are not in the same plane, Eve will
have a hard time to intersect the beam which has a diameter below one meter
close to Alice. So arguably, her best strategy would be to attach her
satellites directly on Alice’s. But as for the ground case, we impose an
exclusion radius around Alice (in agreement with the general assumption also
valid for QKD), which sets the minimal distance between Alice and Eve orbits.
Note that all objects in space are well monitored and and this assumption can
be verified with a reasonable effort esa_debris .

Both Alice’s and Eve’s angular velocities have the same direction as Bob on
earth. Let’s consider first a single passage of the satellites over the ground
station. In order to calculate $\gamma$, we trace the instantaneous collection
efficiency of Bob and Eve with respect of time, where time zero is fixed such
as Alice, Eve, Bob and the center of the earth are aligned. We conservatively
assume that if Eve completely intersects the beam, she resends the signals to
Bob and is consequently not detected directly. Finally, we integrate the
instantaneous efficiency over the period of communication between Alice and
Bob. The instantaneous efficiency with respect of time are calculated for Bob
and Eve respectively as:

$\eta^{B}(t)=\eta_{b}*\frac{D_{R}^{2}}{\theta_{div}^{2}d_{B}(t)^{2}}$ (18)

$\eta^{E}(t)=\frac{2}{\pi}\iint_{A(t)}\frac{e^{-2\left(\frac{x^{2}+y^{2}}{\theta_{div}^{2}d_{E}(t)^{2}}\right)}}{{\theta_{div}^{2}d_{E}(t)^{2}}}\,dx\,dy$
(19)

where $d_{B}(t)$ and $d_{E}(t)$ are the distances from Alice of Bob and Eve
with respect of time and the integral is considered over the area of Eve
telescope $A(t)$ moving with respect of Alice telescope. In the end in order
to calculate $\gamma$ with evaluate the ratio between the average efficiency
integrated over a period of communication between Alice and Bob:

$\gamma=\frac{\int_{-T}^{T}\eta^{B}(t)\,dt}{\int_{-T}^{T}\eta^{E}(t)\,dt}$
(20)

where $T=400s$ as it can be seen from Fig.2(a).

Figure C.3: Exclusion raduis vs $\gamma$ (for a single passage).

Fig. 2(a) and Fig. 2(b) show the instantaneous efficiencies of Bob and Eve,
respectively, for a configuration with an exclusion radius around Alice
satellite of 16 km and Alice’s orbit is 600 km above ground. The communication
is considered to be started and finished when the satellite is 20° above the
horizon with respect to Bob. As it can be seen the communication Alice and Bob
last for over 400 s, while Eve’s time of interception is only of few hundreds
of ms. If the efficiency is averaged over the passage of the satellite we can
again calculate the factor $\gamma$. Fig. C.3 shows the needed exclusion
radius in order to obtain a given $\gamma$. We can see that for an exclusion
radius above 16 km, a value of $\gamma$ lower than $0.1$ it can be assured,
again. Note, this is for a size of Eve’s telescope of 2m (sic!), which would
be very easy to spot.

This value of $\gamma$ is true for a single passage, however, a passage of
Alice over Bob occurs at a much higher frequency than the perfect alignment of
the Alice, Eve and Bob. The closer Eve is to Alice the longer the beating
period will be. This means that in order to implement such an attack it is not
sufficient to use a single satellite in a fixed orbit. The active strategy
would involve either a constellation of satellites or a satellite with
adjustable orbit. Just to give an idea, for the parameters considered here
(orbit of 600 km above ground for Alice and Eve 15 km below her) the period
between two links from Alice to Bob is around 1.7 hours, while the period
between two intercept events for Eve (Eve is in between Alice and Bob during
communication) would be of 20 days.

Overall, these estimations, although based on a worst case scenario, show that
it is possible to guarantee a $\gamma$ as low as $0.1$.

##  Appendix D : Physical probabilistic channel model

Figure D.1: Graphical representation of our degraded quantum wiretap channel
model.

Fig. D.1 represents our (degraded) quantum wiretap channel model, which is a
physical-probabilistic model. It shows the impairments undergone by the
transmitted average number of photons, $\mu=\absolutevalue{\alpha_{1}}^{2}$,
over the main and wiretap channels.

Bob’s channel power attenuation has the following contributions:
$\eta_{f}^{B}$ (free-space), $\eta_{atm}$ (atmospheric, e.g. turbulences),
$\eta_{p}$ (pointing) and $\eta_{o}$ (optical loss from telescope input lens
to detector). The detector efficiency, $\eta_{det}$, is included in the
overall losses parameter $\eta$. The channel transition probabilities are also
affected by the dark current noise, modelled by $p_{dark}$. Then, the
probabilistic model of the detector is fully described by the probabilities
$\epsilon_{0}=(1-p_{dark})e^{-\eta_{o}\Delta}$ and
$\epsilon_{1}=(1-p_{dark})e^{-(\eta\absolutevalue{\alpha_{1}}^{2}+\eta_{o}\Delta)}$.

Eve’s channel is only affected by propagation in free-space, $\eta_{f}^{E}$,
and by the Gaussian angular distribution of the beam, modelled as
$e^{-2(\frac{2\theta_{E}}{\theta_{div}})^{2}}$, or
$e^{-2(\frac{2r_{E}}{d\theta_{div}})^{2}}$, since $\theta_{E}\approx r_{E}/d$
with $\theta_{E}$ Eve’s exclusion angle, $\theta_{div}$ the divergence angle
and $d$ the distance between Alice and Bob. In our model, we express the
number of photons at Eve’s detector as a fraction of those received by Bob as
$\eta^{E}(\gamma)=\gamma\eta$. This modelling makes the parameter $\gamma$ a
design choice which controls the distinguishability of the coherent states at
Eve’s detector.

##  Appendix E  Distinguishability of Eve’s coherent states with $\gamma$ at
Eve’s detection.

Figure E.1: Representation of the coherent states sent by Alice and received
by Eve in the qubit space, in the classical phase space and as histograms on
the quadrature P (respectively from left to right).  Figure E.2: The angle
$\phi(\gamma)$ (left) and the error probability $\epsilon*(\gamma)$ vs the
received number of photons $\eta\mu$ for different values of $\gamma$.

Our design parameter $\gamma$ controls the distinguishability (orthogonality)
of the coherent states at Eve’s detection. This dependency can be visualized
in different representations, as shown in Fig. E.1: (left) representation of
the (rank-2) Hilbert space spanned by the coherent states at Eve’s reception,
$\varphi(\gamma)$ is the angle between the coherent states, (center) the P-Q
phase space with the (unitary variance) Gaussian uncertainty of each state and
(right) representation of the Gaussian distribution along the P quadrature.
Given the angle $\varphi(\gamma)=cos^{-1}\left(\langle
0,\sqrt{\gamma\eta}\alpha_{1}\rangle\right)$, the Holevo-Helstrom optimization
induces $\epsilon*(\gamma)$ and the symmetric space
$\phi_{0}^{*}(\gamma)=\phi_{1}^{*}(\gamma)=0.5(\pi/2-\varphi(\gamma))$.

Fig. E.2 shows the sensitivity of $\varphi(\gamma)$ to variations of the
received number of photons. The lower the $\gamma$, the less sensitivity. We
observe that for $\eta\mu=4$, we have $\varphi(0.1)=35^{o}$ and
$\epsilon^{*}(0.1)=0.2$ with an increase in orthogonality of 10% and a
decrease of 5% in (uncoded) error probability for a fluctuation around $1$
photon.

## References

  * (1) C.H. Bennett and G. Brassard, _Quantum cryptography: Public key distribution and coin tossing_ , in Proc. of IEEE Int. Conf. Computers, Systems and Signal Processing (1984).
  * (2) A. Boaron, G. Boso, D. Rusca, C. Vulliez, C. Autebert, M. Caloz, M. Perrenoud, G. Gras, F. Bussieres, M-J. Li, D. Nolan, A. Martin, H. Zbinden, _Secure quantum key distribution over 421 km of optical fiber_ , Phys. Rev. Lett. 121, 190502 (2018).
  * (3) XT. Fang, P. Zeng, H. Liu et al., _Implementation of quantum key distribution surpassing the linear rate-transmittance bound_ , Nat. Photonics 14, (2020)
  * (4) SK. Liao, WQ. Cai, WY. Liu, et al. _Satellite-to-ground quantum key distribution_ , Nature 549, 43–47 (2017).
  * (5) J. Yin, YH. Li, SK. Liao, et al. _Entanglement-based secure quantum cryptography over 1,120 kilometres_ , Nature 582, 501–505 (2020).
  * (6) P. W. Shor and J. Preskill, _Simple proof of security of the BB84 quantum key distribution protocol_ , Phys. Rev. Lett. 85, 441 (2000).
  * (7) D. Mayers _Unconditional security in quantum cryptography_ , Journal of the ACM 48, 3, 351406 (2001).
  * (8) G. Kat and K. Tamaki, _Security of six-state quantum key distribution protocol with threshold detectors._ Sci. Rep. 6, 30044 (2016).
  * (9) M. Curty, K. Azuma and HK. Lo, _Simple security proof of twin-field type quantum key distribution protocol._ npj Quantum Inf. 5, 64 (2019).
  * (10) R. Renner, N. Gisin, and B. Kraus, _Information-theoretic security proof for quantum-key-distribution protocols_ , Phys. Rev. A 72, 012332, (2005).
  * (11) V. Scarani, H. Bechmann-Pasquinucci, N. J. Cerf, M. Dusěk, N. Lütkenhaus, M. Peev, _The security of practical quantum key distribution_ , Rev. Mod. Phys. 81, 1301 (2009).
  * (12) A. D. Wyner, _The wire-tap channel_ , Bell System Technical Journal 54, 8, (1975).
  * (13) A. D. Wyner, _Capacity and error exponent for the direct detection photon channel-Part I_ , IEEE Trans. Inf. Theory 34, 6, (1998).
  * (14) A. D. Wyner, _Capacity and error exponent for the direct detection photon channel-Part II_ , IEEE Trans. Inf. Theory 34, 6, (1998).
  * (15) I. Csiszár and J. Körner, _Broadcast channels with confidential messages_ , IEEE Trans. Inf. Theory 24, 3, (1978).
  * (16) U. Maurer, _Secret key agreement by public discussion from common information,_ ” IEEE Trans. Inf. Theory 39, 3, (1993).
  * (17) M. Bellare, S. Tessaro, and A. Vardy, _Semantic security for the wiretap channel_ , in Proc. Advances in Cryptology, (2012).
  * (18) N. Cai, A. Winter, and R. W. Yeung. _Quantum privacy and quantum wiretap channels_ , Problems of Information Transmission 40 4, (2004).
  * (19) I. Devetak, _The private classical capacity and quantum capacity of a quantum channel_ , IEEE Trans. Inf. Theory 51 1,(2005).
  * (20) M. Hayashi, _Quantum wiretap channel with non-uniform random number and its exponent and equivocation rate of leaked information,_ IEEE Trans. Inf. Theory 61 10, (2015).
  * (21) I. Devetak and P. W. Shor, _The capacity of a quantum channel for simultaneous transmission of classical and quantum information_ , Commun. Math. Phys. 256, (2005).
  * (22) U. M. Maurer, _The strong secret key rate of discrete random triples_ , Communication and Cryptography, (Springer, Boston, 1994).
  * (23) Z. Pan, K. P. Seshadreesan, W. Clark, M. R. Adcock, I. B. Djordjevic, J. H. Shapiro, and S. Guha, _Secret key distillation over a pure loss quantum wiretap channel under restricted eavesdropping_ , Phys. Rev. Applied 14, 024044, (2020).
  * (24) Z. Pan, K. P. Seshadreesan, W. Clark, M. R. Adcock, I. B. Djordjevic, J. H. Shapiro and S. Guha, _Secret key distillation across a quantum wiretap channel under restricted eavesdropping_ , in Proc. IEEE Int. Symp. on Inf. Theory, (2019).
  * (25) T. Vergoossen, R. Bedington, J. A. Grieve, A. Ling, _Satellite quantum communications when man-in-the-middle attacks are excluded_ , Entropy 21, 9 (2019).
  * (26) M. Fujiwara, T. Ito, M. Kitamura, H. Endo, O. Tsuzuki, M. Toyoshima, H. Takenaka, Y. Takayama, R. Shimizu, M. Takeoka, R. Matsumoto, and M. Sasaki, _Free-space optical wiretap channel and experimental secret key agreement in 7.8 km terrestrial link_ , Opt. Exp. 26 15, (2018).
  * (27) G. Smith, _Private classical capacity with a symmetric side channel and its application to quantum cryptography_ , Phys. Rev. A 78, 022306 (2008).
  * (28) M. Wilde and H. Qi, _Energy-Constrained Private and Quantum Capacities of Quantum Channels_ , IEEE Trans. Inf. Theory 64 12, (2018).
  * (29) H. Endo, T. S. Han, T. Aoki, and M. Sasaki, _Numerical Study on Secrecy Capacity and Code Length Dependence of the Performances in Optical Wiretap Channels,_ IEEE Photonics Journal 7 5, (2015).
  * (30) H. Endo, M. Fujiwara, M. Kitamura, T. Ito, M. Toyoshima, Y. Takayama, H. Takenaka, R. Shimizu, N. Laurenti, G. Vallone, P. Villoresi, T. Aoki, and M. Sasaki, _Free-space optical channel estimation for physical layer security,”_ Opt. Express 24, (2016).
  * (31) M. Hayashi , _Quantum Information. An Introduction_ , (Springer, 2006).
  * (32) M. Hayashi and A. Vázquez-Castro, _Physical Layer Security Protocol for Poisson Channels for Passive Man-in-the-middle Attack_ , IEEE Trans. Inf. Forensics and Security 15, (2020).
  * (33) A. S. Holevo, _The Capacity of Quantum Channel with General Signal States_ , IEEE Trans. on Inf. Theory, 44, 1, 1996.
  * (34) S. Pirandola, R. Laurenza, C. Ottavani, L. Banchi, _Fundamental limits of repeaterless quantum communications_ , Nature Communications 8, 15043 (2017).
  * (35) M. Hayashi and A. Vázquez-Castro, _Two-Way Physical Layer Security Protocol for Gaussian Channels_ , IEEE Trans. on Communications, 68 5, (2020).
  * (36) K.M.R. Audenaert, J. Casamiglia, R. Munoz-Tapia, E. Bagan, Ll. Masanes, A. Acín and F. Verstraete, _Discriminating States: The Quantum Chernoff Bound_ , Phys. Rev. Lett. 98, 160501 (2007).
  * (37) K.M.R. Audenaert, M. Nussbaum, A. Szko?la and F. Verstraete, _Asymptotic Error Rates Quantum Hypothesis Testing,_ Commun. Math. Phys. 279, (2008)
  * (38) Carl W. Helstrom, ”Quantum Detection and Estimation Theory”, _Mathematics in Science and Engineering_ , Academic Press 123. (New York, 1976).
  * (39) _On asymptotically optimal hypothesis testing in quantum statistics_ , Probab. Appl. 23, 411-415 (1978)
  * (40) R.S. Kennedy, _A near-optimum receiver for the binary coherent state channel_ , Rep. 108, MIT RLE. Quarterly Progress Report (1973).
  * (41) S.JK. Dolinar, _An optimum receiver for the binary coherent state quantum channel_ , Rep. 111, MIT RLE Quarterly Progress Report (1973).
  * (42) M. Takeoka and M. Sasaki _Discrimination of the binary coherent signal: Gaussian-operation limit and simple non-Gaussian near-optimal receivers_ , Phys. Rev. A 78, 022320 (2008).
  * (43) K. Tsujino, D. Fukuda, G. Fujii, S. Inoue, M. Fujiwara, M. Takeoka, and M. Sasaki, _Quantum Receiver beyond the Standard Quantum Limit of Coherent Optical Communication_ , Phys. Rev. Lett. 106, 250503 (2011)
  * (44) I. Devetak and A. Winter, _Distillation of secret key and entanglement from quantum states_ , in Proc. R. Soc. Lond. A 461 2053, (2005).
  * (45) R. Qi, Z. Sun, Z. Lin, P. Niu, W. Hao, L. Song, Q. Huang, J. Gao, L. Yin and G-L. Long, _Implementation and security analysis of practical quantum secure direct communication_ , Light Sci Appl 8, 22 (2019).
  * (46) A. Thangaraj, S. Dihidar, A. R. Calderbank, S. W. McLaughlin and J. Merolla, _Applications of LDPC Codes to the Wiretap Channel_ , IEEE Trans. on Inf. Theory, 53 8, (2007).
  * (47) D. Klinc, J. Ha, S. W. McLaughlin, J. Barros, and B. Kwak, _LDPC codes for the Gaussian wiretap channel_ , IEEE Trans. Inf. Forensics Security, 6 3, (2011).
  * (48) H. Tyagi and A. Vardy, _Universal Hashing for Information-Theoretic Security_ , in Proc. of the IEEE 103 10, (2015).
  * (49) M Er-long, H. Zheng-fu, G. Shun-sheng, Z. Tao, D. Da-sheng and G. Guang-can, _Background noise of satellite-to-ground quantum key distribution_ , New Journ. of Physics 7, 215 (2005).
  * (50) B. Tapley, B. Schutz, and G. Born _Statistical Orbit Determination_ (Elsevier, 2004)
  * (51) see e.g. ESA Space Debris Office.
  * (52) M. Perrenoud, M. Caloz, E. Amri, C. Autebert, Ch. Shönenberger, H. Zbinden,and F. Bussières, _Operation of parallel SNSPDs at high detection rates_ , to appear in Supercond. Sci. Technol, (2020).


Combinatorial spectra of graphs

Martin Dzúrik

Department of Mathematics and statistics, Faculty of Science,
Masaryk University, Kotlářská 2, CZ-61137 Brno, Czech Republic

In this article we are introducing combinatorial spectra of graphs, this is a generalization of $H$-Hamiltonian spectra. The main motivation was to made from $H$-Hamiltonian spectra an operation
and develop some algebra in this field. An improved version of this operation form a commutative monoid. The most important thing is that most of the basic concepts of graph theory, such as maximum pairing, vertex and edge connectivity and coloring, Ramsey numbers, isomorphisms and regularity, can be expressed in the language of this operation.

This work was supported from Operational Programme Research, Development
and Education – „Project Internal Grant Agency of Masaryk University" (No.

§ INTRODUCTION

In the article [1] we have created a generalization of the Hamiltonian spectrum of a graph $G$ called the $H$-Hamiltonian spectrum of the graph $G$ denoted by ${\mathscr{H}}_{H}(G)$. Not only does this generalization give us the opportunity to talk, for example, about the isomorphism of graphs and the regularity of graphs in the language of these spectra, but there are several relations between ${\mathscr{H}}_{H}(G)$ and ${\mathscr{H}}_{H'}(G)$ for related $H$ and $H'$, for example for $H'=\overline{H}$. And so this brings some basic calculus to this area.

This approach has led us to one more generalization, which we call the combinatorial spectrum. This spectrum is now for $R$-weighted graphs, more precisely for sets of $R$-weighted graphs and we denote it $\mathscr{H} * \mathscr{G}$. This will play a role of multiplication, we also get some addition $+$. When we denote $\mathscr{P}(Graphs)$ the set of all sets of graphs we will get that $(\mathscr{P}(Graphs),*,+)$ is a $R$-module, semigroup (or commutative monoid) and something close to ring. The most important thing is that most of the basic concepts of graph theory, such as maximum pairing, vertex and edge connectivity and coloring, Ramsey numbers, isomorphisms and regularity, can be expressed in the language of these combinatorial spectra. Together with the already mentioned calculus, it gives us a hope that all these concepts could be linked, studied together and transfer the results from one to the other.

In this article we will recall a definition of generalized Hamiltonian spectra of
undirected finite graphs from the article [1] and we will define combinatorial spectra. Then we will show some basic
algebraic properties of these spectra and describe connections to another
topics in graph theory. At the end we will show another properties of combinatorial spectra.

The author would like to thank Lukáš Vokřínek for many helpful discussions.

Recall that,
a graph $G$ is a pair

\[
\]

where $V(G)$ is a finite set of vertices of $G$ and $E(G)\subseteq V(G) \times V(G)$,
a symmetric antireflexive relation, is a set of edges. We will denote an edge between $v$ and $u$ by $\{v,u\}$.

Let us recall the definition of the generalized Hamiltonian spectrum from [1].

Let $G,H$ be graphs such that $|V(G)|=|V(H)|$ and
$f\,:\,V(H)\rightarrow V(G)$ is a
bijection, then we call $f$ a pseudoordering on the graph $G$ (by $H$),

\[
s_H(f,G)=\sum_{\{x,y\}\in E(H)}\rho_G(f(x),f(y)),
\]

$\rho_G (x,y)$ is the distance of $x,y$ in the graph $G$. Then

\[
\mathscr{H}_{H}(G)=\{s_H(f,G)|f~\text{pseudoordering on}~ G \text{ by $H$}\}
\]

is the $H$-Hamiltonian spectrum of the graph $G$.

Now we will define a combinatorial spectrum.
In the rest of this article we will use a notation $R$ for a ring.
In combinatorial spectra we talk about $R$-weighted complete graphs,
for many application we will use simply $R=\mathbb{R}$.

Let $H$ and $G$ be $R$-weighted complete graphs such that $|V(G)|=|V(H)|$ with weighted functions

\[
v_H:E(H) \rightarrow R,
\]

\[
v_G:E(G) \rightarrow R,
\]

and $f\,:\,V(H)\rightarrow V(G)$ be a bijection then we define $H *_f G$ as follows

\[
V(H *_f G) = V(H), \quad E(H *_f G)=E(H), \quad v_{ H *_f G}(e)=v_H(e) \cdot v_G(f(e))
\]

Let $H$ and $G$ be $R$-weighted complete graphs such that $|V(G)|=|V(H)|$, we define

\[
H*G=\{H *_f G ~| ~f : V(G) \rightarrow V(H),\text{ bijection}\}
\]

\[
H \* G = \sfrac{\langle H*G \rangle}{iso},
\]

where $\langle-\rangle$ means closure under isomorphisms (but on given set of vertices).

$\*$ clould be equivalently defined by

\[
H*G=\{[H *_f G] ~| ~f : V(G) \rightarrow V(H),\text{ bijection}\},
\]

where $[K]$ is an isomorphism class of graph $K$.

\[
\langle-\rangle : \mathscr{P}(R-Graphs_n) \rightarrow \mathscr{P}(R-Graphs_n)
\]

is an isotonic idempotent map.

Let $\mathscr{H},~\mathscr{G}$ be sets (or classes) of $R$-weighted complete graphs with the same number of vertices than we define

\[
\mathscr{H}*\mathscr{G}=
\bigcup_{\substack{G \in \mathscr{G}\\
H \in \mathscr{H}}}
\mathscr{H}\*\mathscr{G}=
\bigcup_{\substack{G \in \mathscr{G}\\
H \in \mathscr{H}}}
\]

Now $*$ and$\*$are operations

\[\begin{tikzcd}[row sep=tiny]
*:\mathscr{P}(R-Graphs_n)\times \mathscr{P}(R-Graphs_n)\arrow[r] &\mathscr{P}(R-Graphs_n)
\\
\*:\sfrac{\langle\mathscr{P}(R-Graphs_n)\rangle}{iso}\times \sfrac{\langle\mathscr{P}(R-Graphs_n)\rangle}{iso}\arrow[r] &\sfrac{\langle\mathscr{P}(R-Graphs_n)\rangle}{iso}.
\end{tikzcd}\]

Where $\mathscr{P}(R-Graphs_n)$ denotes the set of all sets of $R$-weighted complete graphs on $n$ vertices.

The first part is obvious and the second part is given by the following commutative diagram.

\[
\begin{tikzcd}
\mathscr{P}(R-Graphs_n)\times \mathscr{P}(R-Graphs_n)  \arrow[r, "*"] \arrow[d, two heads,"\langle - \rangle \times\langle - \rangle"', bend right] & \mathscr{P}(R-Graphs_n)\arrow[d, two heads,"\langle - \rangle"', bend right]\\
\langle\mathscr{P}(R-Graphs_n)\rangle\times \langle\mathscr{P}(R-Graphs_n)\rangle \arrow[u, bend right,hook] \arrow[d, "\cong"]\arrow[r, dotted,"!"] & \langle\mathscr{P}(R-Graphs_n)\rangle\arrow[d, "\cong"]\arrow[u, bend right,hook]\\
\sfrac{\langle\mathscr{P}(R-Graphs_n)\rangle}{iso}\times \sfrac{\langle\mathscr{P}(R-Graphs_n)\rangle}{iso} \arrow[r, dotted,"!"] & \sfrac{\langle\mathscr{P}(R-Graphs_n)\rangle }{iso},
\end{tikzcd}
\]

where the bottom arrow is $\*$. Where

\[\langle\mathscr{P}(R-Graphs_n)\rangle
=\{ \langle\mathscr{G}\rangle| \mathscr{G} \in \mathscr{P}(R-Graphs_n)\}
\]

The middle arrow exists uniquely, because of the fact
\[
\langle\mathscr{G}*\mathscr{H}\rangle=\langle\mathscr{G}\rangle * \langle\mathscr{H}\rangle.
\]

Let $G$ be an (connected) unweighted graph then we define $R$-weighted complete graphs $I(G)$, $\rho(G)$ as follows,

\[
\]

\[
\begin{cases}
1  & \text{for }e \in E(G)\\
0  &\text{for }e\notin E(G)
\end{cases},
\quad v_{\rho(G)}(\{x,y\}) = \rho_G(x,y).
\]

In the rest of the section we will show some algebraic properties $*$.

Let $F$, $G$ and $H$ be $R$-weighted complete graphs such that $|V(F)|=|V(G)|=|V(H)|$ and $f\,: V(F) \rightarrow V(G)$, $f\,: V(G) \rightarrow V(H)$ be pseudoorderings then

\[
F *_{f}( G*_{g } H)=(F*_f G)*_{g \circ f} H , \quad
F \*_{f}( G\*_{g } H)=(F\*_f G)\*_{g \circ f} H .
\]

\[
v_{(F*_f G)*_{g\circ f} H}(e)=v_{F*_f G}(e) \cdot v_H(g(f(e)))= v_F(e) \cdot v_G(f(e)) \cdot v_H(g(f(e))),
\]

\[
v_{F *_{f}( G*_{g} H)}(e)= v_{F}(e) \cdot v_{G*_{g} H}(f(e))=
v_{F}(e) \cdot v_G (f(e)) \cdot v_H (g(f (e))).
\]

For $\*$ similar.

Let $G$ and $H$ be $R$-weighted complete graphs such that $|V(G)|=|V(H)|$ and $f\,: V(F) \rightarrow V(G)$ be pseudoordering then there is an isomorphism

\[
\xymatrix{&f:~H*_f G & G*_{f^{-1}} H \ar@<1ex>[l]
\ar@<1ex>[l];[]~:f^{-1}.}
\]

\[
v_{G*_{f^{-1}} H}(f(e))=v_G (f(e)) \cdot v_H ((f^{-1}\circ f)(e))=v_H(e) \cdot v_G(f(e))= v_{H*_f G}(e).
\]

Let $H$ be a $R$-weighted complete graph then

\[
H*_f I(K_{|V(H)|})= H
\]

\[
v_{H*_f I(K_{|V(H)|})}(e)=v_H(e) \cdot 1 = v_H(e).
\]

Let $\mathscr{F},~\mathscr{G},~\mathscr{H}$ be sets of $R$-weighted complete graphs of the same number of vertices then

\[
(\mathscr{F}*\mathscr{G})*\mathscr{H}=\mathscr{F}*(\mathscr{G}*\mathscr{H}), \quad
\]

\[
\mathscr{H}\*\mathscr{G} = \mathscr{G}\*\mathscr{H}, \quad \mathscr{H}\*\bigl\{I(K_{|V(H)|})\bigr\}=\mathscr{H}.
\]

Equalities follows from Lemmas <ref>, <ref> and <ref>. For example for first one

(ℱ   *𝒢)*ℋ

={ (F*_f G)*_g H     |         F∈ℱ,G∈𝒢,H∈ℋ,f,g   pseudoorderings     }

={ (F*_f G)*_g'∘f H    |         F∈ℱ,G∈𝒢,H∈ℋ,f,g'   pseudoorderings     }

={ F *_f( G*_g'  H)          |         F∈ℱ,G∈𝒢,H∈ℋ,f,g'   pseudoorderings     }

For another similar.

$ is a semigroup and
\[(\sfrac{\langle\mathscr{P}(R-Graphs_n)\rangle}{iso},\*,\bigl\{I(K_{|V(H)|})\bigr\})\]
is a comutative monoid.

Let $G$ be a $R$-weighted complete graph with weighted function $v_H$ then we define

\[
s(G)=\sum_{e \in E(G)} v_H(e).
\]

And for $\mathscr{G} \in \mathscr{P}(R-Graphs_n)$ we define

\[
s(\mathscr{G})=\{s(G)|G\in\mathscr{G} \}.
\]

Let $H_1,H_2\in R-Graphs_n$ such that $V(H_1)=V(H_2)$ then we define an operation $+$ on $ R-Graphs_n$ as follows

\[
V(H_1+H_2)=V(H_1), \quad
\]

We also define an operation on $ \mathscr{P}(R-Graphs_n)$ as follows, let $\mathscr{H}_1,\mathscr{H}_2\in \mathscr{P}(R-Graphs_n)$ such that all graphs have the same set of vertices then

\[
\mathscr{H}_1+\mathscr{H}_2=\left\{ H_1+H_2\middle|H_1\in \mathscr{H}_1,  H_2\in \mathscr{H}_2
\right\}
\]

Let $H_1,H_2,G$ be $R$-weighted complete graphs with the same number of vertices such that $V(H_1)=V(H_2)$ then it holds

\[
(H_1+H_2)*G\subseteq H_1 * G + H_2 * G
\]

\[
(H_1+H_2)\*G\subseteq H_1 \* G + H_2 \* G.
\]

It is easy to prove that

\[
(H_1+H_2)*_f G= H_1 *_f G + H_2 *_f G
\]

and from this we get the statement of the lemma.

For $\*$ similar.

Let $H_1,H_2,G$ be $R$-weighted complete graphs with the same number of vertices such that $V(H_1)=V(H_2)$
and $|s(H_1*G)|=1$ then it holds

\[
s((H_1+H_2)*G) = s(H_1 * G) + s(H_2 * G)
\]

From the previous lemma we get one inclusion, lets take an arbitrary element of $ s(H_1 * G) + s(H_2 * G)$ which is equal to

\[
s(H_1 *_f G) + s(H_2 *_g G)\overset{|s(H_1*G)|=1}{=} s(H_1 *_g G) + s(H_2 *_g G)= s((H_1 + H_2) *_g G)
\]

and the last thing is an element of $s((H_1+H_2)*G)$.

Let $\mathscr{H}_1, \mathscr{H}_2 ,~\mathscr{G}\in \mathscr{P}(R-Graphs_n)$ then

\[
(\mathscr{H}_1+\mathscr{H}_2)*\mathscr{G}\subseteq \mathscr{H}_1 * \mathscr{G} + \mathscr{H}_2 * \mathscr{G}
\]

\[
(\mathscr{H}_1+\mathscr{H}_2)\*\mathscr{G}\subseteq \mathscr{H}_1 \* \mathscr{G} + \mathscr{H}_2 \* \mathscr{G}
\]

\begin{align*}
(&\mathscr{H}_1+\mathscr{H}_2)*\mathscr{G} \\
&= \bigcup_{\substack{H_1 \in \mathscr{H}_1,H_2 \in \mathscr{H}_2,\\ G \in \mathscr{G}}} (H_1+H_2)*G \overset{L\ref{l8}}{ \subseteq }
\bigcup_{\substack{H_1 \in \mathscr{H}_1,H_2 \in \mathscr{H}_2,\\ G \in \mathscr{G}}} H_1 *  G + H_2 * G\\
&= \mathscr{H}_1 * \mathscr{G} + \mathscr{H}_2 * \mathscr{G} .
\end{align*}

For $\*$ similar.

Let $\mathscr{H}_1,~\mathscr{G}\in \mathscr{P}(R-Graphs_n)$ such that for all $H_1 \in \mathscr{H}_1,~ G \in \mathscr{G}$ holds $|s(\{H_1\}*\{G\})|=1$ then

\[
s((\mathscr{H}_1+\mathscr{H}_2)*\mathscr{G})= s(\mathscr{H}_1 * \mathscr{G}) + s(\mathscr{H}_2 * \mathscr{G})= s(\mathscr{H}_1 * \mathscr{G} +\mathscr{H}_2 * \mathscr{G}).
\]

The proof is similar as before, but we replace the lemma <ref> by <ref>, where is equality.

§ CONNECTION TO ANOTHER TOPICS

In this section we are going to show how can be many standard concepts in graph theory be expressed in the language of combinatorial spectra.

Let $H$ and $G$ be unweighted graphs such that $|V(G)|=|V(H)|$ then

\[
\mathscr{H}_{H}(G)=s(\{I(H)\}*\{\rho(G)\}).
\]

The proof is just a straight forward comparison of definitions <ref>, <ref> and <ref>.

Let $\mathscr{G}$ be a set of $R$-weighted complete graphs with the same number of vertices then

\[
\langle \mathscr{G} \rangle = K_{n}* \mathscr{G},
\]

where $\langle - \rangle$ is closure under isomorphisms introduced in definition <ref> and $n$ is a number of vertices of graphs in $\mathscr{G}$.

proof follows from this equation

\[
K_{n}*_f G= f^{-1}(G).
\]

Let $G$ be an unweighted graph then

\[
s(\mathscr{P}_{|V(G)|}* I(G))=\{ \text{cardinalities of pairings in the graph }G\},
\]

\begin{align*}
\mathscr{P}_{|V(G)|} &= \left\{I(P_{|V(G)|,k})\middle| k \in \left\{0, \dots ,   \left\lfloor\frac{|V(G)|}{2}\right\rfloor  \right\}   \right\},\\
\bigsqcup_{i=1}^{k} \bigl(\xymatrix{ \cdot \ar@{-}[r] &\cdot  } \bigr) \sqcup \bigsqcup_{i=1}^{|V(G)|-2k} \cdot
\end{align*}

Let $\{e_1,\dots,e_k\}$ be a pairing in the graph $G$, then we can construct a pseudoordering $ f : P_{|V(G)|,k} \rightarrow V(G)$ such that each edge of $P_{|V(G)|,k}$ maps to $e_i$ for some $i$. For this $f$ we have

\[
s(I(\mathscr{P}_{|V(G)|})*_f I(G))=k,
\]

\[
s(\mathscr{P}_{|V(G)|}* I(G))\supseteq\{ \text{cardinalities of pairings in the graph }G\}.
\]

Let $ f : P_{|V(G)|,k} \rightarrow V(G)$ be a pseudoordering, when we delete from $P_{|V(G)|,k}$ edges which are mapped to no-edges of $G$ we will get a pseudoordering
$ g : P_{|V(G)|,l} \rightarrow V(G)$ such that

\[
s(I(P_{|V(G)|,k})*_f I(G))= s(I(P_{|V(G)|,l})*_g I(G)).
\]

But now image of $g$ form a pairing in the graph $G$ and hence

\[
s(\mathscr{P}_{|V(G)|}* I(G))\subseteq\{ \text{cardinalities of pairings in the graph }G\}.
\]

\[
s\left(S_{|V(G)|}*I(G)\right)=\{deg_G(v)| v\in V(G)\},
\]

where $S_{|V(G)|}=K_{1,|V(G)|-1}$ is a star with same number of vertices as the graph $G$ and $deg_G(v)$ is a degree of vertex $v$ in the graph $G$.

Let $f:S_{|V(G)|} \rightarrow I(G)$ be a pseudoordering, then

\[
s\left(S_{|V(G)|}*_f I(G)\right)= deg_G(f(c)),
\]

where $c$ is a center of the star. Indeed, let $\{u,v\}\in E\left(S_{|V(G)|}*_f I(G)\right)$ then weight of this edge is zero if both vertices $u,v$ are different from vertex $c$.
And weight of edge {c,v} is

\begin{align*}
v_{S_{|V(G)|}*_f I(G)} \{c,v\} = \begin{cases}1 & \text{if }\{f(c),f(v)\}\in E(G) \\
0 & \text{if }\{f(c),f(v)\}\notin E(G).
\end{cases}
\end{align*}

$G$ is vertex $k$-colorable if and only if

\[
\min s\left( \mathscr{H}_k * \{I(G)\}\right)= 0,
\]

\[
\mathscr{H}_k =\left\{    I\left(\bigsqcup_{i=1}^{k} K_{n_i}\right) \middle| n_1,\dots,n_k \in \mathbb{N}, \sum_{j=0}^k n_j = |V(G)|   \right\}.
\]

Let we have a proper $k$-coloring $g: V(G) \rightarrow \{1,\dots,k\}$ of the graph $G$, let $n_i=|g^{-1}(i)|$ be a number of vertices of color $i$. Take an arbitrary bijection

\[
f_i:V(K_{n_i}) \rightarrow g^{-1}(i),
\]

for all $i \in \{1,\dots,k\}$.
Then we define a bijection

\[
f=\bigsqcup_{i=1}^{k}f_i:\bigsqcup_{i=1}^{k} K_{n_i} \rightarrow   V(G),
\]

this pseudoordering satisfy

\[
s\left( I\left(\bigsqcup_{i=1}^{k} K_{n_i}\right) *_f I(G)\right)= 0.
\]

Indeed, let $\{v,u\} \in E(\bigsqcup_{i=1}^{k} K_{n_i} )$, then $f(v),f(u)$ have the same color in coloring $g$ hence there is not an edge $\{f(v),f(u)\}$, this means that all nonzero edges in
$I(\bigsqcup_{i=1}^{k} K_{n_i})$ maps to zero by $f$.

Let now

\[
\min s\left( \mathscr{H}_k * \{I(G)\}\right)= 0,
\]

this means that there exists a pseudoordering $f$ and a decomposition $\sum_{j=0}^k n_j = |V(G)|$ such that

\[
s\left( I\left(\bigsqcup_{i=1}^{k} K_{n_i}\right) *_f I(G)\right)= 0.
\]

From this we can define a coloring similar as in the opposite direction.

Let $a \in R$ then we define

\[
U_a: R-Graph_n \rightarrow Graph_n,
\]

defined as follows, for graph $G$ with weight function $v_G$, we define unweighted graph $U_a(G)$,

\[
V(U_a(G))=V(G),~E(U_a(G))=\left\{e\in E(G) \middle|  v_G (e)=a   \right\}.
\]

Following lemmas will be used for description of edge colorability and edge connectivity.

Let $G\neq K_{|V(G)|}$ be a unweighted graph then

\[
I(G)*I(K_{|V(G)|}\setminus e)
\]

is equal to $I$ of a set of all graphs obtainable from $G$ by deleting at most 1 edge.

In a pseudoordering is some edge $e'$ of $G$ mapped to the edge $e$ and this pseudoordering gives us a graph $G \setminus e'$.

Let $G\neq K_{|V(G)|}$ be a unweighted graph then

\[
I(G)*I(K_{|V(G)|}\setminus e)^{*k}
\]

is equal to $I$ of set of all graphs obtainable from $G$ by deleting at most $k$ edges. Where

\[
H^{*k}=\underbrace{H*\dots *H}_k

Proof is given by iteration of the previous lemma (<ref>).

\begin{align*}
I(G)*I(K_{|V(G)|}\setminus e)^{*k} &= I(G)*I(K_{|V(G)|}\setminus e)^{*(k-1)}*I(K_{|V(G)|}\setminus e)\\
&=\{G \setminus \leq k -1 \text{ edges}\}*I(K_{|V(G)|}\setminus e)\\
&=\{G \setminus \leq k  \text{ edges}\}.
\end{align*}

Let $\mathscr{G} \in \mathscr{P}(R-Graphs_n)$
if there exists $n \in \mathbb{N}$ such that for all $n\leq k\in \mathbb{N}$

\[
\mathscr{G}^{*k}=\mathscr{G}^{*n},
\]

we will denote

\[
\mathscr{G}^{*\infty}=\mathscr{G}^{*n}.
\]

This is a standard notation from the theory of semigroups.
Also we will define for $G \in R-Graphs_n$

\[
\]

\[
I(K_{|V(G)|}\setminus e)^{*\infty} \cup \left\{I(K_{|V(G)|})\right\}
\]

is equal to $I$ of set of all graphs with given number of vertices.

\[
I(K_{|V(G)|}\setminus e)^{*\infty}=I(K_{|V(G)|}\setminus e)*I(K_{|V(G)|}\setminus e)^{*\infty},
\]

hence by lemma <ref> it is equal to $I$ of set of all graphs obtainable from $K_{|V(G)|}\setminus e$ by deleting at most $\infty$ edges. Then it is any graph up to $I(K_{|V(G)|})$.

\[I(G)*\left(\sum_{i=1}^{k-1} \left(I(K_{|V(G)|}\setminus e)^{*\infty} \cup \left\{I(K_{|V(G)|})\right\}\right)+ I(K_{|V(G)|}) \right)\]

is equal to a set of all $k$-colorings (possibly non-proper) of the graph $G$ where we add zeros to non-edges of $G$.

\begin{align*}
\sum_{i=1}^{k-1} &\left(I(K_{|V(G)|}\setminus e)^{*\infty} \cup \left\{I(K_{|V(G)|})\right\}\right)\\
\overset{L\ref{l6}}{=}&\sum_{i=1}^{k-1}\left( \text{set of all graphs weighted by 0 and 1}              \right)\\
\overset{\phantom{L\ref{l6}}}{=} &(\text{set of all graphs weighted by }0,\dots,k-1),
\end{align*}

\begin{align*}
&I(G)*\left(\sum_{i=1}^{k-1} \left(I(K_{|V(G)|}\setminus e)^{*\infty} \cup \left\{I(K_{|V(G)|})\right\}\right)+ I(K_{|V(G)|}) \right)\\
=&I(G)*\left((\text{set of all graphs weighted by }0,\dots,k-1)+I(K_{|V(G)|}) \right)\\
=&I(G)*\phantom{(}(\text{set of all graphs weighted by }1,\dots,k)\\
=&(\text{set of all }k\text{-colorings of the graph } G).
\end{align*}

$G$ is edge-$k$ colorable if and only if

\[
\exists H \in I(G)*\sum_{i=1}^{k-1} \left( \left(I(K_{|V(G)|}\setminus e)^{*\infty} \cup \left\{I(K_{|V(G)|})\right\}\right) + I(K_{|V(G)|}) \right)
\]

such that

\[
\forall a \in \{1,\dots,k\} :~ s(I(U_a(H))*S_{|V(G)|})\leq 1.
\]

By lemma <ref> we have that condition

\[
\exists H \in I(G)*\sum_{i=1}^{k-1} \left( \left(I(K_{|V(G)|}\setminus e)^{*\infty} \cup \left\{I(K_{|V(G)|})\right\}\right) + I(K_{|V(G)|}) \right),
\]

means there exists a coloring of the graph $G$. By the theorem <ref>

\[
s(I(U_a(H))*S_{|V(G)|})\leq 1,
\]

is equivalent to the fact that degree of any vertex of $U_a(H)$ is at most $1$ for $a\in \{1,\dots,k\}$. Hence second condition says that the coloring is proper.

$G$ has friendly bisection if and olny if

\[
\exists H \in   \left\{   I\left(K_{|V(G)|} \right)- 2\cdot I\left(K_{\frac{|V(G)|}{2},\frac{|V(G)|}{2}} \right)    \right\} * \{I(G)\}
\]

such that

\[
s\left(H * S_{|V(G)|}\right)\geq 0.
\]

\[
\left\{   I\left(K_{|V(G)|} \right)- 2\cdot I\left(K_{\frac{|V(G)|}{2},\frac{|V(G)|}{2}} \right)    \right\} * \{I(G)\}
\]

is the set of all weighted graphs obtainable from $I(G)$ by given process, let $A\subseteq V(G)$ be an arbitrary subset. If we now denote $I(G)_A$ a graph given by changing all signs of edges of $I(G)$ between set $A$ and $V(G) \setminus A$. The last combinaorial spectra is equal to

\[
\left\{I(G)_A\middle||A|=\frac{|V(G)|}{2}\right\}.
\]

Let $A\subseteq V(G)$ be a subset and we denote $B=A\subseteq V(G)$. Now we will compute a combinatorial spectrum $s\left( I(G)_A* S_{|V(G)|}\right)$.

\[
s\left( I(G)_A*_f S_{|V(G)|}\right)= \begin{cases}
|N(f^{-1}(c)) \cap A| - |N(f^{-1}(c)) \cap B| & \text{if } f^{-1}(c) \in A\\
|N(f^{-1}(c)) \cap B| - |N(f^{-1}(c)) \cap A| & \text{if } f^{-1}(c) \in B,
\end{cases}
\]

where $N(v)\subseteq V(G)$ is the neighborhood of the vertex $v$ and $c$ is a center of the star $S_{|V(G)|}$.

Let now $H \in \left\{I(G)_A\middle||A|=\frac{|V(G)|}{2}\right\}$, such that

\[
s\left(H * S_{|V(G)|}\right)\geq 0.
\]

By previous result it is equivalent to $A,V(G) \setminus A$ being a friendly bisection of $G$.

Let $G$ be unweighted graph, then $
G$ is edge connected if and only if

\[
\min \left(s\left( \mathscr{H}_{|V(G)|}* I(G)\right)\right)\geq 1,
\]

\[
\mathscr{H}_{|V(G)|}=\left\{I(K_{n,|V(G)|-n}) ~\middle|~ 1\leq n \leq|V(G)|-1 \right\}.
\]

The proof follows from the fact that

\[
s(K_{n,|V(G)|-n}*_f I(G))
\]

is equal to the number of edges of $G$ between sets of vertices $f(A),f(B)\subseteq V(G)$, where $A,B\subseteq V(K_{n,|V(G)|-n})$ are two sides of this bipartite graph.
And from the fact that a $G$ is connected if and only if for any partition $P,V(G)\setminus P\subseteq V(G)$ of the graph $G$, there exists an edge in $G$ connecting $P$ and $V(G)\setminus P$.

Let $G$ be unweighted graph, then
G \text{ is edge } (k+1) \text{-connected iff }

\[
\min \left(s\left( \mathscr{H}_{|V(G)|}* I(K_{|V(G)|}\setminus e)^{*k}*I(G)\right)\right)\geq 1,
\]

\[
\mathscr{H}_{|V(G)|}=\left\{I(K_{n,|V(G)|-n}) ~\middle|~ 1\leq n \leq|V(G)|-1 \right\}.
\]

The proof follows from lemmas <ref> and <ref>. By lemma <ref> is the spectrum

\[
\left(I(K_{|V(G)|}\setminus e)^{*k}*I(G)\right)
\]

equal to $I$ of set of all graphs obtainable from $G$ by deleting at most $k$ edges. Now by lemma <ref> the whole formula is equivalent to fact
that all graphs obtainable from $G$ by deleting at most $k$ edges are connected.

Following lemmas will be used for description of vertex connectivity.

Let $H$ be $R$-weighted complete graph, then

\[
\]

is a set of all graphs obtainable from $H$ by vanishing all edges neighboring to at most $k$ vertices. By this we mean a set
\[
\left\{ H_{\setminus A}\middle|A \subseteq V(H),~|A|\leq k\right\},
\]

where $H_{\setminus A}$ is a graph given by vanishing all edges which have at least one endpoint in $A$.
And for $G$ unweighted graph we denote

\[
\overline{G}=K_{|V(G)|}\setminus G.
\]

It is a complement of a graph $G$.

The proof is similar to proof of lemma <ref>.

Let $G$ be unweighted graph, then

\[
\left(I(G)+ \left(-\frac{1}{2}\right) \cdot K_{|V(G)|} \right) * I\left(\overline {K_{1,|V(G)|-1}}\right)^{*k} + \frac{1}{2} \cdot K_{|V(G)|}
\]

is a set of all graphs obtainable from $I(G)$ by changing all edges neighboring to at most $k$ vertices to $\frac{1}{2}$.

Follows from lemma <ref>
When we have some edge which is not a neighbor of any of those vertices then it's weight will be changed by $-\frac{1}{2}$ then times $1$ and $+\frac{1}{2}$, hence it will be the same.
But if we have a vertex neighboring to some of those vertices then it's weight will be changed by $-\frac{1}{2}$ then times $0$ and $+\frac{1}{2}$, hence it will be equal to $\frac{1}{2}$.

Let $G$ be unweighted graph such that $G\neq K_{|V(G)|}$ and $k \in \mathbb{N}$, then
$G$ is vertex $ (k+1) $-connected if and only if for all

\[\begin{aligned}
&H \in \\
&\left(\left(I(G)+ \left(-\frac{1}{2}\right) \cdot K_{|V(G)|} \right) * I\left(\overline {K_{1,|V(G)|-1}}\right)^{*k} + \frac{1}{2} \cdot K_{|V(G)|}\right)* \mathscr{H}_{|V(G)|},
\end{aligned}\]

there exists $e\in E(H)$ such that $v_H(e)=1$ or

\[
H \cong \frac{1}{2} \cdot I(K_{n,|V(G)|-n})
\]

for some $n \in \{1,\dots ,|V(G)|-1 \}$.

\[
\mathscr{H}_{|V(G)|}=\left\{I(K_{n,|V(G)|-n}) ~\middle|~ 1\leq n \leq|V(G)| \right\}.
\]

\begin{align*}
&\left(\left(I(G)+ \left(-\frac{1}{2}\right) \cdot K_{|V(G)|} \right) * I\left(\overline {K_{1,|V(G)|-1}}\right)^{*k} + \frac{1}{2} \cdot K_{|V(G)|}\right)* \mathscr{H}_{|V(G)|}\\
&=\left\{\substack{\text{set of all graphs obtainable from $I(G)$ by changing} \\ \text{all edges neighboring to at most $k$ vertices to $\frac{1}{2}$}} \right\}* \mathscr{H}_{|V(G)|},
\end{align*}

hence whole formula is equal to set of all graphs obtainable from $I(G)$ by changing all edges neighboring to at most $k$ vertices to $\frac{1}{2}$
and then leave only edges between some nonempty proper subset of vertices and it's complement.

Let $G$ be not $(k+1)$-connected we will show that there exists a graph $H$ which does not satisfy given condition. By lemma <ref>
Because $G$ is not a complete graph, know that there exist vertices $v_1,v_2,\dots, v_l \in V(G)$ where $l\leq k$ such that
$G\setminus \{ v_1,v_2,\dots, v_l \}$ is disconnected. Let $C$ be a component of $G\setminus \{ v_1,v_2,\dots, v_l \}$,
if we now consider a graph $H$ in the spectrum from the theorem given by changing all edges neighboring to vertices $\{ v_1,v_2,\dots, v_l \}$ to $\frac{1}{2}$
and then leave only edges between $C\cup \{ v_1,v_2,\dots, v_l \}$ and it's complement. By previous this graph lies in the spectrum and we will show that it not satisfy the condition.
All edges inside sets $C\cup \{ v_1,v_2,\dots, v_l \}$ and $\overline{C\cup \{ v_1,v_2,\dots, v_l \}}$ are $0$,
all edges between $C$ and $\overline{C\cup \{ v_1,v_2,\dots, v_l \}}$ are $0$ and all edges between $ \{ v_1,v_2,\dots, v_l \}$ and $\overline{C\cup \{ v_1,v_2,\dots, v_l \}}$ are $\frac{1}{2}$.
Hence there is no $1$ and it is not isomorphic to $\frac{1}{2} \cdot I(K_{n,|V(G)|-n})$.

For another direction let $G$ be $(k+1)$-connected we will show that all $H$ from the spectrum satisfy the condition. We already know that all $H$ from the spectrum are obtained by a set
$\{ v_1,v_2,\dots, v_l \}\subseteq V(G)$ and a partition in to two nonempty parts $A,\overline{A}\subseteq V(G)$. If $G\setminus \{ v_1,v_2,\dots, v_l \}$
has a nonempty intersection with both $A$ and $\overline{A}$
then because $G\setminus \{ v_1,v_2,\dots, v_l \}$ is connected, there exists at least one edge between $A$ and $\overline{A}$, hence $H$ contains an edge weighted by $1$.

If $A\supseteq G\setminus \{ v_1,v_2,\dots, v_l \}$ (analogously for $\overline{A}$) then $\overline{A} \subseteq \{ v_1,v_2,\dots, v_l \}$
and this means that all edges between $A$ and $\overline{A}$
are weighted by $\frac{1}{2}$ and rest are by previous part $0$, this means that it is isomorphic to $ \frac{1}{2} \cdot I(K_{n,|V(G)|-n})$.

The condition of $G$ not being a complete graph from the previous theorem can be easily said also by combinatorial spectra, it is equivalent to the following condition,

\[
s\left(I(G)*I\left( \bigl(\xymatrix{ \cdot \ar@{-}[r] &\cdot  } \bigr) \sqcup \bigsqcup_{i=1}^{|V(G)|-2} \cdot \right) \right)\neq \{1\}.
\]

Let $n>k \in \mathbb{N}$ then $n \geq R(k,k)$ if and only if

\[
\exists G \in \bigl( 2 \cdot I(K_{n}\setminus e)^{*\infty} + (-1) \cdot K_{n}  \bigr),
\]

such that

\[
-{k \choose 2}   <
s \left( G
*    I\left( K_k \sqcup \bigsqcup_{i=1}^{|V(G)|-k} \cdot   \right) \right)  <  {k \choose 2 },
\]

where $R(k,k)$ is a Ramsey number.

The idea of this condition is generate all graphs and check that there not contains a monochromatic clique.
By lemma <ref> we know that $I(K_{n}\setminus e)^{*\infty}$ is set of $I$ of all graphs of order $n$ up to a complete graph, but the complete graph is irrelevant for Ramsey condition.
Hence $\bigl( 2 \cdot I(K_{n}\setminus e)^{*\infty} + (-1) \cdot K_{n}  \bigr)$ is the set of all colorings of a graph $K_n$ by colors $1,-1$. Now the formula

\[
s \left( G
*    I\left( K_k \sqcup \bigsqcup_{i=1}^{|V(G)|-k} \cdot   \right) \right)
\]

is equal to the set of numbers of $1$ minus numbers of $-1$ in all induced subgraphs of $G$ of order of $k$.
And inequalities say that all these subgraphs are not monochromatic.

§ PROPERTIES

In this section we are going to show some properties of combinatorial spectra.

Let $G$ be a $\mathbb{Z}$-weighted complete graph such that

\begin{equation}\label{huste}
s\left(G*I\left( \bigl(\xymatrix{ \cdot \ar@{-}[r] &\cdot  } \bigr) \sqcup \bigsqcup_{i=1}^{|V(G)|-2} \cdot \right) \right)
= \{1,2,\dots,k\},
\end{equation}

for some $k$,

\[
\bigcup_{H \subseteq K_{|V(G)|}}s(I(H)*G) = \{0,\dots,l\}
\]

where $l$ is the only element of $

Let we have a $m\in \bigcup_{H \subseteq K_{|V(G)|}}(s(I(H)*G))$ such that $m \neq l$ we will show that also
$m+1 \in \bigcup_{H \subseteq K_{|V(G)|}}(s(I(H)*G))$.
\[
m = s(I(H)*_f G),
\]

if there is an edge $e \in E(G)$ such that $v_G(e)= 1$ and $v_{I(H)}(f^{-1} (e))=0$ then we will consider a graph
$H'=H\cup f^{-1}(e)$ and now

\[
m+1=s(I(H')*_f G).
\]

if there is no that edge we will consider a

\[
i=\min \left\{ v_G(e)  \middle| e\in E(G),\, v_{I(H)}(f^{-1} (e))=0  \right\},
\]

this set is non-empty because $m\neq l$ and by the assumption $i\geq 2$.
Let $e_1$ be such an edge for which the set is minimized. By minimality of $i$ and by property (<ref>) there exists an edge $e_2$ such that
$ and $v_{I(H)}(f^{-1} (e_2))=1$. Let now consider a graph $H'= H \cup e_1 \setminus e_2$, this graph again satisfy the condition what we want

\[
m+1=s(I(H')*_f G).
\]

Let $G$ be an unweighted connected graph then

\[
\bigcup_{H \subseteq K_{|V(G)|}}\mathscr{H}_H(G) = \{0,\dots,h^+_{K_{|V(G)|}}(G)\},
\]

where $h^+_{H}(G)=\max\{\mathscr{H}_H(G)\}$.

This corollary is only an application of theorems <ref> and <ref>, the only thing which remains is to check the condition

\[
s\left(\rho (G)*I\left( \bigl(\xymatrix{ \cdot \ar@{-}[r] &\cdot  } \bigr) \sqcup \bigsqcup_{i=1}^{|V(G)|-2} \cdot \right) \right)
= \{1,2,\dots,k\},
\]

but this is obvious, let $v,u\in V(G)$ be vertices with distance $i \geq 2 $, let $v,v_1,\dots,v_{i-1},u$ be a path of minimal length connecting $v$ and $u$ then now the distance between
$v_1$ and $u$ is $i-1$.

Let $R$ be a ring then we have an inclusion

\[
R \hookrightarrow \mathscr{P}(R-Graphs_n)
\]

given by

\[
r \mapsto r\{\cdot I(K_n)\},
\]

respecting the structure.

We would like to say that it is a homomorphism of rings but the right side is not a ring, but if the structure of
$\mathscr{P}(R-Graphs_n)$ has a name (for example ordered weak ring) it will be a homomorphism of that.

\begin{align*}
(r\cdot s)\cdot \{I(K_n)\} &= \left( r\cdot \{I(K_n)\} \right)* \left( s\cdot \{I(K_n)\} \right) \\
(r +  s)\cdot \{I(K_n)\} &= \left( r\cdot \{I(K_n)\} \right)+ \left( s\cdot \{I(K_n)\} \right)
\end{align*}

and it also preserves $0$ and $1$ of these two "weak rings".

Let $R$ be a ring then $R$ is a domain if and only if
\[\mathscr{P}(R-Graphs_n)\]
is a "domain" (this means that it does not contain zero divisors).

Let $R$ be not a domain and $r,s\in R$ such that $ r\cdot s = 0$, then
\[
0=0\cdot I(K_n)=(r\cdot s)\cdot I(K_n)=\left( r\cdot I(K_n) \right)* \left( s\cdot I(K_n) \right)
\]

and this means that $\mathscr{P}(R-Graphs_n)$ is not a domain.

Let now $R$ be a domain and
\[
\mathscr{R},\mathscr{S}\in \mathscr{P}(R-Graphs_n)\text{ such that } \mathscr{R}*\mathscr{S} = \{ 0 \},
\]

where the $0$ means the graph with all edges weighted by $0$.
We will show that one of them is equal to zero. If both of them have nonzero edge $e,e'$ then in $\mathscr{R}*_f  \mathscr{S}$
exists at least one edge weighted by product of weights of $e,e'$ and because $R$ is a domain, this product is nonzero.

Let $H,~G$ be unweighted graphs, where $G$ is connected then

\[h_H (P_{|V(G)|-1}) - \binom{|V(G)|+1}{ 3} +h_{K_{|V(G)|}}(G)
\leq h_H(G),\]

where $h_{H}(G)=\min\{\mathscr{H}_H(G)\}$.
Moreover, if $\overline{H}$ is connected then both sides are equal if and only if $G$ is a complement of a path.

The main theorem of the article [1] is this:

\[
h^+ (G)\leq h^+_H (P_{|V(G)|-1})
\]

moreover, if $H$ is connected then both sides are equal if and only if $G$ is a path. If we translate it by the theorem <ref>
we will get this

\[
\max s(I(H)* \rho(G))\leq \max s(I(H)* \rho(P_{|V(G)|-1})).
\]

Let us substitute there $H=K_{|V(G)|}\setminus H$ and make the following computation.

\begin{align*}
\text{LHS}&\overset{\phantom{T\ref{diststrict}}}{=}\max s\bigl(I(K_{|V(G)|}\setminus H)* \rho(G)\bigr)\\
&\overset{\phantom{T\ref{diststrict}}}{=}\max s\bigl( (I(K_{|V(G)|})+ (-1) \cdot I(H) ) * \rho(G)   \bigr)\\
&\overset{T\ref{diststrict}}{=}\max\bigl(s\bigl(I(K_{|V(G)|}) *\rho(G)\bigr) - s(I(H)* \rho(G))\bigr),\\
&\overset{\phantom{T\ref{diststrict}}}{=}s\bigl(I(K_{|V(G)|}) *\rho(G)\bigr) - \min s(I(H)* \rho(G)).
\end{align*}

Theorem <ref> can be used because

\[
|s\left((-1) \cdot I(K_{|V(G)|})* \rho(G)\right)|=1.
\]

\begin{align*}
\text{RHS}&\overset{\phantom{T\ref{diststrict}}}{=}\max s\bigl(I(K_{|V(G)|}\setminus H)* \rho(P_{|V(G)|-1})\bigr)\\
&\overset{\phantom{T\ref{diststrict}}}{=}s\bigl(I(K_{|V(G)|}) *\rho(P_{|V(G)|-1})\bigr) - \min s\bigl(I(H)* \rho(P_{|V(G)|-1})\bigr).
\end{align*}

\begin{align*}
&\min s\bigl(I(H)* \rho(P_{|V(G)|-1})\bigr) - s\bigl(I(K_{|V(G)|}) *\rho(P_{|V(G)|-1})\bigr) + \\
& \phantom{ssssssssssssssssssssssssssssssssssssssss} +s\bigl(I(K_{|V(G)|}) *\rho(G)) \\
&\leq \min s(I(H)* \rho(G)\bigr).
\end{align*}

The last thing is that

\begin{align*}
s&\bigl(I(K_{|V(G)|}) *\rho(P_{|V(G)|-1}) \\
&= \bigl(1+2+\dots + (|V(G)|-1) \bigr) + \bigl(1 +2 + \dots + ( |V(G)|-2)\bigr) +  \dots + \bigl( 1 \bigr)\\
&= \binom{|V(G)|}{2} + \binom{|V(G)|-1}{2}+ \dots + \binom{2}{2} = \binom{|V(G)|+1}{3}.
\end{align*}

Now we are going to show some sufficient conditions for $|s(H*G)|=1$, as we know from Theorem <ref> and Lemma <ref>, couples of graphs (or sets of graphs) with this property
satisfy strict distributivity, hence they are good for calculations as we have seen in previous Theorem. We would like to have much more of those couples. For this aim we are going to introduce the following relation on the set of pseudoorderings.

Let $G$ and $H$ be $R$-weighted complete graphs and two pseudorderings

\[
g,f:H \rightarrow G.
\]

We will define a relation $\sim$ by the following

\begin{align*}
f&\sim g, \text{  if and only if  } \\
\exists \varphi \in \Aut{H},\, &\exists\psi \in \Aut{G}
\text{  such that  }  g=\psi \circ f \circ  \varphi.
\end{align*}

The relation $\sim$ is an equivalence relation.

It is reflective

\[
id \circ f \circ id = f,~ id\in \Aut{H},\, id\in \Aut{G}
\]

It is symmetric, let

\[
g=\psi \circ f \circ  \varphi,~ \varphi\in \Aut{H},\, \psi\in \Aut{G},
\]

\[
f=\varphi^{-1} \circ g \circ  \psi^{-1}, ~ \psi^{-1} \in \Aut{G},\, \varphi^{-1} \in \Aut{H}.
\]

It is also transitive, let

\[
f\sim g, g\sim h,
\]

this is equivalent to

\[
g=\psi \circ f \circ \varphi,~ h= \psi' \circ g \circ \varphi', ~\varphi,\varphi'\in \Aut{H},\, \psi,\psi'\in \Aut{G}
\]

\[
h= \psi' \circ \psi \circ f \circ \varphi \circ \varphi',~ \psi' \circ \psi\in \Aut{G},\, \varphi \circ \varphi'\in  \Aut{H}.
\]

\[
g(H)*_f G \overset{\phantom{bb}g^{-1}}{\cong} H*_{f\circ g} G = H*_g f^{-1}  (G).
\]

Lets prove the second part $H*_{f\circ g} G = H*_g f^{-1}  (G)$.

\[
v_{H*_{f\circ g} G}(e)=v_H(e) \cdot v_G (f(g(e)))
\]

\[
v_{H*_g f^{-1}  (G)}(e)=v_H(e) \cdot v_{f^{-1}  (G)}(g(e)) = v_H(e) \cdot v_{G}(f(g(e))).
\]

For the first part we need to show that

\[
v_{g(H)*_f G}(g(e)) = H*_{f\circ g} G,
\]

\[
v_{g(H)*_f G}(g(e)) = v_{g(H)}(g(e)) \cdot v_G (f(g(e)))= v_{H}(e) \cdot v_G (f(g(e))).
\]

Let $H$ and $G$ be $R$-weighted complete graphs (or unweighted graphs)
we denote a set of all pseudoorderings as follows

\[
pso(H,G)=\{f: V(H)\rightarrow V(G)|f \text{ bijection}\}.
\]

Let $H,~G$ be $R$-weighted complete graphs then the map
\[
H*_{-} G: pso(H,G)\rightarrow H*G
\]

converts $\sim$ in to an isomorphism.

\[
g=\psi \circ f \circ  \varphi,~ \varphi\in \Aut{H},\, \psi\in \Aut{G},
\]

\[
H*_{\psi \circ f \circ  \varphi} G \overset{L \ref{l13}}{=} H*_{ f \circ  \varphi}  \psi^{-1}( G) \overset{\psi\in \Aut{G}}{=}
H*_{ f \circ  \varphi} G \overset{\substack{ L \ref{l13}\\ \varphi}}{\cong } \varphi(H)*_f G \overset{\varphi\in \Aut{H}}{=}
H*_f G.
\]

Let $H,~G$ be $R$-weighted complete graphs then

\[
\left|\sfrac{pso(H,G)}{\sim} \right|=1 \implies |H\*G|=1.
\]

If any two pseudoorderings $f$ and $g$ are in relation $f\sim g$ then by the proposition <ref> are get isomorphic elements of combinatorial spectrum

\[
H*_f G \cong H*_g G,
\]

hence if all are isomorphic then

\[
\]

Let $H,~G$ be $R$-weighted complete graphs then

\[
\left|\sfrac{pso(H,G)}{\sim} \right|=1 \implies |s(H*G)|=1.
\]

Let $H,~G$ be $R$-weighted complete graphs with the same set of vertices then

\[
\Aut{G} \circ \Aut{H}= pso(H,G) \implies |H\*G|=1 \implies |s(H*G)|=1.
\]

The condition of having the same set of vertices is only for a simplification of the statement we know that a combinatorial spectrum
will not changed if we replace a graph by some isomorphic one. This means that we can all our graphs consider with the set of vertices $\{1,\dots,|V(G)|\}$.

We will show that

\[
\Aut{G} \circ \Aut{H}= pso(H,G) \implies \left|\sfrac{pso(H,G)}{\sim} \right|=1,
\]

then it is enough to use the theorem <ref>.
Let $f\in pso(H,G)$, by the condition above there exist $\psi \in \Aut{G},\,\varphi \in \Aut{H}$, such that

\[
\psi \circ \varphi = f.
\]

This we can rewrite as

\[
f=\psi \circ id \circ \varphi
\]

and this is by the definition $id \sim f$. And now if all pseudoorderings are in $\sim $ with $id$ then

\[
\left|\sfrac{pso(H,G)}{\sim} \right|=1.
\]

Assuming the same set of vertices, it is even an equivalence

\[
\Aut{G} \circ \Aut{H}= pso(H,G) \iff \left|\sfrac{pso(H,G)}{\sim} \right|=1.
\]

It remains to show the implication from right to left.
Let $f\in  pso(H,G)$, it is in relation $id\sim f$ this means that

\[
f=\psi \circ id \circ  \varphi=\psi \circ  \varphi ,~ \varphi\in \Aut{H},\, \psi\in \Aut{G},
\]

hence $f\in \Aut{G} \circ \Aut{H}$.

It also holds

\[
\Aut{G} \circ \Aut{H}= pso(H,G) \iff \Aut{H} \circ \Aut{G}= pso(H,G).
\]

This can be proven by applying $\phantom{a}^{-1}$,

\begin{align*}
(\Aut{G} \circ \Aut{H})^{-1}&= \left(pso(H,G) \right)^{-1}\\
\Aut{H}^{-1} \circ \Aut{G}^{-1}&= \left(pso(H,G) \right)^{-1}\\
\Aut{G} \circ \Aut{H}&= pso(H,G).
\end{align*}

Let $G$ be an unweighted graph then

\[
\Aut{G}=\Aut{I(G)}=\Aut{\rho(G)}.
\]

First equation is obvious. Let $\varphi \in \Aut{G}$ it is also an
isomorphism of $\rho(G)$ because isomorphisms preserves distances.

Let $\varphi \in \Aut{\rho(G)}$ because

\[
U_1(\rho(G))= G,
\]

hence it is also an isomorphism of $G$.

The opposite implication from the corollary <ref> does not hold,

\[
|s(H*G)|=1 \notimplies \Aut{G} \circ \Aut{H}= pso(H,G).
\]

Let us denote the following graph by $H'$.

[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm]
(-0.56,-3.34) rectangle (8.25,3.74);
[color=zzttqq,fill=zzttqq,fill opacity=0.1] (0,1) – (0,-1) – (1.9,-1.62) – (3.08,0) – (1.9,1.62) – cycle;
[color=zzttqq,fill=zzttqq,fill opacity=0.1] (8,-1) – (8,1) – (6.1,1.62) – (4.92,0) – (6.1,-1.62) – cycle;
[color=zzttqq] (0,1)– (0,-1);
[color=zzttqq] (0,-1)– (1.9,-1.62);
[color=zzttqq] (1.9,-1.62)– (3.08,0);
[color=zzttqq] (3.08,0)– (1.9,1.62);
[color=zzttqq] (1.9,1.62)– (0,1);
[color=zzttqq] (8,-1)– (8,1);
[color=zzttqq] (8,1)– (6.1,1.62);
[color=zzttqq] (6.1,1.62)– (4.92,0);
[color=zzttqq] (4.92,0)– (6.1,-1.62);
[color=zzttqq] (6.1,-1.62)– (8,-1);
(3.08,0)– (4.92,0);
(3.08,0)– (4.92,0);
(1.9,1.62)– (0,-1);
(0,1)– (1.9,-1.62);
(6.1,1.62)– (8,-1);
(8,1)– (6.1,-1.62);

[color=xdxdff] (0,1) circle (1.5pt);
[color=xdxdff] (0,-1) circle (1.5pt);
[color=uququq] (1.9,-1.62) circle (1.5pt);
[color=uququq] (3.08,0) circle (1.5pt);
[color=uququq] (1.9,1.62) circle (1.5pt);
[color=qqqqff] (8,1) circle (1.5pt);
[color=qqqqff] (8,-1) circle (1.5pt);
[color=uququq] (6.1,1.62) circle (1.5pt);
[color=uququq] (4.92,0) circle (1.5pt);
[color=uququq] (6.1,-1.62) circle (1.5pt);

And $G'=K_{9,1}$,
we will prove that $H=I(H'),~ G=\rho(G')$ is a counterexample.

\begin{align*}
&\overset{\ref{thmdeg}}{=}2\{|E(H')|\}-\{deg_H(v)|v\in V(H)\}\\
\end{align*}

\[\Aut{\rho(G)} \circ \Aut{I(H)}= pso(H,G)
\]

was satisfied then it would be satisfied also

\[
pso(H,G)= \Aut{I(H)} \circ   \Aut{\rho(G)}  = \Aut{\rho(H)} \circ   \Aut{I(G)}
\]

and then would be by corollary <ref>

\[
\]

But this is not true, if we consider two pseudoorderings, $f$ sending a vertex on the side to a center and $g$ sending some of the vertices on the bridge to a center,
we will get that $s(\rho(H)*_f I(G))>s(\rho(H)*_g I(G))$.

Let $H,\,G$ be $R$-weighted complete graphs we define

\[
H \perp G \text{  if and only if  }  |s(H*G)|=1.
\]

Let $\mathscr{G},\,\mathscr{H}$ be classes of $R$-weighted complete graphs we define

\[
\mathscr{H} \perp \mathscr{G} \text{  if and only if  }  \forall H \in \mathscr{H}, \, \forall G \in \mathscr{G}: ~ H\perp G.
\]

Let $\mathscr{H}$ be a class of $R$-weighted complete graphs we define a class

\[
{\mathscr{H}}^{\perp}= \{ G \,|\,\forall H \in \mathscr{H} :~ H\perp G \}.
\]

Let $H$ be a $R$-weighted complete graph we denote

\[
\]

\[
I^{-1}\left(I(S_n)^{\perp}\right)=\{\text{set of all regular graphs of order }n\}
\]

where $S_n=K_{1,n-1}$.

\[
I^{-1}\left(I(S_n)^{\perp}\right)=\{ H \,| I(H)\perp I(S_n) \},
\]

from the theorem <ref> we know that $s(I(H)*I(S_n))$ is a set of degrees of $H$, if it must
be one element set that means it is a regular graph.

\[
I^{-1}\left(\rho(S_n)^{\perp}\right)=\{\text{set of all regular graphs of order }n\}.
\]

We can prove it in similar way as before or we can do it better.
We will prove that

\[
I(S_n)^{\perp}= \rho(S_n)^{\perp}.
\]

All distances in $S_n$ are $1$ or $2$, this leads us to a formula

\[
\rho(S_n)= 2I(K_n) - I(S_n),
\]

now by the theorem <ref> is
\begin{align}
s(H*\rho(S_n))&=\underbrace{2s(H*I(K_n))}_{\text{one number}} ~+~ s((-1)H*I(S_n))\notag\\
s(H*\rho(S_n))&=\underbrace{2s(H*I(K_n))}_{\text{one number}} ~-~ s(H*I(S_n))\notag
\end{align}

\[
I(S_n)^{\perp}= \rho(S_n)^{\perp}.
\]

From the previous proof we can get a proposition

Let $G$ be an unweighted graph with diameter at most $2$ then

\[
I(G)^{\perp}= \rho(G)^{\perp}.
\]

Let $\mathscr{H},\,\mathscr{G}$ be classes of $R$-weighted complete graphs and $\mathscr{A}\subseteq \mathscr{P}(R)$, we define

\[
\mathscr{H} \perp_{\mathscr{A}} \mathscr{G} \text{  if and only if  }  \forall H \in \mathscr{H}, \, \forall G \in \mathscr{G}: ~ s(H*G)\in \mathscr{A}.
\]

Analogously we define a set

\[
{\mathscr{H}}^{\perp_{\mathscr{A}}}= \{ G \,|\,\forall H \in \mathscr{H} :~ s(H*G)\in \mathscr{A} \}.
\]

Let $\mathscr{A}\subseteq \mathscr{P}(R)$ be a set closed under $+$ and under multiplication by an element of $R$ and it is closed under subsets (this we will call an ideal), then

\[
\]

is closed under $+$, multiplication by an element of $R$.

Let $G,G'\in {\mathscr{H}}^{\perp_{\mathscr{A}}}$, this means that

\[
\forall H \in \mathscr{H} :~ s(H*G),s(H*G')\in \mathscr{A}.
\]

By the theorem <ref>

\[
s(H*(G+G'))\subseteq s(H*G) + s(H*G'),
\]

because $s(H*G),s(H*G')\in \mathscr{A}$ then by the assumptions also $s(H*G) + s(H*G')\in \mathscr{A}$ and then also $s(H*(G+G'))\in \mathscr{A}$.

Let now $G\in {\mathscr{H}}^{\perp_{\mathscr{A}}}$ and $r\in R$, this means that

\[
\forall H \in \mathscr{H} :~ s(H*G)\in \mathscr{A},
\]

\[
\forall H \in \mathscr{H} :~ s(H*(r\cdot G))\in \mathscr{A} \iff \forall H \in \mathscr{H} :~ r\cdot s(H*G)\in \mathscr{A}
\]

and the right hand side is true by assumptions.

\[
I^{-1}\left(\rho(\{\text{connected bipartite graphs}\})^{\perp_{\mathscr{P}(2\mathbb{Z})}} \right)=\{\text{GWEC}\},
\]

Where GWEC means graphs with Eulerian components.

At first we will prove that for $n\in \mathbb{N},\, n\leq |V(G)|$ is satisfied

\[
s\left(I\left(C_{n}\sqcup \bigsqcup_{i=1}^{|V(G)|-n} \cdot \right) * \rho(G)\right) \in \mathscr{P}(2\mathbb{Z}),
\]

for $G$ connected bipartite graph. Let $A,\overline{A} \subseteq V(G)$ such that all edges of $G$ are between $A$ and $\overline{A}$.
All distances between these two sets are odd and all distances inside these two sets are even.

\[
s\left(I\left(C_{n}\sqcup \bigsqcup_{i=1}^{|V(G)|-n} \cdot \right)*_f \rho(G)\right)=\sum_{i=1}^{n_a} a_i + \sum_{j=1}^{n_b} b_j
\]

where $a_i$ is even and $b_j$ is odd and $n_b$ is even.
Indeed, $n_b$ is a number of edges
\[
\{u,v\}\in E \left(C_{n}\sqcup \bigsqcup_{i=1}^{|V(G)|-n} \cdot \right)
\]

such that $|\{f(u),f(v)\}\cap A|=1$ and this needs to be even because as many times
a cycle
\[
f\left(\left(C_{n}\sqcup \bigsqcup_{i=1}^{|V(G)|-n} \cdot \right)\right) \]

leaves $A$ as many times it needs to come back.

The set $\mathscr{P}(2\mathbb{Z})$ is an ideal, by the theorem <ref>
\[\rho(\{\text{connected bipartite graphs}\})^{\perp_{\mathscr{P}(2\mathbb{Z})}}\]

closed under $+$,

\[
I^{-1}\left(\rho(\{\text{connected bipartite graphs}\})^{\perp_{\mathscr{P}(2\mathbb{Z})}} \right)
\]

is closed under disjoint unions. We have proven that

\[
\left(C_{n}\sqcup \bigsqcup_{i=1}^{|V(G)|-n} \cdot\right) \in I^{-1}\left(\rho(\{\text{connected bipartite graphs}\})^{\perp_{\mathscr{P}(2\mathbb{Z})}} \right),
\]

then also all disjoint unions of these graphs are also in this set. Any graph with Eulerian components can be written as disjoint union of graphs of the shape

\[
C_{n}\sqcup \bigsqcup_{i=1}^{|V(G)|-n} \cdot,
\]

\[
\{\text{GWEC}\}\subseteq I^{-1}\left(\rho(\{\text{connected bipartite graphs}\})^{\perp_{\mathscr{P}(2\mathbb{Z})}} \right).
\]

Let now
\[
G\in I^{-1}\left(\rho(\{\text{connected bipartite graphs}\})^{\perp_{\mathscr{P}(2\mathbb{Z})}} \right)
\]

this at least means that

\[
s\left(I(G)*\rho(K_{1,|V(G)|-1})\right)\in \mathscr{P}(2\mathbb{Z}).
\]

We know that

\[
\rho\left(K_{1,|V(G)|-1}\right)=2\cdot I\left(K_{|V(G)|}\right)-I\left(K_{1,|V(G)|-1}\right)
\]

it is explained in the proof of the proposition <ref>.

\begin{align*}
I(G) &*\rho
& =s\left(I(G)*\left(2\cdot I\left(K_{|V(G)|}\right)-I\left(K_{1,|V(G)|-1}\right)\right)\right)\\
& =2s\left(I(G)*I\left(K_{|V(G)|}\right)\right)-s\left(I(G)*I\left(K_{1,|V(G)|-1}\right)\right),
\end{align*}

\[
s\left(I(G)*\rho(K_{1,|V(G)|-1})\right)\in \mathscr{P}(2\mathbb{Z}) \iff s\left(I(G)*I(K_{1,|V(G)|-1})\right)\in \mathscr{P}(2\mathbb{Z}).
\]

By the theorem <ref> we know that
s\left(I(G)*I(K_{1,|V(G)|-1})\right)$ is equal to set of degrees of $G$, hence we get that all degrees of $G$ are even and this means that $G$
has Eulerian components. And this gives us the second inequality

\[
\{\text{GWEC}\}\supseteq I^{-1}\left(\rho(\{\text{connected bipartite graphs}\})^{\perp_{\mathscr{P}(2\mathbb{Z})}} \right).
\]

[1] Dzúrik, M. (2021). An upper bound of a generalized upper Hamiltonian number of a graph. Archivum Mathematicum, (5), 299–311. https://doi.org/10.5817/am2021-5-299