# Reduced superfluid density in a doped spin liquid candidate

K. Wakamatsu1 Y. Ueno1 K. Miyagawa1 H. Taniguchi2 K. Kanoda1,∗ 1Department of
Applied Physics, University of Tokyo, Bunkyo-ku, Tokyo, 113-8656, Japan
2Graduate School of Science and Engineering, Saitama University, Saitama
338-8570, Japan

###### Abstract

A quantum spin liquid (QSL) would be an exotic stage for superconductivity. A
promising candidate for a doped QSL is the organic triangular-lattice system,
$\kappa$-(BEDT-TTF)4Hg2.89Br8, which hosts a non-Fermi liquid and magnetism of
a QSL nature and shows superconductivity upon cooling. Here, we report that
its superfluid density is anomalously reduced, indicating the existence of
substantial incoherent spectral weight and weak superconducting phase
stiffness. Moreover, the ratio of the superconducting transition temperature
to the nominal Fermi temperature is as large as 0.1, orders of magnitude
beyond typical BCS values. These observations in a system free from competing
orders that complicate the similar issue in underdoped cuprates give a clue to
the enigmatic missing superfluid density in doped Mott insulators.

The superfluid density, a spectral weight contributing to superconducting
condensates, determines the fundamental nature of superconductivity, such as
phase stiffness [1], and thus closely pertains to phase fluctuations. A
quantum spin liquid (QSL) is a nontrivial magnetic state free from order and
possibly bearing fractionalization, entanglement and/or chirality [2, 3, 4].
The superconductivity that emerges by doping such an anomalous magnetic state
[5, 6, 7, 8, 9] is of keen interest with regard to the unconventional pairing
nature out of a BCS framework. In the absence of adequate model materials that
address this question, the layered organic conductor with a triangular
lattice, $\kappa$-(BEDT-TTF)4Hg2.89Br8 ($\kappa$-HgBr) [10], has recently
arisen as a promising doped QSL candidate. The present work experimentally
investigates the nature of superconductivity that emerges in this system in
terms of the superfluid density, which is a key parameter to elucidate the
possible unconventionality of pairing.

$\kappa$-HgBr has a quasi-two-dimensional structure with insulating and
conducting layers alternately stacked, and both layers have monoclinic
sublattices [12, 13]. In the conducting layers, the ET molecules form dimers,
which constitute a quasi-triangular lattice characterized by two kinds of
transfer integrals, $t$ and $t^{\prime}$, between the adjacent dimer molecular
orbitals (Fig. 1(a)). According to the molecular orbital calculations, the
ratio, $t^{\prime}/t$, in $\kappa$-HgBr is 1.02 [11], which means a nearly
right triangular lattice. Although most $\kappa$-(ET)${}_{2}X$ compounds have
half-filled bands, or equivalently, one hole carrier per dimer because of the
monovalent anion $X^{-1}$, the band filling in $\kappa$-HgBr deviates from
half by 0.055 assuming Hg+2 and Br-1 because of the nonstoichiometric
composition of Hg, 2.89; if it is 3.0, the band filling will be half. The
compositional ratio of $4.0:2.89:8.0$ that results from the incommensurate
sublattice of Hg against ET and Br is precisely determined by x-ray
diffraction [12, 13] and cannot be varied. The band-filling deviation from
half corresponds to 11% hole doping to the half-filled band and is consistent
with Raman spectroscopy [14].

Several experiments indicate that $\kappa$-HgBr is a hole-doped version of the
QSL candidate, $\kappa$-(BEDT-TTF)2Cu2(CN)3, hosting a similar triangular
lattice and comparable or larger electron correlation [11]. The resistivity
and Hall coefficient [15] show that $\kappa$-HgBr hosts a non-Fermi liquid
with the effective carrier density largely reduced from that of the total band
electrons, suggesting that strong electron correlation prohibits double
occupancy as if mobile carriers are restricted to doped holes. Interestingly,
the spin susceptibility of $\kappa$-HgBr is nearly perfectly scaled to that of
$\kappa$-(BEDT-TTF)2Cu2(CN)3. $\kappa$-HgBr is thus regarded as a hole-doped
version of $\kappa$-(BEDT-TTF)2Cu2(CN)3. Notably, superconductivity that
appears at low temperatures is suggested to be of an unconventional nature out
of the BCS picture in that the Cooper pairs are barely overlapping, saliently
robust to the magnetic field and preformed prior to their condensate [16, 17],
reminiscent of BEC-like pairing (Fig. 1(b)). The superfluid density ns of such
unconventional condensates is of profound interest. The present work
investigates $n_{\textrm{s}}$ in this doped spin liquid candidate.

We evaluated the $n_{\textrm{s}}$ value by measuring the in-plane magnetic
penetration depth, $\lambda_{\parallel}$, whose inverse square is related to
$n_{\textrm{s}}$ as
$1/\lambda_{\parallel}^{2}=\mu_{0}n_{\textrm{s}}e^{2}/m^{\ast}$ ($\mu_{0}$:
magnetic permeability, $n_{\textrm{s}}$: superfluid density, $e$: elementary
charge, $m^{\ast}$: effective mass). Among several experimental ways to
estimate the $\lambda_{\parallel}$ value, we employed a method to evaluate it
from the magnetization curve, as decribed later. The magnetization was
measured with Quantum Design SQUID magnetometers (MPMS-XL and MPMS-5S), where
a crystal was fixed to a plastic-straw sample holder with a Kapton film. The
net sample magnetization was obtained as the difference between the
magnetizations with and without the sample. The sample used in the present
work is a rhombic single crystal with diagonal lengths of $\sim$2 and
$\sim$2.3 mm, a thickness of $\sim$0.5 mm and a weight of $\sim$3 mg. To date,
the difficulty in obtaining crystals showing bulk superconductivity at ambient
pressure has prohibited experimental access at ambient pressure [15]. The
present work at ambient pressure was, nevertheless, made possible by
confirming the bulk superconductivity in the used crystal in terms of the ac
susceptibility (Fig. 1(c)). Spin susceptibility in the normal state was also
confirmed to reproduce the earlier results (Fig. 1(d)).

$\lambda_{\parallel}$ can be deduced from the field dependence of the
magnetization, $M(H)$, in the reversible field region under a magnetic field
applied perpendicular to the layers. The $M(H)$ for strong type II
superconductors with $\kappa=\lambda_{\parallel}/\xi_{\parallel}\gg 1$
($\xi_{\parallel}$; the in-plane superconducting coherence length) is
expressed by

$-4\pi
M=(\alpha\phi_{0}/8\pi\lambda_{\parallel}^{2})\ln(\beta{H_{\textrm{c2}\perp}}/H)$
(1)

for a field range of $H_{\textrm{c1}\perp}\ll H_{\textrm{irr}}<H\ll
H_{\textrm{c2}\perp}$ ($H_{\textrm{irr}}$: irreversible magnetic field above
which the magnetization is reversible, $H_{\textrm{c2}\perp}$: perpendicular
upper critical field, $\phi_{0}$: flux quantum, $\alpha$: core contribution
factor, $\beta$: a constant of the order of unity) [18]. In this field range,
vortices are free from collective pinning, and magnetization is reversible
against field sweeps. According to Eq. (1), $dM/d(\ln H)$ gives an estimate of
$\lambda_{\parallel}$. As the correction factor $\alpha$ from the London
model, which does not consider the vortex core contribution, we employed
$\alpha$ = 0.77, a value obtained in Ref. [19]. The $M(H)$ curves at fixed
temperatures were measured under upward and downward field sweeps in the range
of 0-5 T. Fig. 2(a) and 2(b) shows the $M(H)$ curve of $\kappa$-HgBr at 1.8 K
along with that of the half-filled system $\kappa$-Br at 5 K (the same reduced
temperature, $T/T_{\textrm{c}}\sim$0.42) for comparison. $\kappa$-HgBr
exhibits a peak in $M(H)$ at $H_{\textrm{p}}$ = 30 Oe and reversible behavior
above $H_{\textrm{irr}}$ = 300 Oe; both the $H_{\textrm{p}}$ and
$H_{\textrm{irr}}$ values are approximately an order of magnitude below those
in $\kappa$-Br [20], suggesting that the superconductivity in $\kappa$-HgBr is
highly resilient to magnetic fields. Accordingly, the temperature dependence
of $H_{\textrm{irr}}$ shows that the vortex liquid phase is largely extended
in the $H-T$ plane in $\kappa$-HgBr in comparison with $\kappa$-Br (Fig.
2(c)). The extended vortex liquid state in superconductivity with BEC-like
character is theoretically suggested [21]. Magnetization curves above
$H_{\textrm{irr}}$ at several temperatures are shown in Fig. 3(a). The gray
lines indicate the fits of Eq. (1), and their slopes correspond to
$(\alpha\phi_{0}/8\pi)[1/\lambda_{\parallel}(T)^{2}]$. The fit also yields the
values of $\beta H_{\textrm{c2}\perp}$, which is approximately 50 T at 2 K.
Conventionally, the $\beta$ value ranges from 1-2, e.g., 1.44 in the case of
$\alpha$ = 0.77 [19]. $H_{\textrm{c2}_{\perp}}$ of $\kappa$-HgBr at low
temperatures is reported to be $\sim$15 T by torque measurements [17] and
largely exceeds 9 T (the highest field studied) by the Nernst effect, which is
susceptible to vortex liquidity [16], suggesting an extraordinarily large
$H_{\textrm{c2}\perp}$ for $T_{\textrm{c}}$ = 4.2 K. Nevertheless, the $\beta$
value in $\kappa$-HgBr likely exceeds the conventional range; probably,
$\beta$ = 3-4. Although there is an argument on possible modifications of Eq.
(1) [22], considering that the $\beta$ in $\kappa$-Br takes a conventional
value approximately in the range of 1-2 [20, 23], the large $\beta$ value may
characterize the peculiar nature of superconductivity in $\kappa$-HgBr. The
temperature dependence of 1/$\lambda_{\parallel}(T)^{2}$ is shown in Fig.
3(b). The 1/$\lambda_{\parallel}(T)^{2}$ data are fitted by the formula
$1/\lambda_{\parallel}(T)^{2}=1/\lambda_{\parallel}(0)^{2}\times(1-(T/T_{\textrm{c}})^{p})$
with exponent $p$, penetration depth $\lambda_{\parallel}(0)$ and
$T_{\textrm{c}}$ as fitting parameters. The gray line is the best fit with $p$
= 2.4, $\lambda_{\parallel}(0)$ = 1820 nm and $T_{\textrm{c}}$= 4.0 K and, for
reference, the dotted line indicates a fit with $p$ fixed at the empirically
adopted value, 2, which yields $\lambda_{\parallel}(0)$ = 1740 nm and
$T_{\textrm{c}}$ = 4.0 K. The $\lambda_{\parallel}(0)$ value in $\kappa$-HgBr
is three to four times larger than those in the half-filled systems: 490-650
nm in $\kappa$-Br [20, 24, 25] and 430-535 nm in $\kappa$-NCS [25, 26]. With
these $\lambda_{\parallel}(0)$) values, the relation
$1/\lambda_{\parallel}^{2}=\mu_{0}n_{\textrm{s}}e^{2}/m^{\ast}$ yields
$n_{\textrm{s}}/m^{\ast}=9.4\times 10^{54}$, $1.0(\pm 0.3)\times 10^{56}$, and
$1.4(\pm 0.3)\times 10^{56}$ (m3kg)-1 in $\kappa$-HgBr, $\kappa$-Br and
$\kappa$-NCS, respectively (Fig. 4(a)). Further assuming that $m^{\ast}$ is
proportional to the specific heat $\gamma$, which is 55-57 mJ/K2mol for
$\kappa$-HgBr [17, 27], 22-28 mJ/K2mol for $\kappa$-Br [28, 29] and 25-35
mJ/K2mol for $\kappa$-NCS [29, 30], and considering the conducting plane
cross-sectional area of the unit cell, one obtains $n_{\textrm{s}}=4.9\times
10^{19}$, $2.0(\pm 0.6)\times 10^{20}$, and $3.3(\pm 0.9)\times 10^{20}$
(cm)-3 in $\kappa$-HgBr, $\kappa$-Br and $\kappa$-NCS, respectively (Fig.
4(b)). $\kappa$-Br is located very close to the Mott transition [31], which
may be responsible for the smaller $n_{\textrm{s}}$ value in $\kappa$-Br than
in $\kappa$-NCS even in the half-filled case. These values give the relative
ratio of the superfluid density as
$n_{\textrm{s}}(\kappa$-HgBr)/$n_{\textrm{s}}(\kappa$-NCS) = 15$\pm$4% or
$n_{\textrm{s}}(\kappa$-HgBr)/$n_{\textrm{s}}(\kappa$-Br) = 25$\pm$8%.
Clearly, the superfluid density in $\kappa$-HgBr is significantly reduced from
that of the half-filled systems, suggesting that only a fractional spectral
weight approximately equivalent to the doped hole density contributes to the
superconducting condensate. This behavior is called gossamer
superconductivity, which is argued to emerge in doped Mott insulators.

The superfluid density is related to the phase stiffness, which is expressed
as $\hbar^{2}d$/4$\mu_{0}e^{2}\lambda_{\parallel}^{2}$ ($d$: interlayer
distance) and yields approximately 4 K in $\kappa$-HgBr. This value is
considerably smaller than the values of the BCS case, typically 104-105 K [1].
As the phase stiffness measures the macroscopic phase coherence in energy,
this small value in $\kappa$-HgBr is consistent with the previously observed
field resilience and strong fluctuations in superconductivity [16, 17]. From
the penetration depth, the nominal Fermi temperature $T_{\textrm{F}}$ is
evaluated through the relation $k_{\textrm{B}}T_{\textrm{F}}$ =
$\pi\hbar^{2}d$/$\mu_{0}e^{2}\lambda_{\parallel}^{2}$ [32] to be approximately
45 K, which gives a ratio, $T_{\textrm{c}}/T_{\textrm{F}}$, of $\sim$0.09.
This is a large value beyond the BCS framework, where $T_{\textrm{c}}$ is
several orders of magnitude smaller than $T_{\textrm{F}}$. $\kappa$-HgBr is
located in the unconventional pairing region in the $T_{\textrm{c}}$ versus
$T_{\textrm{F}}$ plane (so-called Uemura plot), as shown in Fig. 4(c) [32, 33,
34, 35].

As seen above, the superfluid density takes a reduced value as if only the
doped carriers condense into the superconducting state. Such behavior is
reminiscent of underdoped cuprates, in which the normal-state carrier density
[36], the Drude weight [37] and the superfluid density [32, 38] are discussed
to be governed by the doped carriers. Theoretically, such a significant
reduction in the superfluid density is suggested to occur when double
occupancies of particles are strongly prohibited [6, 39, 40]. Previous
transport studies on $\kappa$-HgBr at low pressures revealed that the mobile
carriers are in a quantum critical state with a spin-liquid background [15,
16, 41, 42], which may bring about an incoherent part, preventing the entire
spectral weight from contributing to the conduction and/or superconducting
condensate. It is argued for underdoped cuprates that some competing or hidden
orders are responsible for the reduction in the superfluid density [43]
because various orders or anomalies appear in the spin and charge degrees of
freedom competing with superconductivity [44, 45]. In this respect,
$\kappa$-HgBr is distinct from cuprates in that no such competing orders have
ever been observed, probably because a QSL free form order is the mother phase
of the superconductivity. Although in recent years the possibility of
competing orders in doped triangular lattices has theoretically suggested in
certain parameter spaces [46, 47], the observation of a considerable reduction
in the superfluid density without apparent competing orders in the present
system would offer a focused target to diverse theoretical challenges with
regard to the issue of missing superfluid spectral weight.

###### Acknowledgements.

This work was supported by Japan Society for the Promotion of Science (grant
Nos. 18H05225, 19H01846, 20K20894, 20KK0060, 21K18144), JST SPRING (grant
JPMJSP2108), and the Mitsubishi Foundation (grant 202110014). Several
experiments were performed using facilities of the Cryogenic Research Center,
the University of Tokyo.

∗Corresponding author, e-mail<EMAIL_ADDRESS>
## References

  * [1] V. J. Emery, and S. A. Kivelson, Importance of phase fluctuations in superconductors with small superfluid density. Nature 374, 434 (1995).
  * [2] Y. Zhou, K. Kanoda, and T.-K. Ng, Quantum spin liquid states. Rev. Mod. Phys. 89, 025003 (2017).
  * [3] L. Savary, and L. Balents, Quantum spin liquids: A review. Rep. Prog. Phys. 80, 016502 (2017).
  * [4] C. Broholm, R. J. Cava, S. A. Kivelson, D. G. Nocera, M. R. Norman, and T. Senthil, Quantum spin liquids. Science 367, eaay0668 (2020).
  * [5] P. W. Anderson, The resonating valence bond state in La2CuO4 and superconductivity. Science 235, 1196 (1987).
  * [6] P. A. Lee, N. Nagaosa, and X.-G. Wen, Doping a Mott insulator: Physics of high-temperature superconductivity. Rev. Mod. Phys. 78, 17 (2006).
  * [7] B. J. Powell and R. H. McKenzie, Quantum frustration in organic Mott insulators: from spin liquids to unconventional superconductors. Rep. Prog. Phys. 74, 056501 (2011).
  * [8] Y.-F. Jiang, and H.-C. Jiang, Topological Superconductivity in the Doped Chiral Spin Liquid on the Triangular Lattice. Phys. Rev. Lett. 125, 157002 (2020).
  * [9] H. C. Jiang, Superconductivity in the doped quantum spin liquid on the triangular lattice. npj Quantum Materials 6, 71 (2021).
  * [10] H. Oike, Y. Suzuki, H. Taniguchi, Y. Seki, K. Miyagawa, and K. Kanoda, Anomalous metallic behaviour in the doped spin liquid candidate $\kappa$-(ET)4Hg2.89Br8. Nat. Commun. 8, 756 (2017).
  * [11] Y. Shimizu, M. Maesato, and G. Saito, Uniaxial Strain Effects on Mott and Superconducting Transitions in $\kappa$-(ET)2Cu2(CN)3. J. Phys. Soc. Jpn. 80, 074702 (2011).
  * [12] R. Li, V. Petricek, G. Yang, P. Coppens, and M. Naughton, Room- and Low-Temperature Crystallographic Study of the Ambient Pressure Organic Superconductor (Bisethylene dithiotetrathiofulvalene)4Hg2.89Br8. Chem. Mater. 10, 1521 (1998).
  * [13] R. N. Lyubovskaya, E. I. Zhilyaeva, S. I. Pesotskii, R. B. Lyubovskii, L. O. Atovmyan, O. A. D${}^{{}^{\prime}}$yachenko, and T. G. Takhirov, Superconductivity of (ET)4Hg2.89Br8 at atmospheric pressure and $T_{c}=4.3$ K and the critical-field anisotropy. JETP Lett. 46, 188 (1987).
  * [14] T. Yamamoto, M. Uruichi, K. Yamamoto, K. Yakushi, A. Kawamoto, and H. Taniguchi, Examination of the Charge-Sensitive Vibrational Modes in Bis(ethylenedithio)tetrathiafulvalene. J. Phys. Chem. B 109, 15226 (2005).
  * [15] H. Oike, K. Miyagawa, H. Taniguchi, and K. Kanoda, Pressure-induced Mott transition in an organic superconductor with a finite doping level. Phys. Rev. Lett. 114, 067002 (2015).
  * [16] Y. Suzuki, K. Wakamatsu, J. Ibuka, H. Oike, T. Fujii, K. Miyagawa, H. Taniguchi, and K. Kanoda, Mott-Driven BEC-BCS Crossover in a Doped Spin Liquid Candidate $\kappa$-(ET)4Hg2.89Br8. Phys. Rev. X 12, 011016 (2022).
  * [17] S. Imajo, S. Sugiura, H. Akutsu, Y. Kohama, T. Isono, T. Terashima, K. Kindo, S. Uji, and Y. Nakazawa, Extraordinary $\pi$-electron superconductivity emerging from a quantum spin liquid. Phys. Rev. Research. 3, 033026 (2021).
  * [18] P. G. De Gennes, Superconductivity of Metals and Alloys (Benjamin, New York, 1966).
  * [19] Z. Hao, and J. R. Clem, Limitations of the London Model for the Reversible Magnetization of Type-II Superconductors. Phys. Rev. Lett. 67, 2371 (1991).
  * [20] K. Wakamatsu, K. Miyagawa, and K. Kanoda, Superfluid density versus transition temperature in a layered organic superconductor $\kappa$-(BEDT-TTF)2Cu[N(CN)2]Br under pressure. Phys. Rev. Research. 2, 043008 (2020).
  * [21] K. Adachi, and R. Ikeda, Stabilization of the vortex-liquid state by strong pairing interaction. Phys. Rev. B 99, 064508 (2019).
  * [22] V. G. Kogan, R. Prozorov, S. L. Bud’ko, P. C. Canfield, J. R. Thompson, J. Karpinski, N.D. Zhigadlo, and P. Miranovi$\acute{c}$, Effect of field-dependent core size on reversible magnetization of high-$\kappa$ superconductors. Phys. Rev. B 74, 184521 (2006).
  * [23] W. K. Kwok, U. Welp, K. D. Carlson, G. W. Crabtree, K. G. Vandervoort, H. H. Wang, A. M. Kini, J. M. Williams, D. L. Stupka, L. K. Montgomery, and J. E. Thompson, Unusual behavior in the upper critical magnetic fields of the ambient-pressure organic superconductor: $\kappa$-(BEDT-TTF)2Cu[N(CN)2]Br [where BEDT-TTF represents bis(ethylenedithio) tetrathiafulvalene]. Phys. Rev. B 42, 8686 (1990).
  * [24] M. Lang, N. Toyota, T. Sasaki, and H. Sato, Magnetic penetration depth of $\kappa$-(BEDT-TTF)2Cu[N(CN)2]Br, determined from the reversible magnetization. Phys. Rev. B 46, 5822 (1992).
  * [25] N. Yoneyama, A. Higashihara, T. Sasaki, T. Nojima, N. Kobayashi, Impurity Effect on the In-plane Penetration Depth of the Organic Superconductors $\kappa$-(BEDT-TTF)${}_{2}X$ ($X$ = Cu(NCS)2 and Cu[N(CN)2]Br). J. Phys. Soc. Jpn. 73, 1290 (2004).
  * [26] M. Lang, N. Toyota, T. Sasaki, and H. Sato, Magnetic Penetration Depth of $\kappa$-(BEDT-TTF)2Cu(NCS)2. Strong Evidence for Conventional Cooper Pairing. Phys. Rev. Lett. 69, 1443 (1992).
  * [27] A. Naito, Y. Nakazawa, K. Saito, H. Taniguchi, K. Kanoda, M. Sorai, Anomalous enhancement of electronic heat capacity in the organic conductors $\kappa$-(BEDT-TTF)4Hg3-δ$X_{8}$. $X=\textrm{Br, Cl}$. Phys. Rev. B 71, 054514 (2005).
  * [28] B. Andraka, C. S. Jee, J. S. Kim, G. R. Stewart, K. D. Carlson, H. H. Wang, A.V. S. Crouch, A. M. Kini, and J. M. Williams, Specific heat of the high T${}_{\textrm{c}}$ organic superconductor $\kappa$-(ET)2Cu[N(CN)2]Br. Solid State Communications. 79, 57 (1991).
  * [29] O. J. Taylor, A. Carrington, and J. A. Schlueter, Specific-Heat Measurements of the Gap Structure of the Organic Superconductors $\kappa$-(ET)2Cu[N(CN)2]Br and $\kappa$-(ET)2Cu(NCS)2. Phys. Rev. Lett. 99, 057001 (2007).
  * [30] B. Andraka, J. S. Kim, G. R. Stewart, K. D. Carlson, H. H. Wang, and J. M. Williams, Specific heat in high magnetic field of $\kappa$-di[bis(ethylenedithio)tetrathiafulvalene]-di(thiocyano)cuprate [$\kappa$-(ET)2Cu(NCS)2]: Evidence for strong-coupling superconductivity. Phys. Rev. B 40, 11345 (1989).
  * [31] K. Kanoda, Metal-Insulator Transition in $\kappa$-(ET)${}_{2}X$ and (DCNQI)${}_{2}M$: Two Contrasting Manifestation of Electron Correlation. J. Phys. Soc. Jpn. 75, 051007 (2006).
  * [32] Y. J. Uemura, G. M. Luke, B. J. Sternlieb, J. H. Brewer, J. F. Carolan, W. N. Hardy, R. Kadono, J. R. Kempton, R. F. Kiefl, S. R. Kreitzman, P. Mulhern, T. M. Riseman, D. L. Williams, B. X. Yang, S. Uchida, H. Takagi, J. Gopalakrishnan, A. W. Sleight, M. A. Subramanian, C. L. Chien, M. Z. Cieplak, G. Xiao, V. Y. Lee, B. W. Statt, C. E. Stronach, W. J. Kossler, and X. H. Yu, Universal Correlations between T${}_{\textrm{c}}$, and n${}_{\textrm{s}}/m^{\ast}$ (Carrier Density over Effective Mass) in High-T${}_{\textrm{c}}$ Cuprate Superconductors. Phys. Rev. Lett. 62, 2317 (1989).
  * [33] Y. J. Uemura, L. P. Le, G. M. Luke, B. J. Sternlieb, W. D. Wu, J. H. Brewer, T. M. Riseman, C. L. Seaman, M. B. Maple, M. Ishikawa, D. G. Hinks, J. D. Jorgensen, G. Saito, and H. Yamochi, Basic similarities among cuprate, bismuthate, organic, Chevrel-phase, and heavy-fermion superconductors shown by penetrationdepth measurements. Phys. Rev. Lett. 66, 2665 (1991).
  * [34] C. A. R. S$\acute{a}$ de Melo, M. Randeria, and J. R. Engelbrecht, Crossover from BCS to Bose superconductivity: Transition temperature and time-dependent Ginzburg-Landau theory.  Phys. Rev. Lett. 71, 3202 (1993).
  * [35] T. Hazra, N. Verma, and M. Randeria, Bounds on the superconducting transition temperature: applications to twisted bilayer graphene and cold atoms. Phys. Rev. X 9, 031049 (2019).
  * [36] Y. Ando, Y. Kurita, S. Komiya, S. Ono, and K. Segawa, Evolution of the Hall coefficient and the peculiar electronic structure of the cuprate superconductors. Phys. Rev. Lett. 92, 197001 (2004).
  * [37] D. N. Basov, and T. Timusk, Electrodynamics of high-$T_{\textrm{c}}$ superconductors. Rev. Mod. Phys. 77, 721 (2005).
  * [38] C. Panagopoulos, B. D. Rainford, J. R. Cooper, W. Lo, J. L. Tallon, J. W. Loram, J. Betouras, Y. S. Wang, and C. W. Chu, Effects of carrier concentration on the superfluid density of high-$T_{\textrm{c}}$ cuprates. Phys. Rev. B 60, 14617 (1999).
  * [39] W.-C. Lee, J. Sinova, A. A. Burkov, Y. Joglekar, and A. H. MacDonald, Theory of reduced superfluid density in underdoped cuprate superconductors. Phys. Rev. B 77, 214518 (2008).
  * [40] O. Simard, C.-D. H$\acute{e}$bert, A. Foley, D. S$\acute{e}$n$\acute{e}$chal, and Tremblay A.-M. S. , Superfluid stiffness in cuprates: Effect of Mott transition and phase competition. Phys. Rev. B 100, 094506 (2019).
  * [41] H. Taniguchi, T. Okuhata, T. Nagai, K. Satoh, N. Mori, Y. Shimizu, M. Hedo, and Y. Uwatoko, Anomalous pressure dependence of superconductivity in layered organic conductor, $\kappa$-(BEDT-TTF)4Hg2.89Br8. J. Phys. Soc. Jpn. 76, 113709 (2007).
  * [42] K. Wakamatsu, Y. Suzuki, T. Fujii, K. Miyagawa, H. Taniguchi, and K. Kanoda, Thermoelectric signature of quantum critical phase in a doped spin liquid candidate. arXiv:2201.10714
  * [43] S. Chakravarty, R. B. Laughlin, D. K. Morr, and C. Nayak, Hidden order in the cuprates. Phys. Rev. B 63, 094503 (2001).
  * [44] E. Fradkin, S. A. Kivelson, and J. M. Tranquada, Colloquium: Theory of intertwined orders in high temperature superconductors. Rev. Mod. Phys. 87, 457 (2015).
  * [45] B. Keimer, S. A. Kivelson, M. R. Norman, S. Uchida, and J. Zaanen, From quantum matter to high-temperature superconductivity in copper oxides. Nature 518, 179 (2015).
  * [46] Z. Zhu, D. N. Sheng, and A. Vishwanath, Doped Mott Insulators in the Triangular Lattice Hubbard Model. Phys. Rev. B 105, 205110 (2022).
  * [47] A. Wietek, R. Rossi, F. $\check{S}$imkovic, M. Klett, P. Hansmann, M. Ferrero, E. M. Stoudenmire, T. Sch$\ddot{a}$fer, and A. Georges, Mott Insulating States with Competing Orders in the Triangular Lattice Hubbard Model. Phys. Rev. X 11, 041013 (2021).

Figure 1:  (Color online) Crystal structure and superconducting properties of
$\kappa$-HgBr. (a) Crystal structure of $\kappa$-HgBr. BEDT-TTF molecules and
anions (Br and Hg) constitute conducting and insulating layers, respectively.
In the conducting plane, two BEDT-TTF molecules form a dimer, and the dimers
form a triangular lattice. In the case of $\kappa$-HgBr, band filling deviates
from half-filling, and 11% hole doping is realized. The blue arrows and red
spheres depict singly occupied holes with spins and vacancies (holons)
produced by the doped holes. (b) Pressure dependence of $T_{\textrm{c}}$ and
$k_{\textrm{F}}\xi_{\parallel}$. $k_{\textrm{F}}$ and $\xi_{\parallel}$
express the Fermi wavenumber and the in-plane superconducting coherence
length, respectively. The data under pressure are taken from Ref. [16], and
$T_{\textrm{c}}$ at ambient pressure is for the sample used in this study.
$T_{\textrm{c}}$ forms a dorm against pressure, and the value of
$k_{\textrm{F}}\xi_{\parallel}$ at low pressures is as low as $\sim$3, which
means bare overlapping of the Cooper pairs. (c) ac susceptibility of the
$\kappa$-HgBr crystal used in the present study. The ac fields with amplitudes
of 0.01 and 0.1 Oe and a frequency of 10 Hz were applied perpendicular to the
conducting layers. The inset shows the ac susceptibility corrected for the
demagnetization effect by approximating the crystal shape with a spheroid,
which yields the demagnetization coefficient, $N$$\sim$0.69. The magnitude of
the corrected ac susceptibility inevitably contains an ambiguity of 10-20%
considering the forcible approximation of the sample shape. Thus, low-
temperature saturation can be regarded to indicate complete diamagnetism. (d)
Temperature dependence of the spin susceptibility of $\kappa$-HgBr. A magnetic
field $H$ = 5 T was applied parallel and perpendicular to the conducting
layers. The core diamagnetism is corrected. This behavior reproduces the
results reported in Ref. [10].  Figure 2:  (Color online) Magnetization curves
and irreversibility fields of $\kappa$-HgBr and $\kappa$-Br. (a) Magnetization
curves of $\kappa$-HgBr and $\kappa$-Br at the same reduced temperature,
$T/T_{\textrm{c}}\sim$0.42. The vertical axis is normalized by the sample
volume. (b) Expanded panel of (a). (c) Irreversibility field versus
$T/T_{\textrm{c}}\sim$ for $\kappa$-HgBr and $\kappa$-Br.  Figure 3:  (Color
online) Magnetization and penetration depth of $\kappa$-HgBr. (a) Magnetic
field dependence of the magnetization in $\kappa$-HgBr in the reversible
region at several temperatures. The black lines are the fits of the formula
$-4\pi M=(\alpha\phi_{0}/8\pi\lambda_{\parallel}^{2})\ln(\beta
H_{\textrm{c2}\perp}/H)$ to the data. The broken curve shows the calculated
value of core diamagnetism. To avoid the contribution of the core diamagnetism
to the magnetization, we used the magnetization data (closed symbols) in the
field range where the core diamagnetism is negligible in the analysis. (c)
Temperature dependence of the 1/$\lambda_{\parallel}^{2}$ of $\kappa$-HgBr.
The line represents the fits of the form
$1/\lambda_{\parallel}(T)^{2}=1/\lambda_{\parallel}(0)^{2}\times[1-(T/T_{\textrm{c}})^{p}]$
with $p$ as a free parameter, which yields 2.4 and is fixed at 2.  Figure 4:
(Color online) Comparison of $n_{\textrm{s}}/m^{\ast}$ and $n_{\textrm{s}}$
between half-filled and hole-doped cases and Uemura plot in some strongly
correlated materials. (a) and (b), Superfluid weight $n_{\textrm{s}}/m^{\ast}$
and superfluid density $n_{\textrm{s}}$ of $\kappa$-Br [20, 24, 25, 28, 29],
$\kappa$-NCS [25, 26, 29, 30] and $\kappa$-HgBr. The values of electron
correlation $U/t$ refer to Ref. [11]. (c) Superconducting transition
temperature versus nominal Fermi temperature (so-called Uemura plot) for
several strongly correlated electron systems of organic, cuprate and heavy
electron materials. The symbols of the red star and gray squares for
$\kappa$-HgBr, $\kappa$-Br and $\kappa$-NCS are located using the present
values, whereas other symbols for the cuprates and heavy electron systems are
located using the information in Refs. [32, 33, 34, 35]. BSCCO, YBCO and LSCO
indicate the cuprates of
Bi${}_{\textrm{2-x}}$Pb${}_{\textrm{x}}$Sr${}_{\textrm{2}}$Ca${}_{\textrm{2}}$Cu${}_{\textrm{3}}$O${}_{\textrm{10}}$,
YBa${}_{\textrm{2}}$Cu${}_{\textrm{3}}$O${}_{\textrm{y}}$, and
La${}_{\textrm{2-x}}$Sr${}_{\textrm{x}}$CuO4, respectively. The line of
$T_{\textrm{c}}=T_{\textrm{F}}/8$ indicates the two-dimensional limit of the
BEC-like condensate.


# Euler dynamic H-trails in edge-colored graphs††thanks: This research was
supported by grants CONACYT FORDECYT-PRONACES/ 39570/2020 and UNAM DGAPA-
PAPIIT IN102320. The second author is a doctoral student from Posgrado en
Ciencias Matemáticas, Universidad Nacional Autónoma de México (UNAM) and
received a fellowship 782239 from CONACYT.

Galeana-Sánchez Hortensia  Instituto de Matemáticas, Universidad Nacional
Autónoma de México, Área de la investigación científica, Circuito Exterior,
Ciudad Universitaria, 04510 Coyoacán, CDMX, México  Vilchis-Alfaro Carlos
Corresponding author. Email<EMAIL_ADDRESS>Instituto de
Matemáticas, Universidad Nacional Autónoma de México, Área de la investigación
científica, Circuito Exterior, Ciudad Universitaria, 04510 Coyoacán, CDMX,
México

###### Abstract

Alternating Euler trails has been extensively studied for its diverse
practical and theorical applications. Let H be a graph possibly with loops and
G a graph without loops. In this paper we deal with any fixed coloration of
E(G) with V(H) (H-coloring of G). A sequence
$W=(v_{0},e_{0}^{1},\ldots,e_{0}^{k_{0}},v_{1},e_{1}^{1},\ldots,e_{n-1}^{k_{n-1}},v_{n})$
in $G$, where for each $i\in\\{0,\ldots,n-1\\}$, $k_{i}\geq 1$ and
$e_{i}^{j}=v_{i}v_{i+1}$ is an edge in $G$, for every
$j\in\\{1,\ldots,k_{i}\\}$, is a dynamic $H$-trail if $W$ does not repeat
edges and $c(e_{i}^{k_{i}})c(e_{i+1}^{1})$ is an edge in $H$, for each
$i\in\\{0,\ldots,n-2\\}$. In particular a dynamic $H$-trail is an alternating
Euler trail when $H$ is a complete graph without loops and $k_{i}=1$, for
every $i\in\\{1,\ldots,n-1\\}$.

In this paper, we introduce the concept of dynamic $H$-trail, which arises in
a natural way in the modeling of many practical problems, in particular, in
theoretical computer science.

We provide necessary and sufficient conditions for the existence of closed
Euler dynamic $H$-trail in $H$-colored multigraphs. Also we provide polynomial
time algorithms that allows us to convert a cycle in an auxiliary graph,
$L_{2}^{H}(G)$, in a closed dynamic H-trail in $G$, and vice versa, where
$L_{2}^{H}(G)$ is a non-colored simple graph obtained from $G$ in a polynomial
time.

Keywords: Edge colored graph, Dynamic H-trail, Euler dynamic H-trails,
Hamiltonian cycles

##  1 Introduction

For basic concepts, terminology and notation not defined here, we refer the
reader to [3] and [5]. Throughout this work, we will consider graphs,
multigraphs (graphs allowing parallel edges) and simple graphs (graphs with no
parallel edges nor loops). Let $G$ be a multigraph, $V(G)$ and $E(G)$ will
denoted the sets of vertices and edges of $G$, respectively.

A spanning circuit in a graph $G$ is defined as a closed trail that contains
each vertex of $G$. We will say that a graph is supereulerian if it contains a
spanning circuit. Let $T$ be a spanning circuit in $G$: if $T$ visits each
vertex of $G$ exactly once, then $T$ will be called Hamilton cycle; and if $T$
visits each edge of $G$, then $T$ will be called Euler trail. We will say that
a graph is hamiltonian if it has a Hamilton cycle and eulerian if it contains
an Euler trail.

In [15], Harary and Nash-Williams introduced the following graphs. Let $G$ be
a graph with $p$ vertices and $q$ edges, for $n\geq 2$, $L_{n}(G)$ will denote
the graph with $nq$ vertices that are obtained as follows: for each edge
$e=uv$ of $G$, we take two vertices $f(u,e)$ and $f(v,e)$ in $L_{n}(G)$ and
adding a path with $n-2$ new intermediate vertices connecting $f(u,e)$ and
$f(v,e)$; finally, for each vertex $u$ of $G$, we add an edge joining $f(u,e)$
and $f(u,g)$, whenever $e$ and $g$ are distinct edges with end point $u$. They
also proved the followings relationships between eulerian graphs and
hamiltonian cycles of $L_{n}(G)$.

######  Theorem 1 ([15]).

Let $G$ be a graph. The following assertions holds:

  1. 1.

If $G$ is eulerian, then $L_{n}(G)$ is hamiltonian, for every $n\geq 2$.

  2. 2.

If $L_{n}(G)$ is hamiltonian, for some $n\geq 3$, then $G$ is eulerian.

  3. 3.

$G$ is superulerian if and only if $L_{2}(G)$ is hamiltonian.

An edge-coloring of a graph $G$ is defined as a mapping
$c:E(G)\rightarrow\mathbb{N}$, where $\mathbb{N}$ is the set of natural
numbers. We will say that $G$ is an edge-colored graph whenever we are taking
a fixed edge-coloring of $G$. A properly colored spanning circuit is a
spanning circuit with no consecutive edges having the same color, including
the first and the last in a closed spanning circuit. An edge-colored graph is
supereulerian, if $G$ contains a properly colored spanning circuit. Several
authors have worked with this concept, for example, Bang-Jensen, Bellitto and
Yeo [2]; Guo, Li, Li and Zhang [14]; Guo, Broersma, Li and Zhang [13].
Properly colored walks are of interest as a generalization of walk in
undirected and directed graphs, see [3], as well as, in graph theory
application, for example, in genetic and molecular biology [9, 10, 20], social
science [6], channel assignment is wireless networks [1, 18]. For more details
on properly colored walks, we refer the reader to Chapter 16 of [3].

Kotzig [16] gave the following characterization of edge-colored multigraphs
containing properly colored closed Euler trail.

######  Theorem 2 (Kotzig [16]).

Let $G$ be an edge-colored eulerian multigraph. Then $G$ has a properly
colored closed Euler trail if and only if $\delta_{i}(x)\leq\sum_{j\neq
i}\delta_{j}(x)$, where $\delta_{i}(x)$ is the number of edges with color $i$
incident with $x$, for each vertex $x$ of $G$.

Different kinds of edge-coloring in undirected and directed graphs have been
studied, for example, in [17] the arcs of a tournament were colored with the
vertices of a poset. In this paper we will consider the following edge-
coloring. Let $H$ be a graph possibly with loops and $G$ be a graph without
loops. An $H$-coloring of $G$ is a function $c:E(G)\rightarrow V(H)$. We will
say that $G$ is an $H$-colored graph, whenever we are taking a fixed
$H$-coloring of $G$. A walk $W=(v_{0},e_{0},v_{1},e_{1},\ldots,e_{k-1},v_{k})$
in $G$, where $e_{i}=v_{i}v_{i+1}$ for every $i$ in $\\{0,\ldots,k-1\\}$, is
an $H$-walk if
$(c(e_{0}),a_{0},c(e_{1}),\ldots,c(e_{k-2}),a_{k-2},c(e_{k-1}))$ is a walk in
$H$, with $a_{i}=c(e_{i})c(e_{i+1})$ for every $i\in\\{0,\dots,k-2\\}$. We
will say that $W$ is closed if $v_{0}=v_{k}$ and $c(e_{k-2})c(e_{0})\in E(H)$.
Let $W$ be an $H$-walk, if $W$ is a trail then $W$ will be called $H$-trail.
Notice that if $H$ is a complete graph without loops, then an $H$-walk is a
properly colored walk.

Since, properly colored walks have been very useful for modeling and solving
different problems, as we mentioned above, $H$-colored graphs and $H$-walks
can also model interesting problems, for example, routing problems or in
communications networks were some transitions are restricted because of
natural phenomenon, external attack or failure. More applications of colored
walks with restrictions in color’s succession can be found in [19].

The concepts of $H$-coloring and $H$-walks were introduced, for the first time
by Linek and Sands in [17], and have been worked mainly in the context of
kernel theory and related topics, see [7, 8, 12].

In [11], Galeana-Sánchez, Rojas-Monroy, Sánchez-López and Villarreal-Valdés
defined the graph $G_{u}$ as follows: Let $u$ be a vertex of $G$; $G_{u}$ is
the graph such that $V(G_{u})=\\{e\in E(G):e\textrm{ is incident}$
$\textrm{with }u\\}$, and two different vertices $a$ and $b$ are joining by
only one edge in $G_{u}$ if and only if $c(a)$ and $c(b)$ are adjacent in $H$.

They also showed necessary and sufficient conditions for the existence of
closed Euler $H$-trails, as follows.

######  Theorem 3 ([11]).

Let $H$ be a graph possibly with loops and $G$ be an $H$-colored multigraph
without loops. Suppose that $G$ is Eulerian and $G_{u}$ is a complete
$k_{u}$-partite graph, for every $u$ in $V(G)$ and for some $k_{u}$ in
$\mathbb{N}$. Then $G$ has a closed Euler $H$-trail if and only if
$|C_{i}^{u}|\leq\sum_{j\neq i}|C_{j}^{u}|$ for every $u$ in $V(G)$, where
$\\{C_{1}^{u},...,C_{k_{u}}^{u}\\}$ is the partition of $V(G_{u})$ into
independent sets.

In [4], Benítez-Bobadilla, Galeana-Sánchez and Hernández-Cruz introduced a
generalization of $H$-walk as follows. They allowed “lane changes”, i.e., they
allowed concatenation of two $H$-walks as long as, the last edge of the first
one and the first edge of the second one satisfy that $x_{k-1}=y_{0}$ and
$x_{k}=y_{1}$. As a result, they defined the following new concept: Let $G$ be
an $H$-colored multigraph, a dynamic $H$-walk in $G$ is a sequence of vertices
$W=(x_{0},x_{1},\ldots,x_{k})$ in $G$ such that for each
$i\in\\{0,\ldots,k-2\\}$ there exists an edge $f_{i}=x_{i}x_{i+1}$ and there
exists an edge $f_{i+1}=x_{i+1}x_{i+2}$ such that $c(f_{i})c(f_{i+1})$ is an
edge in $H$.

For the purpose of this paper, we need a definition and notation that will
allows us to know the edges that belong to a dynamic $H$-walk. So, we will say
that $W=(v_{0},e_{0}^{1},\ldots,e_{0}^{k_{0}},v_{1},e_{1}^{1},\ldots,$
$e_{1}^{k_{1}},v_{2},\ldots,v_{n-1},e_{n-1}^{k_{n-1}},\ldots,$
$e_{n-1}^{k_{n-1}},v_{n})$, where for each $i\in\\{0,\ldots,n-1\\}$,
$k_{i}\geq 1$ and $e_{i}^{j}=v_{i}v_{i+1}$ for every
$j\in\\{1,\ldots,k_{i}\\}$, is a dynamic $H$-walk if
$c(e_{i}^{k_{i}})c(e_{i+1}^{1})$ is an edge in $H$, for each
$i\in\\{0,\ldots,n-2\\}$. If $W$ is a dynamic $H$-walk that does not repeat
edges, then $W$ will be called dynamic $H$-trail. We will say that a dynamic
$H$-trail, $W$, is an Euler dynamic $H$-trail if $E(G)=E(W)$. We will say that
a dynamic $H$-trail is a closed dynamic $H$-trail whenever a) $v_{0}=v_{n}$
and $c(e_{n-1}^{k_{n-1}})c(e_{0}^{1})$ is an edge in $H$; or b) $v_{1}=v_{n}$
and $e_{n-1}^{k_{n-1}}$ and $e_{0}^{1}$ are parallel in $G$. Notice that if
$W$ is a closed dynamic $H$-walk that satisfies condition b, then $W$ can be
rewrite as
$W=(v_{1},e_{1}^{1},...,v_{n-1}=v_{0},e_{n-1}^{1},\ldots,e_{n-1}^{k_{n-1}},e_{0}^{1},\ldots,e_{0}^{k_{0}},v_{n}=v_{1})$,
and $W$ satisfies condition (a) (unless $n=1$, i.e., $W$ is of the form
$(x,e_{0},\ldots,e_{k},y)$, where $k\geq 1$).

It follows from the definition of dynamic $H$-trail that every $H$-trail in
$G$ is a dynamic $H$-trail in $G$. Moreover, if $G$ has no parallel edges,
then every dynamic $H$-trail is an $H$-trail.

A motivation for the study of dynamic $H$-walks are their possibles
applications. For example, suppose that it is require to send a message from
point $A$ to point $B$ through communication network which can have faults in
its links (such as damage, attack, virus or blockage), where each one of its
edge has an assigned color depending on the probability that the message is
delivered correctly (in time, complete, unchanged or virus-free). In this
case, the vertices of $H$ are the colors assigned to the edges of the network
and the set of edges of $H$ will depend on the transitions that are convenient
(for example, if transition with the same probability of failure are
forbidden, then $H$ will have no loops). In practice, it is possible to send
messages simultaneously over two or more connections. In these cases, the use
of dynamic H-walks can improve message delivery.

Motivated by the Theorem 3 and its proof, we think that it is possible to give
conditions, similar to those of Theorem 3, on an $H$-colored multigraph that
guarantee the existence of closed Euler dynamic $H$-trail. In the process, we
find an auxiliary graph, we call it $L_{3}^{H}(G)$, that allows us to link the
closed dynamic $H$-trails with hamiltonian graphs.

The rest of the paper is organized as follows. Section 2 is devoted to give
some notation and terminology, which will be used throughout the paper. In
Section 3, we will define the graph $L_{n}^{H}(G)$. Then we will prove that
$G$ contains a closed Euler dynamic $H$-trails if and only if $L_{n}^{H}(G)$
is hamiltonian, for every $n\geq 3$.

##  2 Notation and Terminology

Let $G$ be a multigraph. If $e$ is an edge and $u$ and $v$ are the vertices
such that $e=uv$, then $e$ is said to join $u$ and $v$, we will say that $u$
and $v$ are the ends of $e$, we will say that the edge $e$ is incident with
$u$ (respectively $v$) and also we will say that $u$ and $v$ are adjacent. If
$u=v$, then the edge $e$ is a loop. Let $e$ and $f$ be two edges with the same
end vertices, we will say $e$ and $f$ are parallel. Its said that $G$ is a
looped graph whenever for every vertex $v$ in $G$, there exists a loop $e$
incident with $v$. A graph $G^{\prime}$ (multigraph or simple graph) is a
subgraph (submultigraph or simple subgraph, respectively) of $G$ if
$V(G^{\prime})\subseteq V(G)$ and $E(G^{\prime})\subseteq E(G)$. Let $S$ be a
nonempty subset of $V(G)$; the subgraph (submultigraph or simple subgraph) of
$G$ whose vertex set is $S$, and whose edge set is the set of those edges of G
that have both ends in $S$, is called the subgraph (submultigraph or simple
subgraph) of $G$ induced by $S$, and is denoted by $G[S]$.

A walk in a multigraph $G$ is a sequence
$(v_{0},e_{0},v_{1},e_{1},\ldots,e_{k-1},v_{k})$, where $e_{i}=v_{i}v_{i+1}$
for every $i$ in $\\{0,\ldots,k-1\\}$. We will say that a walk is closed if
$v_{0}=v_{k}$. If $v_{i}\neq v_{j}$ for all $i$ and $j$ with $i\neq j$, it is
called a path. A cycle is a closed walk
$(v_{0},e_{0},v_{1},e_{1},\ldots,e_{k-1},v_{k},e_{k},v_{0})$, with $k\geq 3$,
such that $v_{i}\neq v_{j}$ for all $i$ and $j$ with $i\neq j$. In a
multigraph $G$ a walk in which no edge is repeated is a trail. A closed Euler
trail in a multigraph $G$, is a closed walk which traverses each edge of $G$
exactly once. If $W=(v_{0},e_{0},v_{1},e_{1},\ldots,e_{k-1},v_{k})$ and
$W^{\prime}=(v_{k},e_{k},v_{k+1},e_{k+1},\ldots,e_{t-1},v_{t})$ are two walks,
the walk $(v_{k},e_{k-1},\ldots,e_{1},v_{1},e_{0},v_{0})$, obtained by
reversing $W$, is denoted by $W^{-1}$ and the walk
$(v_{0},e_{0},v_{1},\ldots,e_{k-1},v_{k},$
$e_{k},v_{k+1},e_{k+1},\ldots,e_{t-1},v_{t})$, obtaining by concatenating $W$
and $W^{\prime}$ at $v_{k}$, is denoted by $W\cup W^{\prime}$.

A simple graph $G$ is said to be multipartite, if for some positive integer
$k$, there exists a partition ${X_{1},\ldots,X_{k}}$ of $V(G)$, such that
$X_{i}$ is an independent set in $G$ (that is no two vertices of $X_{i}$ are
adjacent) for every $i$ in $\\{1,\ldots,k\\}$, in this case, also $G$ is
called $k$-partite. It said that $G$ is a complete $k$-partite graph whenever
$G$ is $k$-partite and for every $u$ in $X_{i}$ and for every $v$ in $X_{j}$ ,
with $i\neq j$ , we have that $u$ and $v$ are adjacent, denoted by
$K_{n_{1},\ldots,n_{k}}$ where $|X_{i}|=n_{i}$ for every $i$ in
$\\{1,\ldots,k\\}$. In the particular case when $k=2$, the graph $G$ is said
to be bipartite graph. A matching in a graph $G$ is a subset $M$ of $E(G)$,
such that no two elements of $M$ are incident with the same vertex in $G$. A
matching $M$ saturates a vertex $v$ if some edge of $M$ is incident with $v$.
If every vertex of $G$ is saturated, the matching $M$ is said to be perfect.
We will need the following results.

######  Theorem 4 (Tutte [21]).

$G$ has a perfect matching if and only if $o(G\setminus S)\leq|S|$ for all
proper subset $S$ of $V(G)$.

######  Lemma 5.

Let $M$ and $M^{\prime}$ be two perfect matching of a graph $G$. If $M\cap
M^{\prime}=\emptyset$, then there exists a partition of the vertices of $G$
into even cycles. Moreover, every cycle alternate edges between $M$ and
$M^{\prime}$.

$G$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$e_{1}$ $e_{3}$ $e_{2}$ $e_{6}$ $e_{5}$ $e_{4}$
$H$$G$$R$

(a) $G$ is an $H$-colored multigraph

$f(v_{1},e_{1})$$f(v_{1},e_{2})$$f(v_{1},e_{3})$$G_{v_{1}}$$f(v_{2},e_{1})$$G_{v_{2}}$$f(v_{3},e_{3})$$f(v_{3},e_{2})$$G_{v_{3}}$$G_{v_{4}}$$m(e_{1})$$m(e_{2})$$m(e_{3})$

(b) $L_{3}^{H}(G)$

Figure 1: The sequence
$P=(v_{1},e_{1},v_{2},e_{6},e_{5},v_{4},e_{4},v_{3},e_{3},e_{2},v_{1})$ is a
closed Euler dynamic $H$-trail in $G$ but there is no closed Euler $H$-trail
in $G$

##  3 Main results

In what follows, $H$ will be a graph possibly with loops, and $G$ will be a
multigraph without loops.

First of all, we will introduce an auxiliary graph, denoted by $L_{n}^{H}(G)$,
which is defined as follows.

######  Definition 1.

Let $G$ be an $H$-colored multigraph with $|E(G)|=q$. For $n\geq 2$,
$L_{n}^{H}(G)$ is the graph with $nq$ vertices, obtained as follows: for each
edge $e=uv$ of $G$, we take two vertices $f(u,e)$ and $f(v,e)$ in
$L_{n}^{H}(G)$, and adding a path with $n-2$ new intermediate vertices
connecting $f(u,e)$ and $f(v,e)$. And the rest of the edges of $L_{n}^{H}(G)$
are defined as follows: a) $f(u,e)$ and $f(u,g)$ are adjacent iff $e\neq g$
and $c(e)c(g)\in E(H)$; b) $f(u,e)$ and $f(v,g)$ are adjacent iff $u\neq v$
and $e$ and $g$ are parallel in $G$.

Notice that $L_{n}^{H}(G)$ is a simple graph.

Before giving a new way to construct the graph $L_{n}^{H}(G)$, we first
introduce some additional notation.

Recall that $G_{u}$ is the graph such that $V(G_{u})=\\{e\in E(G):e\textrm{ is
incident}$ $\textrm{with }u\\}$, and two different vertices $a$ and $b$ are
joining by only one edge in $G_{u}$ if and only if $c(a)$ and $c(b)$ are
adjacent in $H$.

For each $e=xy$ in $E(G)$, by the definition of $G_{x}$ and $G_{y}$, we have
that $e\in V(G_{x})$ and $e\in V(G_{y})$. So, we will say that $f(x,e)$ and
$f(y,e)$ are the copies of $e$ seen as a vertex in $G_{x}$ and $G_{y}$,
respectively; and if $E_{xy}$ is the set of all the edges with end vertices
$x$ and $y$, then we will say that $E_{xy}^{x}=\\{f(x,e):e\in E_{xy}\\}$.

Notice that $L_{n}^{H}(G)$ can be constructed as follows. First take the
disjoint union of $G_{x}$, for every $x$ in $V(G)$. Then, for every pair of
distinct vertices, $x$ and $y$ in $V(G)$, such that $|E_{xy}|=m\geq 1$, we
will have a complete bipartite graph $K_{m,m}$ between $E_{xy}^{x}$ and
$E_{xy}^{y}$. Finally, for every $e=xy\in E(G)$, we change the edge joining
$f(x,e)$ and $f(y,e)$ by the path with $n-2$ new intermediate vertices. The
construction of $L_{3}^{H}(G)$ is illustrated in Figure 1.

It follows from the definition of $L_{2}^{H}(G)$ that
$M_{J}=\\{f(x,e)f(y,e)\in E(L_{2}^{H}(G)):e=xy\in E(G)\\}$ is a perfect
matching, that we will called it joint matching of $L_{2}^{H}(G)$.

The following two lemmas show how to construct a cycle in $L_{2}^{H}(G)$,
based on the order of the edges in a closed dynamic H-trail in $G$, and vice
versa.

######  Lemma 6.

Let $G$ be an $H$-colored multigraph. If
$P=(x_{0},e_{1},\ldots,e_{p_{0}},x_{1},e_{p_{0}+1},$
$\ldots,e_{p_{0}+\ldots+p_{1}},x_{2},$ $\ldots,x_{n-1},$
$e_{p_{0}+\ldots+p_{n-2}+1},\ldots,$ $e_{p_{0}+\ldots+p_{n-1}},x_{n})$ is a
closed dynamic $H$-trail in $G$, then $C=(f(x_{0},e_{1}),$
$f(x_{1},e_{1}),\ldots,$
$f(x_{0},e_{p_{0}}),f(x_{1},e_{p_{0}}),f(x_{1},e_{p_{0}+1}),f(x_{2},e_{p_{0}+1})\ldots,f(x_{n},e_{p_{0}+\ldots+p_{n-1}}),f(x_{0},e_{1}))$
is a
cycle in $L_{2}^{H}(G)$.

###### Proof.

It follows from the definition of $L_{2}^{H}(G)$ that $f(e,x_{i})f(e,x_{i+1})$
is an edge of $L_{2}^{H}(G)$, for every $e=x_{i}x_{i+1}\in E(P)$.

Let $e_{i}$ and $e_{i+1}$ be consecutive edges in $P$ (if
$i=p_{0}+\ldots+p_{n-1}$, then $e_{i+1}=e_{1}$). If $e_{i}$ and $e_{i+1}$ are
parallel, such that $x_{j}$ and $x_{j+1}$ are the ends of both edges, then
$f(x_{j+1},e_{i})$ and $f(x_{j},e_{i+1})$ are adjacent in $L_{2}^{H}(G)$, by
the definition of $L_{2}^{H}(G)$. Otherwise, $e_{i}$ and $e_{i+1}$ are
incident with $x_{j}$, for some $x_{j}$ in $V(P)$. Since $P$ is a closed
dynamic $H$-trail, then $c(e_{i})c(e_{i+1})$ is an edge in $H$ and
$f(x_{j},e_{i})f(x_{j},e_{i+1})\in E(L_{2}^{H}(G))$. Hence, $C$ is a walk in
$L_{2}^{H}(G)$. Since, $P$ is a closed dynamic $H$-trail, then $C$ does not
repeat vertices and, so $C$ is a cycle. Moreover, $C$ alternate edges between
$E(L_{2}^{H}(G))\setminus M_{J}$ and $M_{J}$. ∎

######  Lemma 7.

Let $G$ be an $H$-colored multigraph and $M_{J}$ be the joint matching of
$L_{2}^{H}(G)$. If $C=(f(x_{1},e_{1}),$
$f(y_{1},e_{1}),f(x_{2},e_{2}),f(y_{2},e_{2})\ldots,f(y_{q},e_{q}),f(x_{1},e_{1}))$,
where $e_{i}=x_{i}y_{i}\in E(G)$, be a cycle in $L_{2}^{H}(G)$ that alternate
edges between $E(L_{2}^{H}(G))\setminus M_{J}$ and $M_{J}$, then the following
steps produces a closed dynamic $H$-trail in $G$.

  1. 1.

Star with $P=(x_{1},e_{1},y_{1})$ and $k=2$.

  2. 2.

Let $e_{k}$, with end vertices $x_{k}$ and $y_{k}$. If $e_{k-1}$ and $e_{k}$
are parallel, $x_{k}=x_{k-1}$ and $y_{k}=y_{k-1}$, then we change lanes from
the edge $e_{k-1}$ to $e_{k}$ in $P$. Otherwise, continue $P$ by the edge
$e_{k}$.

  3. 3.

$k=k+1$.

  4. 4.

If $k=q+1$, finish. Otherwise, go to step 2.

###### Proof.

First, we will prove that $P$ is a dynamic $H$-trail in $G$.

Let $e_{k-1}$ and $e_{k}$, with $2\leq k\leq q$.

Since $f(y_{k-1},e_{k-1})f(x_{k},e_{k})\in E(C)$, we have that
$f(y_{k-1},e_{k-1})f(x_{k},e_{k})$ is in $E(L_{2}^{H}(G))$. Hence,
$y_{k-1}=x_{k}$ and $c(e_{k-1})c(e_{k})\in E(H)$ or $y_{k-1}\neq x_{k}$ and
$e_{k-1}$ and $e_{k}$ are parallel in $G$.

If $y_{k-1}=x_{k}$ and $c(e_{k-1})c(e_{k})\in E(H)$, then $e_{k-1}$ and
$e_{k}$ are incident in $y_{k-1}=x_{k}$ and $(x_{1},e_{1},P,x_{k-1},$
$e_{k-1},y_{k-1}=x_{k},e_{k},y_{k})$ is a dynamic $H$-walk in $G$.

Otherwise, $y_{k-1}\neq x_{k}$ and $e_{k-1}$ and $e_{k}$ are parallel edges in
$G$, and $(x_{1},e_{1},P,$ $x_{k-1}=x_{k},e_{k-1},e_{k},$ $y_{k-1}=y_{k})$ is
a dynamic $H$-walk in $G$.

Hence, $P$ is a dynamic $H$-walk in $G$.

On the other hand, since $C$ is a cycle, then $e_{i}$ appears exactly once in
$P$, for every $i\in\\{1,\ldots,q\\}$, and so $P$ is a dynamic $H$-trail.

Now, we prove that $P$ is closed.

Recall that $e_{i}=x_{i}y_{i}$, for every $i\in\\{1,\ldots,q\\}$, and
$y_{i}=x_{i+1}$ or $x_{i}=x_{i+1}$ and $y_{i}=y_{i+1}$ (if $i=q+1$, then
$x_{i+1}=x_{1}$ and $y_{i+1}=y_{1}$). We will consider two cases.

Case 1. $x_{i}=x_{j}$ and $y_{i}=y_{j}$, for every pair of distinct elements,
$i$ and $j$, in $\\{1,\ldots,q\\}$.

It follows from the construction of $P$ that
$P=(x_{1},e_{1},\ldots,e_{q},y_{1})$. Since $C$ is a cycle in $L_{2}^{H}(G)$,
then $q\geq 2$ and, so $P$ is closed.

Case 2. There exists $i$ in $\\{1,\ldots,q\\}$ such that $y_{i}=x_{i+1}$.

If $y_{q}=x_{1}$, then $c(e_{q})c(e_{1})\in E(H)$. Therefore, $P$ is closed.

Otherwise, $e_{q}$ and $e_{1}$ are parallel and, so $P$ is closed.

Therefore, $P$ is a closed dynamic $H$-trail in $G$. ∎

It follows from Lemmas 6 and 7 the following result.

######  Theorem 8.

Let $G$ be an $H$-colored multigraph and $M_{J}$ be the joint matching. Then,
there is a bijection bewteen the set of closed dynamic $H$-trails in $G$ and
the set of cycles in $L_{2}^{H}(G)$ that alternate edges between
$E(L_{2}^{H}(G))\setminus M_{J}$ and $M_{J}$.

###### Proof.

Let $G$ be an $H$-colored multigraph and $M_{J}$ the joint matching of
$L_{2}^{H}(G)$. We will denote by $\mathcal{P}$ the set of closed dynamic
$H$-trails in $G$ and by $\mathcal{C}$ the set of cycles in $L_{2}^{H}(G)$
that alternate edges between $E(L_{2}^{H}(G))\setminus M_{J}$ and $M_{J}$.

Let $T:\mathcal{P}\rightarrow\mathcal{C}$ defined by $T(P)=C$, where
$P=(x_{0},e_{1},\ldots,e_{p_{0}},x_{1},e_{p_{0}+1},\ldots,e_{p_{1}},x_{2},e_{p_{1}+1},\ldots,x_{n-1},$
$e_{p_{0}+\ldots+p_{n-2}+1},\ldots,$ $e_{p_{0}+\ldots+p_{n-1}},x_{n})$, and
$C=(f(x_{0},e_{1}),f(x_{1},e_{1}),\ldots,f(x_{0},e_{p_{0}}),f(x_{1},e_{p_{0}}),f(x_{1},e_{p_{0}+1}),\ldots,$
$f(x_{n},e_{p_{0}+\ldots+p_{n-1}}),f(x_{0},e_{1}))$.

Claim 1. $T$ is well-defined.

It follows from Lemma 6 that $T(P)\in\mathcal{C}$.

Let
$P_{1}=(x_{0},e_{0},\ldots,e_{p_{0}},x_{1},e_{p_{0}+1},\ldots,e_{p_{0}+p_{1}},x_{2},\ldots,x_{n-1},e_{p_{0}+\ldots+p_{n-2}+1},\ldots,e_{p_{0}+\ldots+p_{n-1}},x_{n})$
and
$P_{2}=(y_{0},f_{0},\ldots,f_{q_{0}},y_{1},f_{q_{0}+1},\ldots,f_{q_{0}+q_{1}},y_{2},\ldots,y_{n-1},f_{q_{0}+\ldots+q_{n-2}+1},\ldots,f_{q_{0}+\ldots+q_{n-1}},y_{n})$
in $\mathcal{P}$ such that $P_{1}=P_{2}$.

Since $P_{1}=P_{2}$, then $E(P_{1})=E(P_{2})$ and there exists
$k\in\mathbb{N}$ such that $e_{i}=f_{i+k(mod\,p_{0}+\ldots+p_{n-1})}$ (since
the edges are traversed in the same order but the first edge is not the same).
It follows from the definition of $T$ that $V(T(P_{1}))=V(T(P_{2}))$ and the
order of the vertices are the same. Then, we have that $T(P_{1})=T(P_{2})$.
Therefore, $T$ is well-defined.

Claim 2. $T$ is injective.

Let $P_{1}$ and $P_{2}$ in $\mathcal{P}$ such that $P_{1}\neq P_{2}$.

If $E(P_{1})\neq E(P_{2})$, then $V(T(P_{1}))\neq V(T(P_{2}))$ and, so
$T(P_{1})\neq T(P_{2})$. Otherwise, since $P_{1}\neq P_{2}$, then there exists
$\\{e_{i},e_{i+1}\\}\subseteq E(P_{1})=E(P_{2})$ such that $e_{i}$ is the edge
preceding $e_{i+1}$ in $P_{1}$ and $e_{i}$ is not the edge preceding $e_{i+1}$
in $P_{2}$. Therefore, $T(P_{1})\neq T(P_{2})$ and $T$ is injective.

Claim 3. $T$ is surjective.

Let $C$ be a cycle in $\mathcal{C}$. Since $C$ alternate edges between
$E(L_{2}^{H}(G))\setminus M_{J}$ and $M_{J}$, $C$ must be of the form
$C=(f(x_{1},e_{1}),f(y_{1},e_{1}),\ldots,f(x_{q},e_{q}),$
$f(y_{q},e_{q}),f(x_{1},e_{1}))$, where $e_{i}=x_{i}y_{i}\in E(G)$.

It follows from the definition of $T$ that $T(P)=C$, where $P$ be the closed
dynamic $H$-trail obtained by applying the Lemma 7 to the cycle $C$. Hence,
$T$ is surjective.

Therefore, $T$ is a bijection. ∎

######  Theorem 9.

Let $G$ be an $H$-colored multigraph and $M_{J}$ be the joint matching of
$L_{2}^{H}(G)$. There exists a perfect matching $M$ in $L_{2}^{H}(G)\setminus
M_{J}$ if and only if there exists a partition of the edges of $G$ into closed
dynamic $H$-trails. (Notice that some of the closed dynamic $H$-trails can be
of the form $(x,e_{0},\ldots,e_{k},y)$, where $k\geq 1$).

###### Proof.

Let $G$ be an $H$-colored multigraph and $M_{J}$ be the joint matching of
$L_{2}^{H}(G)$.

Suppose that there exists a perfect matching $M$ in $L_{2}^{H}(G)\setminus
M_{J}$.

It follows by Lemma 5, that there exists a partition of the vertices of
$L_{2}^{H}(G)$ into vertex-disjoint cycles, say
$\mathfrak{C}=\\{C_{1},\ldots,C_{n}\\}$. Moreover, each cycle in
$\mathfrak{C}$ alternate edges between $M_{J}$ and $M$.

Let $\mathfrak{P}=\\{P_{1},\ldots,P_{n}\\}$ be the set of closed dynamic
$H$-trails in $G$ such that $T(P_{i})=C_{i}$, for every
$i\in\\{1,\ldots,n\\}$.

Claim 1 $E(P_{i})\cap E(P_{j})=\emptyset$, for every
$\\{i,j\\}\subseteq\\{1,\ldots,n\\}$.

Proceeding by contradiction, suppose that there exists a pair of distinct
elements, $i$ and $j$ in $\\{1,\ldots,n\\}$, such that $E(P_{i})\cap
E(P_{j})\neq\emptyset$.

Let $e=xy\in E(P_{i})\cap E(P_{j})$, it follows from the definition of $T$
that $f(x,e)$ and $f(y,e)$ are vertices in $V(C_{i})\cap V(C_{j})$, a
contradiction.

Claim 2 $\bigcup_{i=1}^{n}E(P_{i})=E(G)$.

By the definition of $T$, we have that $\bigcup_{i=1}^{n}\;E(P_{i})\subseteq
E(G)$.

On the other hand, let $e\in E(G)$ join $x$ and $y$. Since, $\mathfrak{C}$ is
a partition of the vertices of $L_{2}^{H}(G)$, then there exists a cycle in
$\mathfrak{C}$, say $C_{j}$, such that $f(x,e)f(y,e)\in E(C_{j})$. It follows
from the construction of $P_{j}$ that $e\in E(P_{j})$. Therefore,
$e\in\bigcup_{i=1}^{n}E(P_{i})$ and $E(G)\subseteq\bigcup_{i=1}^{n}E(P_{i})$.

Therefore, $\mathfrak{P}=\\{P_{1},\ldots,P_{n}\\}$ is a partition of the edges
of $G$ into closed dynamic $H$-trails.

Conversely, suppose that there exists a partition of the edges of $G$ into
closed dynamic $H$-trails, say $\mathfrak{P}=\\{P_{1},\ldots,P_{k}\\}$.

Let $\mathfrak{C}=\\{C_{1},\ldots,C_{k}\\}$ a set of cycles in $L_{2}^{H}(G)$
such that $T(P_{i})=C_{i}$, for every $i\in\\{1,\ldots,k\\}$.

Claim 3 If $i\neq j$, then $V(C_{i})\cap V(C_{j})=\emptyset$.

Suppose, to the contrary, that there exists $i$ and $j$ in $\\{1,\ldots,k\\}$,
such that $V(C_{i})\cap V(C_{j})\neq\emptyset$. Let $f(x,e)\in V(C_{i})\cap
V(C_{j})$, for some $e\in E(G)$ and $x\in V(G)$, such that $e$ is incident
with $x$.

It follows from the construction of $C_{i}$ and $C_{j}$ that $e\in E(P_{i})$
and $e\in E(P_{j})$, a contradiction.

Claim 4 $\bigcup_{i=1}^{k}V(C_{i})=V(L_{2}^{H}(G))$.

By the construction of $C_{i}$, we have that
$\bigcup_{i=1}^{k}V(C_{i})\subseteq V(L_{2}^{H}(G))$.

Let $f(x,e)\in V(L_{2}^{H}(G))$, with $e\in E(G)$ and $x\in V(G)$, such that
$e$ is incident with $x$.

Since $\mathfrak{P}$ is a partition of the edges of $G$, then there exists
$P_{i}\in\mathfrak{P}$ such that $e\in E(P_{i})$. It follows from the
construction of $C_{i}$ that $f(x,e)\in
V(C_{i})\subseteq\bigcup_{j=1}^{k}V(C_{j})$. Hence,
$V(L_{2}^{H}(G))\subseteq\bigcup_{j=1}^{k}V(C_{j})$.

Therefore, $\bigcup_{i=1}^{k}V(C_{i})=V(L_{2}^{H}(G))$.

Claim 5 $M=\bigcup_{i=1}^{k}E(C_{i})\setminus M_{J}$ is a perfect matching in
$L_{2}^{H}(G)$.

Recall $M_{J}=\\{f(x,e)f(y,e)\in E(L_{2}^{H}(G)):e=xy\in E(G)\\}$.

It follows from the construction of $C_{i}$ and claims 3 and 4 that $M$ is a
perfect matching in $L_{2}^{H}(G)$.

Therefore, $M$ is a perfect matching in $L_{2}^{H}(G)$, such that $M\cap
M_{J}=\emptyset$. ∎

######  Theorem 10.

Let $G$ be an $H$-colored multigraph. Then:

  1. a.

If $G$ has a closed Euler dynamic $H$-trail, then $L_{n}^{H}(G)$ is
hamiltonian, for every $n\geq 2$.

  2. b.

If $L_{n}^{H}(G)$ is hamiltonian, for some $n\geq 3$, then $G$ has a closed
Euler dynamic $H$-trail.

  3. c.

$G$ has a closed Euler dynamic $H$-trail if and only if $L_{n}^{H}(G)$ is
hamiltonian, for every $n\geq 3$.

###### Proof.

Let $G$ be an $H$-colored multigraph.

a. It follows from Theorems 8 and 9 and definition of $L_{n}^{H}(G)$.

b. Suppose that there exist $n\geq 3$, such that $L_{n}^{H}(G)$is hamiltonian.
Let $C^{\prime}$ be a hamiltonian cycle in $L_{n}^{H}(G)$.

Then, every path from $f(x,e)$ to $f(y,e)$ is in $V(C^{\prime})$ in some
order, for every $e=xy$ in $E(G)$, by the definition of $L_{n}^{H}(G)$. Hence,
we replace the path for the edge $f(x,e)f(y,e)$ to $C^{\prime}$, and we get a
Hamilton cycle in $L_{2}^{H}(G)$, say $C$.

Since $C$ is a Hamilton cycle, then $P=T^{-1}(C)$ is a closed Euler dynamic
$H$-trail in $G$, by Theorem 9.

c. It follows from a and b. ∎

In Theorem 10, we cannot change $n\geq 3$ by $n\geq 2$ because there are
$H$-colored multigraphs without closed Euler dynamic $H$-trail and
$L_{2}^{H}(G)$ is hamiltonian, see Figure 2.

$G$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$e_{1}$ $e_{2}$ $e_{6}$ $e_{7}$
$e_{3}$ $e_{8}$ $e_{5}$ $e_{4}$ $H$$G$$R$

(a) $G$ is an $H$-colored multigraph

$L_{2}^{H}(G)$

(b) $L_{2}^{H}(G)$

Figure 2: The graph $L_{2}^{H}(G)$ is hamiltonian but there is no closed Euler
dynamic $H$-trail in $G$

Recall that $E_{xy}$ is the set of all the edges with end vertices $x$ and
$y$.

######  Definition 2.

Let $G$ be an $H$-colored multigraph and $M$ be a matching in $L_{2}^{H}(G)$.
For each $x$ in $V(G)$, we will say that $M_{x}=\\{f(x,e)f(x,g)\in M\\}$,
i.e., $M_{x}$ consists of the edges in $G_{x}$ that are in $M$. And, for every
pair of vertices $x$ and $y$ in $V(G)$, such that $E_{xy}\neq\emptyset$, we
will define the following sets: $A_{xy}^{M}=\\{e\in E_{xy}:f(x,e)$ is
$M_{x}$-saturate and $f(y,e)$ is not $M_{y}$-saturate$\\}$;
$B_{xy}^{M}=\\{e\in E_{xy}:f(y,e)$ is $M_{y}$-saturate and $f(x,e)$ is not
$M_{x}$-saturate$\\}$; $C_{xy}^{M}=\\{e\in E_{xy}:f(x,e)$ is $M_{x}$-saturate
and $f(y,e)$ is $M_{y}$-saturate$\\}$; and $D_{xy}^{M}=\\{e\in E_{xy}:f(x,e)$
is not $M_{x}$-saturate and $f(y,e)$ is not $M_{y}$-saturate$\\}.$

######  Theorem 11.

Let $G$ be an $H$-colored multigraph. There exists a partition of the edges of
$G$ into closed dynamic $H$-trail, none of them in the form
$(x,a_{1},\ldots,a_{l},y)$, $l\geq 2$, if and only if there exists a non empty
matching, say $M$, in $L_{2}^{H}(G)$, such that for each set
$E_{xy}\neq\emptyset$ one of the following conditions hold: a)
$C_{xy}^{M}=E_{xy}$; b) $|C_{xy}^{M}|<|E_{xy}|$ and
$1\leq|A_{xy}^{M}|=|B_{xy}^{M}|$.

###### Proof.

Let $G$ be an $H$-colored multigraph and $M_{J}$ be the joint matching of
$L_{2}^{H}(G)$.

Suppose that $\mathfrak{P}=\\{P_{1},\ldots,P_{k}\\}$ is a partition of the
edges of $G$ into closed dynamic $H$-trails, such that none of them have the
form $(x,a_{1},\ldots,a_{l},y)$, $l\geq 2$.

By Theorem 9, there exists a perfect matching in $L_{2}^{H}(G)\setminus
M_{J}$. Let $M$ be the perfect matching obtained as in the proof of Theorem 9,
i.e, $M=\bigcup_{i=1}^{k}E(T(P_{i}))\setminus M_{J}$.

Let $x$ and $y$ be a pair of vertices in $G$, such that
$E_{xy}=\\{e_{1},\ldots,e_{q}\\}$, with $q\geq 1$. Since $\mathfrak{P}$ is a
partition of the edges of $G$ into closed dynamic $H$-trails, then there
exists $P_{i}\in\mathfrak{P}$ such that $E_{xy}\cap E(P_{i})\neq\emptyset$,
say $P_{i}=P_{1}$.

Since $P_{1}$ is not of the form $(x,a_{1},\ldots,a_{l},y)$, $l\geq 2$, and
$E_{xy}\cap E(P_{1})\neq\emptyset$, then
$P_{1}=(\ldots,f_{0},x,e_{t_{1}},\ldots,e_{t_{p_{1}}},$ $y,f_{1},\ldots)$,
where $p_{1}\leq q$ and $\\{f_{0},f_{1}\\}\subset E(G)$. (Recall that $M_{x}$
consists of the edges in $G_{x}$ that are in $M$).

If $p_{1}=1$, then $P_{1}=(\ldots,f_{0},x,e_{t_{1}},y,f_{1},\ldots)$. Hence,
$f(x,f_{0})f(x,e_{t_{1}})$ and $f(y,e_{t_{1}})f(y,f_{1})$ are in $M$.

Therefore, $f(x,f_{0})f(x,e_{t_{1}})\in M_{x}$, $f(y,e_{t_{1}})f(y,f_{1})\in
M_{y}$ and $e_{t_{1}}\in C_{xy}^{M}$.

On the other hand, if $p_{1}\geq 2$, then $f(x,f_{0})f(x,e_{t_{1}})$,
$f(y,e_{t_{p_{1}}})f(y,f_{1})$ and $f(y,e_{t_{i}})f(x,e_{t_{i+1}})$ are in
$M$, for every $i\in\\{1,\ldots,p_{1}-1\\}$, see figure 3. Hence,
$e_{t_{1}}\in A_{xy}^{M}$, $e_{t_{p_{1}}}\in B_{xy}^{M}$ and $e_{t_{i}}\in
D_{xy}^{M}$, for every $i\in\\{2,\ldots,p_{1}-1\\}$.

$x$$y$$e_{1}$ $e_{2}$ $e_{p_{1}-1}$ $e_{p_{1}}$ $f_{0}$ $f_{1}$

(a) $P_{1}=(\ldots,f_{0},x,e_{1},\ldots,e_{p_{1}},y,f_{1},\ldots)$

$f(x,e_{1})$$f(y,e_{1})$$f(x,e_{2})$$f(y,e_{2})$$f(x,e_{p_{1}-1})$$f(y,e_{p_{1}-1})$$f(x,e_{p_{1}})$$f(y,e_{p_{1}})$$f(x,f_{0})$$f(y,f_{1})$

(b) Cycle in $L_{2}^{H}(G)$ obtained from $P_{1}$.

Figure 3: In b, the continued edges are in $M$ and the dashed edges are in
$M_{J}$

If $E_{xy}\setminus\\{e_{t_{1}},\ldots,e_{t_{p_{1}}}\\}=\emptyset$, then
$C_{xy}^{M}=E_{xy}$ (when $p_{1}=1$ occurs) or $|C_{xy}^{M}|<|E_{xy}|$ and
$1\leq|A_{xy}^{M}|=|B_{xy}^{M}|$ (when $p_{1}\geq 2$). So, suppose that
$E_{1}=E_{xy}\setminus\\{e_{t_{1}},\ldots,e_{t_{p_{1}}}\\}\neq\emptyset$, then
there exists $P\in\mathfrak{P}$, such that $E(P)\cap E_{1}\neq\emptyset$.

Since $P$ is not of the form $(x,a_{1},\ldots,a_{l},y)$, $l\geq 2$, and
$E_{1}\cap E(P)\neq\emptyset$, then $P=(\ldots,f_{2},x,e_{s_{1}},\ldots,$
$e_{s_{p_{2}}},y,f_{3},\ldots)$, where $\\{f_{2},f_{3}\\}\subset E(G)$. We
will consider two cases.

If $p_{2}=1$, then $P=(\ldots,f_{2},x,e_{s_{1}},y,f_{3},\ldots)$. By the
construction of $M$ we have that the edges $f(x,f_{2})f(x,e_{s_{1}})$ and
$f(y,e_{s_{1}})f(y,f_{3})$ are in $M$. Thus, $f(x,f_{2})f(x,e_{s_{1}})\in
M_{x}$, $f(y,e_{s_{1}})f(y,s_{1})\in M_{y}$ and $e_{s_{1}}\in C_{xy}^{M}$.

On the other hand, if $p_{2}\geq 2$, then $f(x,f_{2})f(x,e_{s_{1}})$,
$f(y,e_{s_{p_{2}}})f(y,f_{3})$ and $f(y,e_{s_{i}})f(x,e_{s_{i+1}})$ are in
$M$, for every $i\in\\{1,\ldots,s_{2}-1\\}$. Hence, $e_{s_{1}}\in A_{xy}^{M}$,
$e_{s_{p_{2}}}\in B_{xy}^{M}$ and $e_{s_{i}}\in D_{xy}^{M}$, for every
$i\in\\{2,\ldots,p_{2}-1\\}$.

If $E_{2}=E_{1}\setminus\\{e_{s_{1}},\ldots,e_{s_{p_{2}}}\\}=\emptyset$, then
$C_{xy}^{M}=E_{xy}$ (when $p_{1}=p_{2}=1$) or $|C_{xy}^{M}|<|E_{xy}|$ and
$1\leq|A_{xy}^{M}|=|B_{xy}^{M}|$ (when $p_{1}\geq 2$ or $p_{2}\geq 2$).
Otherwise, there exists $P^{\prime}\in\mathfrak{P}$, such that $E_{2}\cap
E(P^{\prime})\neq\emptyset$ and we can repeat this procedure and after a
finite number of steps we obtain that $C_{xy}^{M}=E_{xy}$ or
$|C_{xy}^{M}|<|E_{xy}|$ and $1\leq|A_{xy}^{M}|=|B_{xy}^{M}|$.

Now, suppose that there exists $M$, a matching in $L_{2}^{H}(G)$, such that
for every set $E_{xy}\neq\emptyset$, it holds that: $C_{xy}^{M}=E_{xy}$ or
$|C_{xy}^{M}|<|E_{xy}|$ and $1\leq|A_{xy}^{M}|=|B_{xy}^{M}|$.

If $M$ is a perfect matching in $L_{2}^{H}(G)\setminus M_{J}$, then there
exists a partition of $E(G)$ into closed dynamic $H$-trails, by Theorem 9. So,
suppose that $M$ is not a perfect matching in $L_{2}^{H}(G)\setminus M_{J}$.
Recall that $M_{x}=M\cap E(G_{x})$, for every $x\in V(G)$.

Since $C_{xy}^{M}=E_{xy}\neq\emptyset$ or $1\leq|A_{xy}^{M}|$, then for every
$x\in V(G)$, $M_{x}\neq\emptyset$.

Let $N=\bigcup_{x\in V(G)}M_{x}$. Notice that $N$ is a matching in
$L_{2}^{H}(G)\setminus M_{J}$, $A_{xy}^{M}=A_{xy}^{N}$,
$B_{xy}^{M}=B_{xy}^{N}$, $C_{xy}^{M}=C_{xy}^{N}$ and $D_{xy}^{M}=D_{xy}^{N}$.
So, for every set $E_{xy}\neq\emptyset$, it holds that: $C_{xy}^{N}=E_{xy}$ or
$|C_{xy}^{N}|<|E_{xy}|$ and $1\leq|A_{xy}^{N}|=|B_{xy}^{N}|$.

Let $x$ and $y$ be two different vertices in $V(G)$, such that
$E_{xy}\neq\emptyset$.

If $C_{xy}^{N}=E_{xy}$, then $f(x,e)$ and $f(y,e)$ are $N$-saturate, for every
$e\in E_{xy}$. So, we do not add any edge to $N$.

On the other hand, if $|C_{xy}^{N}|<|E_{xy}|$ and
$1\leq|A_{xy}^{N}|=|B_{xy}^{N}|$, then we will consider $G_{xy}$, the subgraph
of $L_{2}^{H}(G)$ induced by the set $\\{f(x,e):e\in E_{xy}\setminus
C_{xy}^{N}\\}\cup\\{f(y,e):e\in E_{xy}\setminus C_{xy}^{N}\\}$.

Since $|C_{xy}^{N}|<|E_{xy}|$, then $V(G_{xy})\neq\emptyset$. Let
$A_{xy}^{N}=\\{e_{1},\ldots,e_{t}\\}$ and
$B_{xy}^{N}=\\{f_{1},\ldots,f_{t}\\}$, since $1\leq|A_{xy}^{N}|=|B_{xy}^{N}|$
we have that $t\geq 1$.

If $D_{xy}^{N}=\emptyset$, then we add the edges $f(y,e_{i})f(x,f_{i})$ to
$N$, for every $i\in\\{1,\ldots,t\\}$. By the definition of the edges of
$L_{2}^{H}(G)$ (point b) and the definition of $G_{xy}$, we have that
$f(y,e_{i})f(x,f_{i})\in E(G_{xy})$. Moreover,
$N\cup\\{f(y,e_{i})f(x,f_{i}):i\in\\{1,\ldots,t\\}\\}$ is still a matching.

On the other hand, when $D_{xy}^{N}\neq\emptyset$, let
$D_{xy}^{N}=\\{g_{1},\ldots,g_{s}\\}$. We add the edges
$f(y,e_{1})f(x,g_{1})$, $f(x,f_{1})f(y,g_{s})$, $f(y,e_{i})f(x,f_{i})$ and
$f(y,g_{j})f(x,g_{j+1})$ to $N$, for every $i\in\\{2,\ldots,t\\}$ and
$j\in\\{1,\ldots,s-1\\}$.

By the definition of the edges of $L_{2}^{H}(G)$ and the definition of
$G_{xy}$, we have that all the edges we add to $N$ are in $E(G_{xy})$ and $N$
is still a matching.

Thus, we add edges to $N$ in such a way every vertex in $G_{xy}$ is
$N$-saturate.

So, we repeat the same process for $x$ and $y$ in $V(G)$ such that
$E_{xy}\neq\emptyset$.

Therefore, $N$ is a perfect matching in $L_{2}^{H}(G)\setminus M_{J}$ and
there exists a partition of $E(G)$ into closed dynamic $H$-trails, by Theorem
9 and, by the construction of $N$, none of them is of the form
$(x,a_{1},\ldots,a_{l},y)$, with $l\geq 2$. ∎

The following result shows a condition on the graph $G_{x}$ that guarantees
the existence of closed Euler dynamic $H$-trail.

######  Theorem 12.

Let $G$ be a connected $H$-colored multigraph, such that $G_{u}$ is a complete
$k_{u}$-partite graph for every $u\in V(G)$ and for some $k_{u}$ in
$\mathbb{N}\setminus\\{1\\}$. Then $G$ has a closed Euler dynamic $H$-trail if
and only if there exists a matching $M$ in $L_{2}^{H}(G)$, such that for every
set $E_{xy}\neq\emptyset$ one of the following conditions hold: a)
$C_{xy}^{M}=E_{xy}$; or b) $|C_{xy}^{M}|<|E_{xy}|$ and
$1\leq|A_{xy}^{M}|=|B_{xy}^{M}|$.

###### Proof.

Let $G$ be a connected $H$-colored multigraph, such that $G_{u}$ is a complete
$k_{u}$-partite graph for every $u\in V(G)$ and for some $k_{u}$ in
$\mathbb{N}\setminus\\{1\\}$.

Suppose that $G$ has a closed Euler dynamic $H$-trail, say $P$.

Case 1. $P$ is not of the form $(x,e_{1},\ldots,e_{k},y)$, with $k\geq 2$.

In this case there exists a matching, say $M$, in $L_{2}^{H}(G)$, such that
for every set $E_{xy}\neq\emptyset$ one of the following conditions hold:
$C_{xy}^{M}=E_{xy}$ or $|C_{xy}^{M}|<|E_{xy}|$ and
$1\leq|A_{xy}^{M}|=|B_{xy}^{M}|$.

Case 2. $P=(x,e_{1},\ldots,e_{k},y)$, with $k\geq 2$.

In this case, since $G_{x}$ is a complete $k_{x}$-partite graph, for some
$k_{x}\geq 2$, then there exists two edges $e$ and $f$ in $E(G)=E(P)$, such
that $c(e)c(f)\in E(H)$. Suppose, without loss of generality, that
$c(e_{1})c(e_{2})\in E(H)$.

If $k=2$, then $P^{\prime}=(x,e_{1},y,e_{2},x)$ is a closed Euler dynamic
$H$-trail. Otherwise, since $G_{x}$ is $k_{x}$-partite graph, we have that
$c(e_{1})c(e_{k})\in E(H)$ or $c(e_{2})c(e_{k})\in E(H)$.

Hence, $P^{\prime}=(x,e_{1},y,e_{2},\ldots,e_{k},x)$ or
$P^{\prime}=(x,e_{1},e_{3},\ldots,e_{k},y,e_{2},x)$ is a closed Euler dynamic
$H$-trail. By Theorem 11, there exists a matching $M$ in $L_{2}^{H}(G)$, such
that for every set $E_{xy}\neq\emptyset$, $C_{xy}^{M}=E_{xy}$ or
$|C_{xy}^{M}|<|E_{xy}|$ and $1\leq|A_{xy}^{M}|=|B_{xy}^{M}|$.

Conversely, suppose that there exists a matching $M$ in $L_{2}^{H}(G)$, such
that for every set $E_{xy}\neq\emptyset$ one of the following conditions hold:
$C_{xy}^{M}=E_{xy}$ or $|C_{xy}^{M}|<|E_{xy}|$ and
$1\leq|A_{xy}^{M}|=|B_{xy}^{M}|$.

It follows from Theorem 11 that there exists a partition of $E(G)$ into closed
dynamic $H$-trails, none of them in the form $(x,e_{1},\ldots,e_{l},y)$, with
$l\geq 2$, say $\mathcal{P}=\\{P_{1},\ldots,P_{k}\\}$.

If $k=1$, then $E(P_{1})=E(G)$ and $P_{1}$ is a closed Euler dynamic
$H$-trail. Otherwise, since $G$ is connected it follows that there exists
$P_{i}\in\mathcal{P}\setminus\\{P_{1}\\}$, say $P_{2}$, such that
$V(P_{1})\cap V(P_{2})\neq\emptyset$. Since $P_{1}$ and $P_{2}$ are closed, we
can suppose that $P_{1}=(x_{0},e_{1},\ldots,e_{m},x_{0})$, where
$e_{1}=x_{0}x_{1}$ and $e_{m}=x_{k_{1}}x_{0}$, and
$P_{2}=(y_{0},f_{1},\ldots,f_{n},y_{0})$, where $f_{1}=y_{0}y_{1}$ and
$f_{n}=y_{k_{2}}y_{0}$, such that $x_{0}=y_{0}$. By the definition of dynamic
$H$-trail, we have that $c(e_{1})c(e_{m})$ and $c(f_{1})c(f_{n})$ are in
$E(H)$. Furthermore, $e_{1},f_{1},e_{m}$ and $f_{n}$ are incident with
$x_{0}=y_{0}$. Hence, $e_{1}e_{m}$ and $f_{1}f_{n}$ are in $E(G_{x_{0}})$.

We will consider the following: if $\\{e_{1},f_{1}\\}\subseteq E_{j}^{x_{0}}$
or $\\{e_{m},f_{n}\\}\subseteq E_{j}^{x_{0}}$, for some
$j\in\\{1,\ldots,k_{x_{0}}\\}$, it follows that $e_{1}f_{n}$ and $e_{m}f_{1}$
are in $E(G_{x_{0}})$, because $G_{x_{0}}$ is a complete $k_{x_{0}}$-partite
graph. In other case, $e_{1}f_{1}$ and $e_{m}f_{n}$ are in $E(G_{x_{0}})$.

By the definition of $G_{x_{0}}$, we have that $c(e_{1})c(f_{n})$ and
$c(e_{m})c(f_{1})$ are edges of $H$ or $c(e_{1})c(f_{1})$ and
$c(e_{m})c(f_{n})$ are edges of $H$.

If $c(e_{1})c(f_{n})$ and $c(e_{m})c(f_{1})$ are edges of $H$, we have that
$Q_{1}=P_{1}\cup P_{2}$ is a closed dynamic $H$-trail. And, if
$c(e_{1})c(f_{1})$ and $c(e_{m})c(f_{n})$ are edges of $H$, we have that
$Q_{1}=P_{1}\cup P_{2}^{-1}$ is a closed dynamic $H$-trail.

If $E(Q_{1})=E(G)$, then $Q_{1}$ is a closed Euler dynamic $H$-trail.
Otherwise, since $G$ is connected it follows that there exists
$P_{i}\in\mathcal{P}\setminus\\{P_{1},P_{2}\\}$, say $P_{3}$, such that
$V(Q_{1})\cap V(P_{3})\neq\emptyset$. Since $Q_{1}$ and $P_{3}$ are closed, we
can suppose that $P_{1}=(v_{1},a_{1},\ldots,a_{s},v_{0})$, where
$a_{1}=v_{0}v_{1}$ and $a_{s}=v_{k_{3}}v_{0}$, and
$P_{3}=(u_{0},g_{1},\ldots,g_{t},u_{0})$, where $g_{1}=u_{0}u_{1}$ and
$g_{t}=u_{k_{3}}u_{0}$, such that $v_{0}=u_{0}$. By the definition of dynamic
$H$-trial, we have that $c(a_{1})c(a_{s})$ and $c(g_{1})c(g_{t})$ are in
$E(H)$. Furthermore, $a_{1},g_{1},a_{s}$ and $g_{t}$ are incident with
$u_{0}=v_{0}$. Hence, $a_{1}a_{s}$ and $g_{1}g_{t}$ are in $E(G_{v_{0}})$.

We will consider the following: if $\\{a_{1},g_{1}\\}\subseteq E_{j}^{v_{0}}$
or $\\{a_{s},g_{t}\\}\subseteq E_{j}^{v_{0}}$, for some
$j\in\\{1,\ldots,k_{v_{0}}\\}$, it follows that $a_{1}g_{t}$ and $a_{s}g_{1}$
are in $E(G_{v_{0}})$, because $G_{v_{0}}$ is a complete $k_{v_{0}}$-partite
graph. In other case, $a_{1}g_{1}$ and $a_{s}g_{t}$ are in $E(G_{v_{0}})$.

By the definition of $G_{v_{0}}$, we have that $c(a_{1})c(g_{t})$ and
$c(a_{s})c(g_{1})$ are edges of $H$ or $c(a_{1})c(g_{1})$ and
$c(a_{s})c(g_{t})$ are edges of $H$.

If $c(a_{1})c(g_{t})$ and $c(a_{s})c(g_{1})$ are edges of $H$, we have that
$Q_{2}=Q_{1}\cup P_{3}$ is a closed dynamic $H$-trail. And, if
$c(a_{1})c(g_{1})$ and $c(a_{s})c(g_{t})$ are edges of $H$, we have that
$Q_{2}=Q_{1}\cup P_{3}^{-1}$ is a closed dynamic $H$-trail.

If $E(Q_{2})=E(G)$, then $Q_{2}$ is a closed Euler dynamic $H$-trail.
Otherwise, we repeat the procedure until we get the desired closed Euler
dynamic $H$-trail. ∎

In Theorem 12 we cannot change the hypothesis “$G_{u}$ is a complete
$k_{u}$-partite for every $u\in V(G)$” to “$G_{u}$ has a complete
$k_{u}$-partite spanning subgraph”, as Figure 4 shows.

$G$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$x_{6}$2 1 1 3 5 4 1 3 2 $H$23451

(a) $G$ is an $H$-colored multigraph

$L_{2}^{H}(G)$$G_{x_{1}}$$G_{x_{2}}$$G_{x_{3}}$$G_{x_{4}}$$G_{x_{5}}$$G_{x_{6}}$

(b) $L_{2}^{H}(G)$

Figure 4: $G_{u}$ is a complete $k_{u}$-partite graph, for $u\in
V(G)\setminus\\{x_{4}\\}$, and $G_{x_{4}}$ has a bipartite spanning subgraph
but there is no closed Euler dynamic $H$-trail in $G$

######  Corollary 13.

Let $G$ be an $H$-colored multigraph. Then $G_{x}$ has a perfect matching, for
every $x\in V(G)$, if and only if there exists a partition of $E(G)$ into
closed $H$-trails.

###### Proof.

Let $G$ be an $H$-colored multigraph and $M_{J}$ be the joint matching of
$L_{2}^{H}(G)$.

Suppose that $G_{x}$ has a perfect matching, for every $x\in V(G)$, say
$M_{x}$. Let $M=\bigcup_{x\in V(G)}M_{x}$.

It follows from the definition of $M_{J}$ that $M\cap M_{J}=\emptyset$. Hence,
$G$ has a partition of its edges into closed dynamic $H$-trails, by Theorem 9.

Let $\mathcal{P}$ be the partition that is obtained as in the proof of Theorem
9. It follows, from the construction of each dynamic $H$-trail in
$\mathcal{P}$, that there is no lane change. So, $\mathcal{P}$ is a partition
of $E(G)$ into closed $H$-trails.

Now, suppose that there exists a partition of $E(G)$ into closed $H$-trails,
say $\mathcal{P}$. By Theorem 9, there exists a perfect matching in
$L_{2}^{H}(G)\setminus M_{J}$. Let $M$ be the perfect matching that is
obtained as in the proof of Theorem 9.

Let $f(x,e)\in V(L_{2}^{H}(G))$. Then, there exists $P\in\mathcal{P}$ such
that $e\in E(P)$. Since $P$ is an $H$-trail and by the construction of $M$, it
follows that $P=(u,g,x,e,v,\ldots)$ and $f(x,g)f(x,e)\in M$. Moreover,
$f(x,g)f(x,e)\in M\cap E(G_{x})$.

Therefore, $M\cap E(G_{x})$ is a perfect matching of $G_{x}$. ∎

Notice that if $H$ is a complete graph without loops and $G$ is an $H$-colored
multigraph. Then $P$ is a properly colored closed trail if and only if $P$ is
an closed $H$-trail.

######  Corollary 14 (Kotzig).

Let $G$ be an edge-colored eulerian multigraph. Then $G$ has a properly
colored closed Euler trail if and only if $\delta_{i}(x)\leq\sum_{j\neq
i}\delta_{j}(x)$, where $\delta_{i}(x)$ is the number of edges with color $i$
incident with $x$, for each vertex $x$ of $G$.

###### Proof.

Let $G$ be an $H$-colored multigraph, where $H$ is a complete graph without
loops and $|V(H)|=c$.

Let $G_{u}$, with $u\in V(G)$. It follows from the definition of $G_{u}$ and
$H$ is a complete graph that $G_{u}$ is a complete $k_{u}$-paritite graph with
independent sets $E_{i}^{u}=\\{e\in E(G)\>:\>e=ux\textrm{ for some }x\in
V(G)\textrm{ and }c(e)=i\\}$, with $i\in\\{1,\ldots,c\\}$. Moreover,
$|E_{i}^{u}|=\delta_{i}(u)$.

Suppose that $G$ has a closed Euler $H$-trail. By Corollary 13 $G_{u}$ has a
perfect matching, for every $u\in V(G)$.

Hence, $\delta_{i}(u)=|E_{i}^{u}|=o(G\setminus S)\leq|S|=\sum_{j\neq
i}|E_{j}^{u}|=\sum_{j\neq i}\delta_{i}(u)$, where $S=V(G_{u})\setminus
E_{i}^{u}$, by Theorem 4.

Suppose that $|E_{i}^{u}|=\delta_{i}(x)\leq\sum_{j\neq
i}\delta_{j}(x)=\sum_{j\neq i}|E_{j}^{u}|$, for each vertex $x$ of $G$.

Claim 1. $G_{u}$ has a perfect matching.

Let $S$ be a proper subset of $V(G_{u})$. Consider $G_{u}\setminus S$.

Case 1. $G_{u}\setminus S$ is connected.

Then $o(G_{u}\setminus S)\leq 1\leq|S|$.

Case 2. $G_{u}\setminus S$ is disconnected.

Since $G_{u}$ is a complete $k_{u}$-partite graph, then $V(G_{u}\setminus
S)\subseteq E_{i}^{u}$, for some $i\in\\{1,\ldots,c\\}$. Hence
$o(G_{u}\setminus S)=|V(G_{u}\setminus S)|\leq|E_{i}^{u}|\leq\sum_{j\neq
i}|E_{j}^{u}|\leq|S|$.

Therefore, it follows from Theorem 4 that $G_{u}$ has a perfect matching.

Let $M=\bigcup_{u\in V(G)}M_{u}$, where $M_{u}$ is a perfect matching in
$G_{u}$. So, $M$ is a perfect matching in $L_{2}^{H}(G)$ and
$C_{xy}^{M}=E_{xy}$, for every $E_{xy}\neq\emptyset$.

It follows from Theorem 12 and Corollary 13 that $G$ has a closed Euler
$H$-trail. ∎

######  Corollary 15 ([11]).

Let $H$ be a graph possibly with loops and $G$ be an $H$-colored multigraph
without loops. Suppose that $G$ is Eulerian and $G_{u}$ is a complete
$k_{u}$-partite graph, for every $u$ in $V(G)$ and for some $k_{u}$ in
$\mathbb{N}$. Then $G$ has a closed Euler $H$-trail if and only if
$|C_{i}^{u}|\leq\sum_{j\neq i}|C_{j}^{u}|$ for every $u$ in $V(G)$, where
$\\{C_{1}^{u},...,C_{k_{u}}^{u}\\}$ is the partition of $V(G_{u})$ into
independent sets.

## References

  * [1] S. K. Ahuja.  Algorithms for routing and channel assignment in wireless infrastructure networks.  PhD thesis, The University of Arizona., 2010.
  * [2] J. Bang-Jensen, T. Bellitto, and A. Yeo.  On supereulerian 2-edge-coloured graphs.  Graphs and Combinatorics, 37(6):2601–2620, 2021.
  * [3] J. Bang-Jensen and G. Z. Gutin.  Digraphs: theory, algorithms and applications.  Springer Science & Business Media, (2008).
  * [4] G. Benítez-Bobadilla, H. Galeana-Sánchez, and C. Hernández-Cruz.  Characterization of color patterns by dynamic $H$-paths.  Discrete Applied Mathematics, 267:41–51, 2019.
  * [5] J. A. Bondy and U. S. R. Murty.  Graph theory with applications, volume 290.  Citeseer, 1976.
  * [6] W. Chou, Y. Manoussakis, O. Megalakaki, M. Spyratos, and Z. Tuza.  Paths through fixed vertices in edge-colored graphs.  Mathématiques et sciences humaines, 127:49–58, 1994.
  * [7] P. Delgado-Escalante and H. Galeana-Sánchez.  Restricted domination in arc-colored digraphs.  AKCE International Journal of Graphs and Combinatorics, 11(1):95–104, 2014.
  * [8] P. Delgado-Escalante, H. Galeana-Sánchez, and L. P. Ramírez.  Independent restricted domination and the line digraph.  AKCE International Journal of Graphs and Combinatorics, 9(1):31–42, 2012.
  * [9] D. Dorninger.  Hamiltonian circuits determining the order of chromosomes.  Discrete Applied Mathematics, 50(2):159–168, 1994.
  * [10] D. Dorninger and W. Timischl.  Geometrical constraints on Bennett’s predictions of chromosome order.  Heredity, 58:321–325, 1987.
  * [11] H. Galeana-Sánchez, R. Rojas-Monroy, R. Sánchez-López, and J. I. Villarreal-Valdés.  Some conditions for the existence of euler $H$-trails.  Graphs and Combinatorics, 35(5):1197–1208, 2019.
  * [12] H. Galeana-Sánchez and R. Sánchez-López.  $H$-kernels in infinite digraphs.  Graphs and Combinatorics, 29(4):913–920, 2013.
  * [13] Z. Guo, H. Broersma, B. Li, and S. Zhang.  Almost eulerian compatible spanning circuits in edge-colored graphs.  Discrete Mathematics, 344(1):112174, 2020.
  * [14] Z. Guo, B. Li, X. Li, and S. Zhang.  Compatible spanning circuits in edge-colored graphs.  Discrete Mathematics, 343(7):111908, 2020.
  * [15] F. Harary and C. S. J. Nash-Williams.  On eulerian and hamiltonian graphs and line graphs.  Canadian Mathematical Bulletin, 8(6):701–709, 1965.
  * [16] A. Kotzig.  Moves without forbidden transitions in a graph.  Matematickỳ časopis, 18(1):76–80, 1968.
  * [17] V. Linek and B. Sands.  A note on paths in edge-coloured tournaments.  Ars Combinatoria, 44:225–228, 1996.
  * [18] S. Sankararaman, A. Efrat, S. Ramasubramanian, and P. K. Agarwal.  On channel-discontinuity-constraint routing in wireless networks.  Ad hoc networks, 13:153–169, 2014.
  * [19] M. Szachniuk, M. C. De Cola, G. Felici, and J. Blazewicz.  The orderly colored longest path problem–a survey of applications and new algorithms.  RAIRO-Operations Research, 48(1):25–51, 2014.
  * [20] M. Szachniuk, M. Popenda, R. W. Adamiak, and J. Blazewicz.  An assignment walk through 3D NMR spectrum.  In 2009 IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology, pages 215–219. IEEE, 2009.
  * [21] W. T. Tutte.  The factorization of linear graphs.  Journal of the London Mathematical Society, 1(2):107–111, 1947\.