# Lowest accreting protoplanetary discs consistent with X-ray photoevaporation
driving their final dispersal

Barbara Ercolano,1 Giovanni Picogna1 and Kristina Monsch2
1 University Observatory, Faculty of Physics, Ludwig-Maximilians-Universität
München, Scheinerstr. 1, 81679 Munich, Germany
2 Harvard-Smithsonian Center for Astrophysics, 60 Garden Street, Cambridge MA
02138, USA E-mail<EMAIL_ADDRESS>
(Accepted XXX. Received YYY; in original form ZZZ)

###### Abstract

Photoevaporation from high energy stellar radiation has been thought to drive
the dispersal of protoplanetary discs. Different theoretical models have been
proposed, but their predictions diverge in terms of the rate and modality at
which discs lose their mass, with significant implications for the formation
and evolution of planets. In this paper we use disc population synthesis
models to interpret recent observations of the lowest accreting protoplanetary
discs, comparing predictions from EUV-driven, FUV-driven and X-ray driven
photoevaporation models. We show that the recent observational data of stars
with low accretion rates (low accretors) point to X-ray photoevaporation as
the preferred mechanism driving the final stages of protoplanetary disc
dispersal. We also show that the distribution of accretion rates predicted by
the X-ray photoevaporation model is consistent with observations, while other
dispersal models tested here are clearly ruled out.

###### keywords:

protoplanetary discs – photoevaporation – accretion rates

††pubyear: 2023††pagerange: Lowest accreting protoplanetary discs consistent
with X-ray photoevaporation driving their final dispersal–Lowest accreting
protoplanetary discs consistent with X-ray photoevaporation driving their
final dispersal

##  1 Introduction

The mechanisms shaping the final stages of protoplanetary disc evolution may
have a dramatic impact on the outcome of the planet formation process (e.g.
Ercolano & Rosotti, 2015; Ercolano et al., 2017b; Monsch et al., 2019;
Jennings et al., 2018; Alexander & Pascucci, 2012; Carrera et al., 2017). Disc
winds–driven by photoevaporation from the central star–are a promising
candidate to explain the phenomenology of the late stages of evolution leading
to the final dispersal of the disc material (e.g. Ercolano & Owen, 2016;
Ercolano et al., 2017a; Weber et al., 2020), while magnetically driven discs
may play a role in the early evolution (e.g. Ercolano & Pascucci, 2017;
Pascucci et al., 2022; Lesur et al., 2022).

In the viscous accretion scenario, accretion rates in protoplanetary discs are
expected to decrease with age, while mass-loss rates due to X-ray or EUV-
driven photoevaporation should remain roughly constant throughout the lifetime
of the disc. Over the years several photoevaporation models have been
developed (e.g. Ercolano & Pascucci, 2017; Ercolano & Picogna, 2022, for
recent reviews), which predict different values for the mass-loss rates.
Photoevaporation can only be efficient at dispersing the disc when the wind
rates exceed the rate at which the disc is accreting. Consequently, in this
picture, the objects with the lowest possible accretion rates should be stars
transitioning from disc-bearing to disc-less and thus offer an insight into
the final stages of disc dispersal.

In this context, Thanathibodee et al. (2022) recently looked for an accretion
signature in disc-bearing stars previously thought to be non-accretors, using
the He I $\lambda 10830\mbox{\AA}$ line. This high excitation line allowed
them to probe material in the innermost regions of protoplanetary discs,
possibly detecting accretion streamers. They found that a large fraction of
this sample (at least $20-30\%$) indeed shows signs of accretion via strong
red-shifted absorption consistent with free-fall velocities, preferentially at
young ages and almost independently of the stellar mass. The accretion rates
were then determined independently by fitting the H$\alpha$ profiles of a sub-
sample of these stars using magnetospheric accretion models (Thanathibodee et
al., 2023, from here on T23). Interestingly, although the sample size was very
small (24 sources), the authors derived a minimum accretion rate of the order
of $10^{-10}$ M⊙ yr-1, which is roughly one order of magnitude above the
detection limit for their sample. Thus the observed value for the accretion
rates of the lowest accreting objects hints at a physical mechanism shutting
off accretion in the last stages of evolution.

In this work, we test three photoevaporation scenarios, namely EUV-driven
(Alexander et al., 2006), FUV-driven (Komaki et al., 2021), and X-ray driven
(Ercolano et al., 2021; Picogna et al., 2021) photoevaporation, for which
suitable mass-loss prescriptions exist. To this aim, we produce synthetic
populations of viscously evolving discs dispersed by photoevaporation to
produce mass accretion distributions to compare with the recent observations
of T23.

##  2 Methods

Figure 1: Panel a: histogram of the stellar mass distribution in our
population synthesis (in blue) compared with the one from the sample of T23 in
orange, where the KDE is overplotted with a solid blue and orange line
respectively, and the median value ($0.3$ M⊙) is marked with a dashed blue
line for our sample and with a dashed orange line for the observed sample
($0.4$ M⊙). Panel b: histogram of the X-ray luminosity density distribution in
the X-ray population synthesis, where the KDE is overplotted with a blue solid
line and the median value of $29.4$ is marked with a dotted dashed red line.
Panel c: histogram of the ionizing flux density distribution in the EUV
population synthesis, where the KDE is overplotted with a blue solid line and
the median value of $41.2$ is marked with a dotted dashed red line.

We use the one-dimensional viscous evolution code SPOCK (Ercolano & Rosotti,
2015) which evolves the gas following

$\frac{\partial{\Sigma}}{\partial{t}}=\frac{1}{R}\frac{\partial}{\partial{R}}\left[3R^{1/2}\frac{\partial}{\partial{R}}(\nu\Sigma
R^{1/2})\right]-\dot{\Sigma}_{w}(R,t)\,,$ (1)

where the first term on the right hand side describes the viscous disc
evolution (Lynden-Bell & Pringle, 1974), and the second one is a sink term
modelling the mass-loss due to internal disc photoevaporation.

We consider either an EUV, FUV, or X-ray mass-loss rate internal
photoevaporation profile as they are well-studied in the literature, and
simple 1D prescriptions of the disc mass-loss rates are provided.

###  2.1 X-ray photoevaporation

The X-ray surface mass-loss rate is given following equations 2 and 3 of
Picogna et al. (2019), with the parameters for the different stellar masses
being provided in Table 1 of Picogna et al. (2021). The mass-loss rate as a
function of X-ray luminosity and stellar mass can be described by (Ercolano et
al., 2021; Picogna et al., 2021)

$\dot{M}_{\mathrm{XEUV}}(M_{\star},L_{X,\mathrm{soft}})=\dot{M}_{\mathrm{XEUV}}(M_{\star})\frac{\dot{M}_{\mathrm{XEUV}}(L_{X,\mathrm{soft}})}{\dot{M}_{\mathrm{XEUV}}(L_{X,\mathrm{soft,mean}})}\,,$
(2)

where the mass-loss rate as a function of stellar mass is

$\dot{M}_{\mathrm{XEUV}}(M_{\star})=3.93\times
10^{-8}\left(\frac{M_{\star}}{M_{\odot}}\right)$ (3)

and the dependence on the soft component of the X-ray luminosity is given by

$\dot{M}_{\mathrm{XEUV}}(L_{X,\mathrm{soft}})=10^{a_{L}\exp{\left(\frac{(\ln(\log(L_{X,\mathrm{soft}})-b_{L})^{2}}{c_{L}}\right)+d_{L}}}\,,$
(4)

with $a_{L}=-1.947\cdot 10^{17}$, $b_{L}=-1.572\cdot 10^{-4}$,
$c_{L}=-0.2866$, $d_{L}=-6.694$. The soft component of the X-ray luminosity is
given by

$L_{X,\mathrm{soft}}=10^{0.95\log{(L_{X})}+1.19}\,,$ (5)

and was obtained by performing a linear fit between the nominal and soft X-ray
luminosities listed in Table 4 of Ercolano et al. (2021). The mean component
of the X-ray luminosity is the soft X-ray luminosity
$L_{X,\mathrm{soft,mean}}$ of a star with a total X-ray luminosity given by
the observational relation between stellar mass and X-ray luminosity (see eq.
15, Güdel et al., 2007).

###  2.2 EUV photoevaporation

We divided the EUV surface mass-loss rate in its diffuse and direct components
following Alexander & Armitage (2007):

$\dot{\Sigma}_{\mathrm{EUV}}(R)=\dot{\Sigma}_{\mathrm{diffuse}}(R)+\dot{\Sigma}_{\mathrm{direct}}(R,t)\cdot
f(R)\,,$ (6)

where $f(R)=1+\exp{(-\frac{R-R_{\mathrm{in}}}{H_{\mathrm{in}}})}$ is a
smoothing function to avoid numerical problems close to the disc inner edge,
$R_{\mathrm{in}}(t)$ is the radius of the inner disc edge and
$H_{\mathrm{in}}(t)$ is the disc scale height at the inner edge.

Figure 2: Synthetic populations showing the accretion rates as a function of
age. The color mapping shows the probability of finding an object of a given
age accreting at a given accretion rate (see text for details). Top row: discs
are dispersed by EUV photoevaporation; bottom row: discs are dispersed by
X-ray photoevaporation. The first column shows the full stellar mass sample,
while the following columns show the result divided in three different stellar
mass bins. The low-accretors population of T23 is overplotted with dots with
variable size increasing by their stellar mass.

The diffuse component of the EUV surface mass-loss rate is then given by

$\dot{\Sigma}_{\mathrm{diffuse}}(R)=2n_{0}(R)u_{l}(R)\mu m_{H}\\\
\mathrm{for}\ R\geq 0.1R_{g}\,,$ (7)

where the density at the base of the flow is

$n_{0}(R)=C_{1}\left(\frac{3\Phi_{\mathrm{diff}}}{4\pi\alpha_{B}R_{g}^{3}}\right)^{1/2}\left(\frac{2}{(R/R_{g})^{15/2}+(R/R_{g})^{25/2}}\right)^{1/5}\,,$
(8)

the wind launch velocity

$u_{l}(R)=c_{s}A\exp{\left[B\left(\frac{R}{R_{g}}-0.1\right)\right]}\left(\frac{R}{R_{g}}-0.1\right)^{D}\,,$
(9)

$\mu=1.35$ the mean molecular weight of the ionized gas, $m_{H}$ the mass of a
hydrogen atom, $C_{1}\simeq 0.14$, $R_{g}$ the gravitational radius,
$\alpha_{B}=2.6\cdot 10^{-13}$ is the Case B recombination coefficient for
atomic hydrogen at $10^{4}$ K, $c_{s}=10$ km $\mathrm{s}^{-1}$ the sound speed
of the ionized gas, $A=0.3423$, $B=0.3612$, $D=0.2457$, and the stellar
diffuse ionizing EUV flux

$\Phi_{\mathrm{diff}}=\begin{cases}\Phi_{\mathrm{EUV}}\left(\frac{R_{\mathrm{thin}}}{R_{\mathrm{in}}}\right)&\text{if
}R_{\mathrm{thin}}<R_{\mathrm{crit}},\\\
\Phi_{\mathrm{EUV}}&\text{otherwise},\end{cases}$ (10)

where $\Phi_{\mathrm{EUV}}$ is the unattenuated stellar ionizing EUV flux (in
photons s-1), $R_{\mathrm{thin}}$ is the radius at which the disc becomes
optically thin in the vertical direction

$\Sigma_{g}(R_{\mathrm{thin}})=m_{H}\sigma_{\mathrm{13.6\,eV}}^{-1}\,,$ (11)

$\sigma_{\mathrm{13.6\,eV}}=6.3\cdot 10^{-18}$ cm2 is the absorption cross-
section for ionizing photons, $R_{\mathrm{crit}}$ is the critical radius at
which the gap opens

$R_{\mathrm{crit}}=1.4\left(\frac{M_{\star}}{M_{\odot}}\right)\ \text{au}\,.$
(12)

The direct component of the EUV surface mass-loss rate (defined only for
$R>R_{\mathrm{in}}$) is given by

$\dot{\Sigma}_{\mathrm{direct}}(R,t)=2C_{2}\mu
m_{H}c_{s}\left[\frac{\Phi_{\mathrm{EUV}}}{4\pi\alpha_{B}(H/R)R_{\mathrm{in}}^{3}(t)}\right]^{1/2}\left[\frac{R}{R_{\mathrm{in}}(t)}\right]^{-a}\,,$
(13)

where $C_{2}=0.235$, $a=2.42$, $H/R$ is the disc aspect ratio.

###  2.3 FUV photoevaporation

The combined X-ray/FUV component of the surface mass-loss rate has been
defined in eq. A1 of Komaki et al. (2021) with coefficients from their Table 2
(as a function of stellar mass) and their Table 3 (as a function of X-ray/FUV
luminosities). However, since in their prescription the FUV contribution is
significantly more important than the X-ray one, we assume here a fixed X-ray
luminosity and consider only the variation of the FUV component. To simplify
the implementation we considered here only the coefficients for a 1 Solar mass
star with varying FUV luminosities, and scale then the total mass-loss rate as
a function of stellar mass by (Komaki et al., 2021)

$\dot{M}_{\mathrm{FUV}}\propto\left(\frac{M_{\star}}{M_{\odot}}\right)^{2.06}\,.$
(14)

###  2.4 Population synthesis

We assume an initial stellar mass function following Kroupa (2001),
$\xi(m)\propto m^{-\alpha}$ , where $\alpha=1.3\pm 0.5$ for $0.08\leq
m/M_{\odot}<0.5$ and $\alpha=2.3\pm 0.3$ for $0.5\leq m/M_{\odot}\leq 1$, from
which we obtain the distribution shown in Figure 1 (a) for a sample of 10,000
stars with a median value of $\sim 0.3$ M⊙. The population of observed low
accretors from T23 is overplotted in orange, where one can see that the
distribution is significantly different from the adopted one due to the low
number statistics (24 sources), but the mean of the distribution ($0.4$ M⊙,
shown with a black dashed line) is consistent with the adopted sample.

Figure 3: Histogram of the accretion rate density distribution in the EUV
(blue), X-ray (orange), and FUV (green) population synthesis. The KDE is
overplotted with a solid line for each distribution, and the median values are
plotted with dotted-dashed lines. For direct comparison the median accretion
rate of the low-accretors population is plotted with a black dotted-dashed
line. The distribution of accretion rates from the sample of Manara et al.
(2023) is added with a black histogram in the full sample for comparison.

Güdel et al. (2007) derived an observational relation between the median X-ray
luminosities and stellar masses

$\log_{10}(L_{X})=(1.54\pm 0.12)\log_{10}(M_{\star})+(30.31\mp 0.06)\,,$ (15)

though a large spread is observed around the mean values, which becomes larger
for small mass stars (e.g. Getman et al., 2022). Kuhn & Hillenbrand (2019)
took a subsample of the Chandra Orion Ultradeep Project (COUP, cf. Getman et
al., 2005) and stratified it in three stellar mass bins using the Baraffe et
al. (1998) evolutionary models. From this sample one can derive an X-ray
luminosity function (XLF) as a function of stellar mass. We then calculated
the median stellar mass for the three stellar mass bins given the adopted IMF,
and shifted the XLF distribution to match the given value of the stellar mass.
We then sampled the X-ray luminosity given the probability density corrected
for the stellar mass and obtained the X-ray luminosity distribution shown in
Figure 1(b) from the 10,000 sampled stellar masses, with a median value of
$10^{29.4}$ erg s-1 and a spread over four orders of magnitude.

The EUV rates are shown to scale with the ratio of incoming ionising flux.
Assuming a chromospheric origins of the EUV flux, we can then adopt the same
scaling relation as eq. 15

$\log_{10}(\Phi_{EUV})=1.54\log_{10}(M_{\star})+42\,$ (16)

and consider a small dispersion around the mean value for each stellar mass of
0.25 dex, as shown in Figure 1 (c), which gives ionizing fluxes ranging from
$10^{40}\,\mathrm{s^{-1}}$ to $10^{42.5}\,\mathrm{s^{-1}}$ with a median of
$10^{41.2}\,\mathrm{s^{-1}}$.

Contributions to the FUV luminosity ($L_{\mathrm{FUV}}$) are believed to come
both from the activity in the chromosphere ($L_{\mathrm{FUV,chr}}$) and
accretion hotspots on the stellar surface (see e.g. Gorti et al., 2009,
$L_{\mathrm{FUV,acc}}$). The accretion component, that is more important in
the early stages of evolution, can be expressed as

$L_{\mathrm{FUV,acc}}=10^{-2}\left(\frac{M_{\star}}{M_{\odot}}\right)\left(\frac{R_{\star}}{R_{\odot}}\right)^{-1}\left(\frac{\dot{M}_{\mathrm{acc}}}{10^{-8}\
\mathrm{M}_{\odot}\mathrm{yr}^{-1}}\right)\ \mathrm{L}_{\odot}\,,$ (17)

assuming the accretion luminosity as a black-body with $T=9000$ K which has a
fraction of $4\%$ in the FUV band (Gorti et al., 2009). The chromospheric
component of the FUV flux is given by

$L_{\mathrm{FUV,chr}}=10^{-3.3}L_{\star}\,,$ (18)

obtained for non-accreting, weak-line T Tauri stars (Valenti et al., 2003).

We constrained the disc properties in order to match the observed mean disc
lifetime of 2-3 Myr (see e.g. Ribas et al., 2014). For the EUV profile we
sampled the viscous $\alpha$-parameter and scaling radius $R_{1}$ for disc
masses ranging from $0.01$–$0.1M_{\star}$ for a typical star with median
values from our distribution ($M_{\star}=0.3M_{\odot}$,
$\Phi_{\mathrm{EUV}}=10^{41.2}$ s-1) and then we selected those returning a
disc life-time in agreement with observations and obtained a best linear fit
given by:

$R_{1}=60.4\log_{10}({\alpha})+3009.7M_{d}[M_{\star}]+226.6\\\ \text{[au]}\,.$
(19)

We then sampled the whole stellar mass range and obtained the full sampling of
the parameter space. For the FUV profile, we did the same procedure, finding a
new best fit:

$\alpha=10^{-9.41+1.678\log_{10}(R_{1})-1.211\log_{10}(M_{d}[M_{\star}])}\,.$
(20)

For the X-ray profile, the disc evolution is primarily driven by the internal
photoevaporation rather than the disc properties, thus we sample uniformly the
parameter space fixing only the disc mass to $0.1M_{\star}$, which is
reasonable for non self-gravitating discs. We summarize the probed parameter
space in Table 1.

Table 1: Parameters for the population synthesis calculations. Name | Viscosity | $R_{1}$ | Disc mass | Stellar mass | Stellar flux
---|---|---|---|---|---
| $\log_{10}(\alpha)$ | au | $M_{\star}$ | $M_{\odot}$ | $(\Phi,\ L_{X})$
EUV | eq. 19 | eq. 19 | eq. 19 | Fig. 1 (a) | Fig. 1 (c)
X | [-4, -2] | [10, 100] | 0.1 | Fig. 1 (a) | Fig. 1 (b)
FUV | eq. 20 | eq. 20 | eq. 20 | Fig. 1 (a) | variable

##  3 Results

Figure 2 shows the accretion rates as a function of time for a population
synthesis of 10,000 discs sampled as described in Section 2. Overplotted with
dots of variable size (based on their stellar mass) is the population of low
accretors from T23, and the observational limit of the He I $\lambda 10830$
marked with a black dashed line at $10^{-11}$ M⊙ yr-1. From the full sample,
shown in the first column, one can immediately see that while the population
of discs with the X-ray profile (second row) catches all the observed data
points in the region with high density ($>10^{-2}$), the populations using the
EUV and FUV photoevaporation profiles (first and last row) cannot explain the
data for the older star-forming regions (Orion OB1a and Upper Sco).
Furthermore the observational data points lie in the upper region of the
distribution, even though they should be a sample of the population accreting
at the lowest possible rates. This means that the bulk of the discs in the
studied star forming regions covers a region not explained by the EUV or FUV
photoevaporation profiles.

Low-mass stars (small dots) cover the lower part of the high density
distribution while higher-mass stars the top part. This is expected from the
observationally derived relation between accretion rate and stellar masses,
that shows a sharp increase of the accretion rate as a function of stellar
mass ($\dot{M}$-$M_{*}$) with a broken power law (e.g. Alcalá et al., 2017).
Ercolano et al. (2014) proposed that the $\dot{M}$-$M_{*}$ distribution is
also a consequence of discs being dispersed by X-ray photoevaporation, which
fits well in this overall picture.

In Figure 3 we plot the histogram of the accretion rate distribution for the
EUV (in blue) and X-ray (in orange) populations. Overplotted are the median
accretion rates in dotted-dashed blue and orange lines respectively, and the
median accretion rate for the observed population of low-accretors with a
dotted-dashed black line. From this one can directly visualise how the median
of the X-ray photoevaporating population and the observed low-accretors is
very similar. On the other hand, for the population dispersing via EUV-
photoevaporation the median accretion rate of the low-accretors population is
close to the high-accretor wing of the EUV population, which is in tension
with the observation that the observed objects should represent the lowest end
of the mass accretion rate distribution.

Overplotted in Figure 3 (black hystogram) is the observed distribution of
accretion rates from the sample of Manara et al. (2023) recently reported by
Alexander et al. (2023). Our results show that the observations favour X-ray
photoevaporation as the main dispersal mechanism over other models, as it
represents well the low-accretor population.

We finally compared the distribution of disc fractions as a function of age,
calculated as the time at which the accretion rate drops below the
observational limit quoted by T23 ($10^{-11}$ M⊙ yr-1) in our population
synthesis with the observed distribution of disc fraction (Figure 4, black
lines). The EUV and X-ray distributions fit the observational data points
perfectly by construction, as we choose the parameter space in order to fit
them for the median stellar mass and EUV ionising field. The FUV distribution
fits less well the observed population as the stellar luminosity (and thus the
wind mass-loss rate) evolves with time (see eq. 17) inducing a stronger
stellar mass dependance. The main difference between the models is the
parameter space adopted to match the observations which is much more limited
for the EUV and FUV profiles with respect to the X-ray one (see Table. 1).

###  3.1 Mass dependent results

Figure 4: Disc fraction as a function of disc lifetime for the EUV (top
panel), X-ray (middle panel) and FUV (bottom panel) synthetic populations
compared with the observational data from Mamajek (2009), divided in three
stellar mass bins. The median disc life-time increases with stellar mass for
the EUV and FUV models, while it decreases for the X-ray models.

The results shown in the previous section assume a well-sampled IMF, which
implies that objects at the lower end of the mass range are the most abundant.
However the sample of low accretors from T23 includes objects with masses
ranging between $0.1$ and $1.39$ M⊙ and a mean of $0.4$ M⊙, resulting in a
slightly different stellar mass function with respect to the adopted IMF (see
Figure 1, a). Despite the low number of objects in observational sample it is
worth trying to decouple the effect of stellar mass from the analysis. To this
aim we repeat the analysis for separate mass bins, as shown in columns 2 to 4
of Figures 2 and 3. The observed median of the observed accretion rate
distribution is always close the median or the lower end of distribution
predicted by the X-ray model. For the EUV and FUV distributions, in contrast,
the median is always close to the higher end of the predicted distribution,
for all mass bins, implying that the EUV and FUV models predict that objects
with accretion rates one or two order of magnitude lower than observed should
be more common.

Finally, in Figure 4 we explore the effect of stellar mass on the disc
lifetimes. In the top panel the population with the X-ray profile profile
shows little variation as a function of stellar mass, with a trend of
decreasing lifetimes for increasing stellar masses, which is consistent with
current observations (Ribas et al., 2015). In the bottom panel, the population
with the EUV profile shows a much stronger dependence on the stellar mass,
with an inverse trend of decreasing disc lifetime for smaller mass stars. The
overall distribution in this case fits the observational data because of the
adopted IMF, but it would overpredict the disc fractions for the stellar mass
distribution studied in T23.

##  4 Conclusions

We conducted a population synthesis study of viscously evolving discs
subjected to different photoevaporation prescriptions, in order to test these
models against the recently published observations of the lowest accretion
rates measured by T23. For the case of X-ray photoevaporation the probability
of finding an object at a given accretion rate changes as a function of age of
the population. However for objects older than approximately 1 Myr it is
clearly not improbable to find objects at rates of order
$10^{-10}M_{\odot}/yr$. In particular for objects older than about 5 Myr the
probability distribution peaks indeed at these values. For lower accretion
rates the probabilty decreases sharply for all ages, indicating that the
lowest accretors of a population of discs being dissipated by X-ray
photoevaporation is indeed expected to be observed accreting at rates of order
$10^{-10}M_{\odot}/yr$.

Our findings can be synthesised as follows:

  * •

EUV, FUV and X-ray photoevaporation predict objects with accretion rates as
those observed in the low-accretor sample of T23.

  * •

However, the low-accretors are part of the bulk or lower end of the
distribution predicted by X-ray photoevaporation, while they fall in the upper
end of the EUV and FUV driven populations, which thus would predict an
overabundance of objects accreting at significantly lower rates, which is not
observed.

  * •

The constraints required by EUV and FUV internal photoevaporation to explain
the observed disk lifetime are considerably more stringent than those of
X-ray-driven disc evolution (see eq. 19).

  * •

The relationship between disk fraction and stellar mass exhibits a strong
dependence for EUV and in particular for FUV profiles, in contradiction with
the observed low-accretor population that shows similar accretion rates across
a wide range of stellar masses.

  * •

The observed distribution of accretion rates favours X-ray photoevaporation as
the main dispersal mechanism.

In light of the results of the population synthesis models shown here, we
conclude that the recent low-accretor observations point to X-ray
photoevaporation as driving the final stages of disc dispersal.

## Acknowledgements

We thank the anonymous referee for a constructive report. We acknowledge
support of the DFG (German Research Foundation), Research Unit “Transition
discs” - 325594231 and of the Excellence Cluster ORIGINS - EXC-2094 -
390783311. KM was supported by NASA Chandra grants GO8-19015X, TM9-20001X,
GO7-18017X, and HST-GO-15326.

## Data Availability

The data for the population synthesis calculations is available at
https://github.com/GiovanniPicogna/low-accretors

## References

  * Alcalá et al. (2017) Alcalá J. M., et al., 2017, A&A, 600, A20
  * Alexander & Armitage (2007) Alexander R. D., Armitage P. J., 2007, MNRAS, 375, 500
  * Alexander & Pascucci (2012) Alexander R. D., Pascucci I., 2012, MNRAS, 422, L82
  * Alexander et al. (2006) Alexander R. D., Clarke C. J., Pringle J. E., 2006, MNRAS, 369, 229
  * Alexander et al. (2023) Alexander R., Rosotti G., Armitage P. J., Herczeg G. J., Manara C. F., Tabone B., 2023, MNRAS, 524, 3948
  * Baraffe et al. (1998) Baraffe I., Chabrier G., Allard F., Hauschildt P. H., 1998, A&A, 337, 403
  * Carrera et al. (2017) Carrera D., Gorti U., Johansen A., Davies M. B., 2017, ApJ, 839, 16
  * Ercolano & Owen (2016) Ercolano B., Owen J. E., 2016, MNRAS, 460, 3472
  * Ercolano & Pascucci (2017) Ercolano B., Pascucci I., 2017, Royal Society Open Science, 4, 170114
  * Ercolano & Picogna (2022) Ercolano B., Picogna G., 2022, European Physical Journal Plus, 137, 1357
  * Ercolano & Rosotti (2015) Ercolano B., Rosotti G., 2015, MNRAS, 450, 3008
  * Ercolano et al. (2014) Ercolano B., Mayr D., Owen J. E., Rosotti G., Manara C. F., 2014, MNRAS, 439, 256
  * Ercolano et al. (2017a) Ercolano B., Rosotti G. P., Picogna G., Testi L., 2017a, MNRAS, 464, L95
  * Ercolano et al. (2017b) Ercolano B., Jennings J., Rosotti G., Birnstiel T., 2017b, MNRAS, 472, 4117
  * Ercolano et al. (2021) Ercolano B., Picogna G., Monsch K., Drake J. J., Preibisch T., 2021, MNRAS, 508, 1675
  * Getman et al. (2005) Getman K. V., et al., 2005, ApJS, 160, 319
  * Getman et al. (2022) Getman K. V., Feigelson E. D., Garmire G. P., Broos P. S., Kuhn M. A., Preibisch T., Airapetian V. S., 2022, ApJ, 935, 43
  * Gorti et al. (2009) Gorti U., Dullemond C. P., Hollenbach D., 2009, ApJ, 705, 1237
  * Güdel et al. (2007) Güdel M., et al., 2007, A&A, 468, 353
  * Jennings et al. (2018) Jennings J., Ercolano B., Rosotti G. P., 2018, MNRAS, 477, 4131
  * Komaki et al. (2021) Komaki A., Nakatani R., Yoshida N., 2021, ApJ, 910, 51
  * Kroupa (2001) Kroupa P., 2001, MNRAS, 322, 231
  * Kuhn & Hillenbrand (2019) Kuhn M. A., Hillenbrand L. A., 2019, ApJ, 883, 117
  * Lesur et al. (2022) Lesur G., et al., 2022, arXiv e-prints, p. arXiv:2203.09821
  * Lynden-Bell & Pringle (1974) Lynden-Bell D., Pringle J. E., 1974, MNRAS, 168, 603
  * Mamajek (2009) Mamajek E. E., 2009, in Usuda T., Tamura M., Ishii M., eds, American Institute of Physics Conference Series Vol. 1158, Exoplanets and Disks: Their Formation and Diversity. pp 3–10 (arXiv:0906.5011), doi:10.1063/1.3215910
  * Manara et al. (2023) Manara C. F., Ansdell M., Rosotti G. P., Hughes A. M., Armitage P. J., Lodato G., Williams J. P., 2023, in Inutsuka S., Aikawa Y., Muto T., Tomida K., Tamura M., eds, Astronomical Society of the Pacific Conference Series Vol. 534, Astronomical Society of the Pacific Conference Series. p. 539 (arXiv:2203.09930), doi:10.48550/arXiv.2203.09930
  * Monsch et al. (2019) Monsch K., Ercolano B., Picogna G., Preibisch T., Rau M. M., 2019, MNRAS, 483, 3448
  * Pascucci et al. (2022) Pascucci I., Cabrit S., Edwards S., Gorti U., Gressel O., Suzuki T., 2022, arXiv e-prints, p. arXiv:2203.10068
  * Picogna et al. (2019) Picogna G., Ercolano B., Owen J. E., Weber M. L., 2019, MNRAS, 487, 691
  * Picogna et al. (2021) Picogna G., Ercolano B., Espaillat C. C., 2021, MNRAS, 508, 3611
  * Ribas et al. (2014) Ribas Á., Merín B., Bouy H., Maud L. T., 2014, A&A, 561, A54
  * Ribas et al. (2015) Ribas Á., Bouy H., Merín B., 2015, A&A, 576, A52
  * Thanathibodee et al. (2022) Thanathibodee T., Calvet N., Hernández J., Maucó K., Briceño C., 2022, AJ, 163, 74
  * Thanathibodee et al. (2023) Thanathibodee T., Molina B., Serna J., Calvet N., Hernández J., Muzerolle J., Franco-Hernández R., 2023, ApJ, 944, 90
  * Valenti et al. (2003) Valenti J. A., Fallon A. A., Johns-Krull C. M., 2003, VizieR Online Data Catalog, p. J/ApJS/147/305
  * Weber et al. (2020) Weber M. L., Ercolano B., Picogna G., Hartmann L., Rodenkirch P. J., 2020, MNRAS, 496, 223


###### Abstract

A graph $G$ has the Perfect-Matching-Hamiltonian property (PMH-property) if
for each one of its perfect matchings, there is another perfect matching of
$G$ such that the union of the two perfect matchings yields a Hamiltonian
cycle of $G$. The study of graphs that have the PMH-property, initiated in the
1970s by Las Vergnas and Häggkvist, combines three well-studied properties of
graphs, namely matchings, Hamiltonicity and edge-colourings. In this work, we
study these concepts for cubic graphs in an attempt to characterise those
cubic graphs for which every perfect matching corresponds to one of the
colours of a proper 3-edge-colouring of the graph. We discuss that this is
equivalent to saying that such graphs are even-2-factorable (E2F), that is,
all 2-factors of the graph contain only even cycles. The case for bipartite
cubic graphs is trivial, since if $G$ is bipartite then it is E2F. Thus, we
restrict our attention to non-bipartite cubic graphs. A sufficient, but not
necessary, condition for a cubic graph to be E2F is that it has the PMH-
property. The aim of this work is to introduce an infinite family of E2F non-
bipartite cubic graphs on two parameters, which we coin _papillon graphs_ ,
and determine the values of the respective parameters for which these graphs
have the PMH-property or are just E2F. We also show that no two papillon
graphs with different parameters are isomorphic.

###### keywords:

Cubic graph, perfect matching, Hamiltonian cycle, 3-edge-colouring

Perfect matchings, Hamiltonian cycles and edge-colourings in a class of cubic
graphs

Marién Abreu Dipartimento di Matematica, Informatica ed Economia
Università degli Studi della Basilicata, Italy<EMAIL_ADDRESS>
John Baptist Gauci Department of Mathematics, University of Malta, Malta john-
<EMAIL_ADDRESS>
Domenico<EMAIL_ADDRESS><EMAIL_ADDRESS>Dipartimento di Matematica,
Informatica ed Economia
Università degli Studi della Basilicata, Italy

Jean Paul Zerafa Department of Technology and Entrepreneurship Education
University of Malta, Malta;
Department of Computer Science, Faculty of Mathematics, Physics and
Informatics
Comenius University, Mlynská Dolina, 842 48 Bratislava, Slovakia
<EMAIL_ADDRESS>The author was partially supported by VEGA 1/0813/18 and
VEGA 1/0743/21.

05C15, 05C45, 05C70

##  1 Introduction

Let $G$ be a simple connected graph of even order with vertex set $V(G)$ and
edge set $E(G)$. A _$k$ -factor_ of $G$ is a $k$-regular spanning subgraph of
$G$ (not necessarily connected). Two very well-studied concepts in graph
theory are _perfect matchings_ and _Hamiltonian cycles_ , where the former is
the edge set of a $1$-factor and the latter is a connected $2$-factor of a
graph. For $t\geq 3$, a _cycle_ of length $t$ (or a $t$-cycle), denoted by
$C_{t}=(v_{1},\ldots,v_{t})$, is a sequence of mutually distinct vertices
$v_{1},v_{2},\ldots,v_{t}$ with corresponding edge set
$\\{v_{1}v_{2},\ldots,v_{t-1}v_{t},v_{t}v_{1}\\}$. For definitions not
explicitly stated here we refer the reader to [4]. A graph $G$ admitting a
perfect matching is said to have the _Perfect-Matching-Hamiltonian property_
(for short the _PMH-property_) if for every perfect matching $M$ of $G$ there
exists another perfect matching $N$ of $G$ such that the edges of $M\cup N$
induce a Hamiltonian cycle of $G$. For simplicity, a graph admitting this
property is said to be PMH. This property was first studied in the 1970s by
Las Vergnas [14] and Häggkvist [9], and for more recent results about the PMH-
property we suggest the reader to [1, 2, 3, 7, 8]. In [3], a property stronger
than the PMH-property is studied: the Pairing-Hamiltonian property, for short
the PH-property. Before proceeding to the definition of this property, we
first define what a pairing is. For any graph $G$, $K_{G}$ denotes the
complete graph on the same vertex set $V(G)$ of $G$. A perfect matching of
$K_{G}$ is said to be a _pairing_ of $G$, and a graph $G$ is said to have the
_Pairing-Hamiltonian property_ if every pairing $M$ of $G$ can be extended to
a Hamiltonian cycle $H$ of $K_{G}$ such that $E(H)-M\subseteq E(G)$. Clearly,
a graph having the PH-property is also PMH, although the converse is not
necessarily true. Amongst other results, the authors of [3] show that the only
cubic graphs admitting the PH-property are the complete graph $K_{4}$, the
complete bipartite graph $K_{3,3}$, and the cube $\mathcal{Q}_{3}$. However,
this does not mean that these are the only three cubic graphs admitting the
PMH-property. For instance, all cubic 2-factor Hamiltonian graphs (all
2-factors of such a graph form a Hamiltonian cycle) are PMH (see for example
[5, 6, 11, 12, 13]).

If a cubic graph $G$ is PMH, then every perfect matching of $G$ corresponds to
one of the colours of a (proper) $3$-edge-colouring of the graph, and we say
that every perfect matching can be extended to a $3$-edge-colouring. This is
achieved by alternately colouring the edges of the Hamiltonian cycle
containing a predetermined perfect matching using two colours, and then
colouring the edges not belonging to the Hamiltonian cycle using a third
colour. However, there are cubic graphs which are not PMH but have every one
of their perfect matchings that can be extended to a $3$-edge-colouring (see
for example Figure 1). The following proposition characterises all cubic
graphs for which every one of their perfect matchings can be extended to a
3-edge-colouring of the graph.

Figure 1: The bold dashed edges can be extended to a proper 3-edge-colouring
but not to a Hamiltonian cycle

######  Proposition 1.1.

Let $G$ be a cubic graph admitting a perfect matching. Every perfect matching
of $G$ can be extended to a $3$-edge-colouring of $G$ if and only if all
$2$-factors of $G$ contain only even cycles.

######  Proof 1.2.

Let $F$ be a $2$-factor of $G$, and let $M$ be the perfect matching
$E(G)-E(F)$. Since $M$ can be extended to a 3-edge-colouring of $G$, $F$ can
be 2-edge-coloured, and hence $F$ does not contain any odd cycles. Conversely,
let $M^{\prime}$ be a perfect matching of $G$, and let $F^{\prime}$ be its
complementary 2-factor, that is, $E(F^{\prime})=E(G)-M^{\prime}$. Since
$F^{\prime}$ contains only even cycles, $M^{\prime}$ can be extended to a
$3$-edge-colouring, by assigning a first colour to all of its edges and then
alternately colouring the edges of the 2-factor $F^{\prime}$ using another two
colours.

We shall call graphs in which all $2$-factors consist only of even cycles as
_even- $2$-factorable_ graphs, denoted by E2F for short. In particular, from
Proposition 1.1, if a cubic graph $G$ has the PMH-property, then it is also
E2F. As in the proof of Proposition 1.1, in the sequel, given a perfect
matching $M$ of a cubic graph $G$, the 2-factor obtained after deleting the
edges of $M$ from $G$ is referred to as the _complementary 2-factor_ of $M$.

If a cubic graph is bipartite, then trivially, each of its perfect matchings
can be extended to a $3$-edge-colouring, since it is E2F. But what about non-
bipartite cubic graphs? In Table 1, we give the number of non-isomorphic non-
bipartite 3-connected cubic graphs (having girth at least $4$) such that each
one of their perfect matchings can be extended to a $3$-edge-colouring. As is
the case of _snarks_ (bridgeless cubic graphs which are not $3$-edge-
colourable), these seem to be difficult to find, as one can notice after
comparing these numbers to the total number of non-isomorphic $3$-edge-
colourable (Class I) non-bipartite $3$-connected cubic graphs having girth at
least $4$, also given in Table 1. The numbers shown in this table were
obtained thanks to a computer check done by Jan Goedgebeur, and the data is
sorted according to the cyclic connectivity of the graphs considered. We
remark that E2F cubic graphs having girth $3$ can be obtained by applying a
star product between an E2F cubic graph of smaller order and the complete
graph $K_{4}$—this has been investigated further by the last two authors in
[15]. This is the reason why only graphs having girth at least 4 are
considered in this work. More results on star products (also known in the
literature as $3$-cut connections) in cubic graphs can be found in [5, 6, 10,
11, 12, 13].

|  | Cyclic connectivity |  | Total no. of graphs |  |
---|---|---|---|---|---|---
|  | $3$ | $4$ | $5$ | $6$ |  | E2F | Class I |  ratio E2F : Class I |
Number of vertices | $8$ | / | $1$ | / | / |  | $1$ | $1$ | $100\%$ |
$10$ | / | / | / | / |  | $0$ | $3$ | $0\%$ |
$12$ | $2$ | $5$ | $2$ | / |  | $9$ | $17$ | $52.94\%$ |
$14$ | $2$ | $2$ | $2$ | / |  | $6$ | $92$ | $6.52\%$ |
$16$ | $35$ | $56$ | $4$ | / |  | $95$ | $716$ | $13.27\%$ |
$18$ | $84$ | $21$ | $9$ | / |  | $114$ | $7343$ | $1.55\%$ |
$20$ | $926$ | $655$ | $15$ | $2$ |  | $1598$ | $93946$ | $1.70\%$ |
$22$ | $2978$ | $331$ | $17$ | $6$ |  | $3332$ | $1400203$ | $0.24\%$ |
Table 1: The number of non-isomorphic non-bipartite $3$-connected cubic graphs
with girth at least $4$ which are E2F and Class I

A complete characterisation of which cubic graphs are PMH is still elusive, so
considering the Class I non-bipartite cubic graphs having the property that
each one of their perfect matchings can be extended to a $3$-edge-colouring
may look presumptuous. As far as we know this property and the corresponding
characterisation problem were never considered before and tackling the
following problem seems a reasonable step to take.

######  Problem 1.3.

Characterise the Class I non-bipartite cubic graphs for which each one of
their perfect matchings can be extended to a $3$-edge-colouring, that is, are
E2F.

We remark that although the PMH-property is an appealing property in its own
right, Problem 1.3 continues to justify its study in relation to cubic graphs.
Observe that in the family of cubic graphs, whilst snarks are not $3$-edge-
colourable, even-$2$-factorable graphs are quite the opposite being “very much
3-edge-colourable", since the latter can be 3-edge-coloured by assigning a
colour to one of its perfect matchings, and then alternately colour the edges
of the complementary 2-factor.

###  1.1 Cycle permutation graphs

Consider two disjoint cycles each of length $t$, referred to as the first and
second $t$-cycles and denoted by $(x_{1},\ldots,x_{t})$ and
$(y_{1},\ldots,y_{t})$, respectively. Let $\sigma$ be a permutation of the
symmetric group $\mathcal{S}_{t}$ on the $t$ symbols $\\{1,\ldots,t\\}$. The
_cycle permutation graph corresponding to $\sigma$_ is the cubic graph
obtained by considering the first and second $t$-cycles in which $x_{i}$ is
adjacent to $y_{\sigma(i)}$, where $\sigma(i)$ is the image of $i$ under the
permutation $\sigma$.

Figure 2: Two different drawings of the smallest non-bipartite E2F cubic graph

The smallest non-bipartite cubic graph (from Table 1) which is E2F is in fact
a cycle permutation graph corresponding to
$\sigma=(1\,\,\,2)\in\mathcal{S}_{4}$, where
$\sigma(1)=2,\sigma(2)=1,\sigma(3)=3$, and $\sigma(4)=4$ (see Figure 2). This
shows that the edges between the vertices of the first and second $4$-cycles
of the cycle permutation graph are
$x_{1}y_{2},x_{2}y_{1},x_{3}y_{3},x_{4}y_{4}$. In what follows we shall denote
permutations in cycle notation and, for simplicity, fixed points shall be
suppressed. With the help of Wolfram Mathematica, in Table 2 we provide the
number of non-isomorphic non-bipartite cycle permutation graphs up to 20
vertices which are PMH or just E2F. Recall that PMH cubic graphs are also E2F,
and so, PMH cycle permutation graphs should be searched for from amongst the
cycle permutation graphs which are E2F. We also remark that, in the sequel,
cycle permutation graphs with total number of vertices equal to twice an odd
number are not considered because, in this case, the first and second cycles
form a 2-factor consisting of two odd cycles, and so they are trivially not
E2F.

|  | E2F | PMH
---|---|---|---
No. of vertices | $8$ | $1$ | $0$
$12$ | $5$ | $1$
$16$ | $28$ | $2$
$20$ | $175$ | $0$
Table 2: The number of non-isomorphic non-bipartite cycle permutation graphs
with girth at least 4 which are E2F and PMH

This work is a first structured attempt at tackling Problem 1.3. We give an
infinite family of non-bipartite cycle permutation graphs which admit the PMH-
property or are just E2F. In Section 2, we generalise the smallest cubic graph
which is E2F into a family of non-bipartite cycle permutation graphs, namely
papillon graphs $\mathcal{P}_{r,\ell}$ (for $r,\ell\in\mathbb{N}$), whose
smallest member $\mathcal{P}_{1,1}$ is, in fact, the graph in Figure 2. We
show that papillon graphs are E2F for all values of $r$ and $\ell$ (Theorem
2.3) and PMH if and only if both $r$ and $\ell$ are even (Theorem 3.11 and
Theorem 3.13).

##  2 Papillon graphs

Let $[n]=\\{1,\ldots,n\\}$, for some positive integer $n$.

######  Definition 2.1.

Let $r$ and $\ell$ be two positive integers. The _papillon graph_
$\mathcal{P}_{r,\ell}$ is the graph on $4r+4\ell$ vertices such that
$V(\mathcal{P}_{r,\ell})=\\{u_{i},v_{i}:i\in[2r+2\ell]\\}$, where:

  1. (i)

$(u_{1},u_{2},\ldots,u_{2r+2\ell})$ is a cycle of length $2r+2\ell$;

  2. (ii)

$u_{i}$ is adjacent to $v_{i}$, for each $i\in[2r+2\ell]$; and

  3. (iii)

the adjacencies between the vertices $v_{i}$, for $i\in[2r+2\ell]$, form a
cycle of length $2r+2\ell$ given by the edge set

$\displaystyle\\{v_{2i-1}v_{2i}:i\in[r+\ell]\\}$
$\displaystyle\cup\\{v_{2i-1}v_{2i+2}:i\in[r+\ell-1]\setminus\\{s\\}\\}$
$\displaystyle\cup\\{v_{2}v_{2s+2},v_{2s-1}v_{2r+2\ell-1}\\},$

where $s=\min\\{r,\ell\\}$.

Clearly, the two papillon graphs $\mathcal{P}_{r,\ell}$ and
$\mathcal{P}_{\ell,r}$ are isomorphic, and henceforth, without loss of
generality, we shall tacitly assume that $r\leq\ell$. The papillon graph
$\mathcal{P}_{r,\ell}$ for $r\geq 2$ is depicted in Figure 3. When $r$ and
$\ell$ are equal, say $r=\ell=n$, the papillon graph $\mathcal{P}_{r,\ell}$ is
said to be _balanced_ , and simply denoted by $\mathcal{P}_{n}$ (see, for
example, Figure 4). Otherwise, $\mathcal{P}_{r,\ell}$ is said to be
_unbalanced_ (see, for example, Figure 11). The $(2r+2\ell)$-cycle induced by
the sets of vertices $\\{u_{i}:i\in[2r+2\ell]\\}$ is referred to as the
_outer-cycle_ , whilst the $(2r+2\ell)$-cycle induced by the vertices
$\\{v_{i}:i\in[2r+2\ell]\\}$ is referred to as the _inner-cycle_. The edges on
these two $(2r+2\ell)$-cycles are said to be the _outer-edges_ and _inner-
edges_ accordingly, whilst the edges $u_{i}v_{i}$ are referred to as _spokes_.
The edges $u_{1}u_{2r+2\ell}$, $v_{2r-1}v_{2r+2\ell-1}$, $v_{2}v_{2r+2}$,
$u_{2r}u_{2r+1}$ are denoted by $a,b,c,d$, respectively, and we shall also
denote the set $\\{a,b,c,d\\}$ by $\mathcal{X}$. The set $\mathcal{X}$ is
referred to as the _principal 4-edge-cut_ of $\mathcal{P}_{r,\ell}$.

Figure 3: The papillon graph $\mathcal{P}_{r,\ell}$, for $\ell\geq r\geq 2$,
and the $4$-pole $\mathcal{T}_{j}$, for $j\in[r+\ell]$

The graph in Figure 2 is actually the smallest (balanced) papillon graph
$\mathcal{P}_{1}$. In general, since $\\{u_{i}:i\in[2r+2\ell]\\}$ and
$\\{v_{i}:i\in[2r+2\ell]\\}$ induce two disjoint $(2r+2\ell)$-cycles in
$\mathcal{P}_{r,\ell}$, and since every vertex belonging to the outer-cycle is
adjacent to exactly one vertex on the inner-cycle, there exists an isomorphism
$\pi$ between the papillon graph $\mathcal{P}_{r,\ell}$ and a cycle
permutation graph corresponding to some $\sigma\in\mathcal{S}_{2r+2\ell}$
satisfying $\pi(x_{i})=u_{i}$ and $\pi(y_{i})=v_{\sigma^{-1}(i)}$, for each
$i\in[2r+2\ell]$. In fact, the papillon graph $\mathcal{P}_{r,\ell}$ is the
cycle permutation graph, with $(u_{1},\ldots,u_{2r+2\ell})$ as the first
cycle, corresponding to the permutation:

  * •

$\sigma_{1,\ell}:=(3\,\,\,4)\ldots(2\ell+1\,\,\,2\ell+2)$, with fixed points
$1$ and $2$, when $\ell\geq 1$;

  * •

$\sigma_{2,2}:=(1\,\,\,2)(3\,\,\,4)(5\,\,\,7)(6\,\,\,8)$;

  * •

$\sigma_{r,3}:=(1\,\,\,2)\ldots(2r-1\,\,\,2r)(2r+1\,\,\,2r+5)(2r+2\,\,\,2r+6)$,
with fixed points $2r+3$ and $2r+4$, when $r\in\\{2,3\\}$; and

  * •

$\sigma_{r,\ell}:=(1\,\,\,2)\ldots(2r-1\,\,\,2r)(2r+1\,\,\,2r+2\ell-1)(2r+2\,\,\,2r+2\ell)(2r+3\,\,\,2r+2\ell-3)(2r+4\,\,\,2r+2\ell-2)\ldots(\alpha\,\,\,\beta)$,
when $\ell\geq r\geq 4$, where $(\alpha\,\,\,\beta)=(2r+\ell\,\,\,2r+\ell+2)$
if $\ell$ is even, and $(\alpha\,\,\,\beta)=(2r+\ell-1\,\,\,2r+\ell+3)$ if
$\ell$ is odd.

We remark that when $r>1$, the above permutations has no fixed points when
$\ell$ is even, but, when $\ell$ is odd, $2r+\ell$ and $2r+\ell+1$ are fixed
points, and thus, in this case, $x_{2r+\ell}$ is adjacent to $y_{2r+\ell}$,
and $x_{2r+\ell+1}$ is adjacent to $y_{2r+\ell+1}$ in $\mathcal{P}_{r,\ell}$.
Note that since $\sigma_{r,\ell}$ is an involution for all positive integers
$r$ and $\ell$, the isomorphism $\pi$ mentioned above can be rewritten as
follows: $\pi(x_{i})=u_{i}$ and $\pi(y_{i})=v_{\sigma(i)}$, for each
$i\in[2r+2\ell]$. The papillon graph $\mathcal{P}_{r,\ell}$ admits a natural
automorphism $\psi$ which exchanges the two cycles, given by
$\psi(u_{i})=v_{\sigma_{r,\ell}(i)}$ and $\psi(v_{i})=u_{\sigma_{r,\ell}(i)}$,
for each $i\in[2r+2\ell]$. In fact, the function $\psi$ is clearly bijective.
Moreover, it maps edges of the outer-cycle to edges of the inner-cycle (and
vice-versa), and maps spokes to spokes, since the edges $u_{i}v_{i}$ are
mapped to $u_{\sigma_{r,\ell}(i)}v_{\sigma_{r,\ell}(i)}$.

Figure 4: The balanced papillon graph $\mathcal{P}_{3}$ on 24 vertices

Before proceeding, we introduce multipoles which generalise the notion of
graphs. This will become useful when describing papillon graphs. A _multipole_
$\mathcal{Z}$ consists of a set of vertices $V(\mathcal{Z})$ and a set of
generalised edges such that each generalised edge is either an edge in the
usual sense (that is, it has two endvertices) or a semiedge. A _semiedge_ is a
generalised edge having exactly one endvertex. The set of semiedges of
$\mathcal{Z}$ is denoted by $\partial\mathcal{Z}$ whilst the set of edges of
$\mathcal{Z}$ having two endvertices is denoted by $E(\mathcal{Z})$. Two
semiedges are _joined_ if they are both deleted and their endvertices are made
adjacent. A _$k$ -pole_ is a multipole with $k$ semiedges. A perfect matching
$M$ of a $k$-pole $\mathcal{Z}$ is a subset of generalised edges of
$\mathcal{Z}$ such that every vertex of $\mathcal{Z}$ is incident with exactly
one generalised edge of $M$. In what follows, we shall construct papillon
graphs by joining together semiedges of a number of multipoles. In this sense,
given a perfect matching $M$ of a graph $G$, and a multipole $\mathcal{Z}$
used as a building block to construct $G$, we shall say that $M$ contains a
semiedge $e$ of the multipole $\mathcal{Z}$, if $M$ contains the edge in $G$
obtained by joining $e$ to another semiedge in the process of constructing
$G$.

The $4$-pole $\mathcal{Z}$ with vertex set $\\{z_{1},z_{2},z_{3},z_{4}\\}$,
such that $E(\mathcal{Z})$ induces the $4$-cycle $(z_{1},z_{2},z_{3},z_{4})$
and with exactly one semiedge incident to each of its vertices is referred to
as a _$C_{4}$ -pole_ (see Figure 5). For each $i\in[4]$, let the semiedge
incident to $z_{i}$ be denoted by $f_{i}$. The semiedges $f_{1}$ and $f_{2}$
are referred to as the _upper left semiedge_ and the _upper right semiedge_ of
$\mathcal{Z}$, respectively. On the other hand, the semiedges $f_{3}$ and
$f_{4}$ are referred to as the _lower left semiedge_ and the _lower right
semiedge_ of $\mathcal{Z}$, respectively (see Figure 5).

Figure 5: A $C_{4}$-pole $\mathcal{Z}$ and the $4$-pole $\mathcal{T}_{j}$ in
$\mathcal{P}_{r,\ell}$

For some integer $n\geq 1$, let $\mathcal{Z}_{1},\ldots,\mathcal{Z}_{n}$ be
$n$ copies of the above $C_{4}$-pole $\mathcal{Z}$. For each $j\in[n]$, let
$V(\mathcal{Z}_{j})=\\{z_{1}^{j},z_{2}^{j},z_{3}^{j},z_{4}^{j}\\}$, and let
$f_{1}^{j},f_{2}^{j},f_{3}^{j},f_{4}^{j}$ be the semiedges of
$\mathcal{Z}_{j}$ respectively incident to
$z_{1}^{j},z_{2}^{j},z_{3}^{j},z_{4}^{j}$ such that $f_{1}^{j}$ and
$f_{2}^{j}$ are the upper left and upper right semiedges of $\mathcal{Z}_{j}$,
whilst $f_{3}^{j}$ and $f_{4}^{j}$ are the lower left and lower right
semiedges of $\mathcal{Z}_{j}$. A _chain of $C_{4}$-poles_ of length $n\geq
2$, is the $4$-pole obtained by respectively joining $f_{2}^{j}$ and
$f_{4}^{j}$ (upper and lower right semiedges of $\mathcal{Z}_{j}$) to
$f_{1}^{j+1}$ and $f_{3}^{j+1}$ (upper and lower left semiedges of
$\mathcal{Z}_{j+1}$), for every $j\in[n-1]$. When $n=1$, a chain of
$C_{4}$-poles of length $1$ is just a $C_{4}$-pole. For simplicity, we shall
refer to a chain of $C_{4}$-poles of length $n$, as a _$n$ -chain of
$C_{4}$-poles_, or simply a _$n$ -chain_. The semiedges $f_{1}^{1}$ and
$f_{3}^{1}$ (similarly, $f_{2}^{n}$ and $f_{4}^{n}$) are referred to as the
upper left and lower left (respectively, upper right and lower right)
semiedges of the $n$-chain. A chain of $C_{4}$-poles of any length has exactly
four semiedges. For simplicity, when we say that $e_{1},e_{2},e_{3},e_{4}$ are
the four semiedges of a chain $\mathcal{Z}^{\prime}$ of $C_{4}$-poles
(possibly of length $1$), we mean that $e_{1}$ and $e_{2}$ are respectively
the upper left and upper right semiedges of $\mathcal{Z}^{\prime}$, whilst
$e_{3}$ and $e_{4}$ are respectively the lower left and lower right semiedges
of the same chain $\mathcal{Z}^{\prime}$ (see Figure 6). The semiedges $e_{1}$
and $e_{2}$ (similarly, $e_{3}$ and $e_{4}$) are referred to collectively as
the _upper semiedges_ (respectively, _lower semiedges_) of
$\mathcal{Z}^{\prime}$. In a similar way, the semiedges $e_{1}$ and $e_{3}$
(similarly, $e_{2}$ and $e_{4}$) are referred to collectively as the _left
semiedges_ (respectively, _right semiedges_) of $\mathcal{Z}^{\prime}$.

Figure 6: A chain of $C_{4}$-poles of length 3 having semiedges
$e_{1},e_{2},e_{3},e_{4}$

In order to construct the papillon graph $\mathcal{P}_{r,\ell}$ using
$C_{4}$-poles as building blocks, for each $j\in[r+\ell]$, we consider the
$4$-pole $\mathcal{T}_{j}$ arising from the cycle
$(u_{2j-1},u_{2j},v_{2j},v_{2j-1})$ of $\mathcal{P}_{r,\ell}$, whose semiedges
are $e_{1}^{j},e_{2}^{j},e_{3}^{j},e_{4}^{j}$ as in Figure 5. The $r$-chain
and $\ell$-chain giving rise to $\mathcal{P}_{r,\ell}$ consist of
$\mathcal{T}_{1},\ldots,\mathcal{T}_{r}$ (referred to as the _right $r$-chain_
of $\mathcal{P}_{r,\ell}$), and
$\mathcal{T}_{r+1},\ldots,\mathcal{T}_{r+\ell}$ (referred to as the _left
$\ell$-chain_ of $\mathcal{P}_{r,\ell}$), which have semiedges
$e_{1}^{1},e_{2}^{r},e_{3}^{1},e_{4}^{r}$, and
$e_{1}^{r+1},e_{2}^{r+\ell},\linebreak e_{3}^{r+1},e_{4}^{r+\ell}$,
respectively. The papillon graph $\mathcal{P}_{r,\ell}$ is then obtained by
joining the semiedges in pairs as follows: $e_{1}^{1}$ to $e_{2}^{r+\ell}$,
$e_{2}^{r}$ to $e_{1}^{r+1}$, $e_{3}^{1}$ to $e_{3}^{r+1}$, and $e_{4}^{r}$ to
$e_{4}^{r+\ell}$.

###  2.1 Odd cycles and isomorphisms in the class of papillon graphs

In this section we shall discuss the presence and behaviour of odd cycles in
papillon graphs. Consider the balanced papillon graph $\mathcal{P}_{n}$ and
let $C$ be an odd cycle in $\mathcal{P}_{n}$. Since cycles intersect
$C_{4}$-poles in $2$, $3$ or $4$ vertices, there must exist some
$t_{1}\in[2n]$, such that $|V(C)\cap V(\mathcal{T}_{t_{1}})|=3$. Without loss
of generality, assume that $t_{1}\in[n]$, that is, $\mathcal{T}_{t_{1}}$
belongs to the right $n$-chain of $\mathcal{P}_{n}$. If
$t_{1}\not\in\\{1,n\\}$, we must have exactly one of the following:

  * •

$|V(C)\cap V(\mathcal{T}_{i})|=4$, for all $i\in\\{1,\ldots,t_{1}-1\\}$; or

  * •

$|V(C)\cap V(\mathcal{T}_{i})|=4$, for all $i\in\\{t_{1}+1,\ldots,n\\}$.

Without loss of generality, assume that we either have $t_{1}=1$, or
$|V(C)\cap V(\mathcal{T}_{i})|=4$, for all $i\in\\{1,\ldots,t_{1}-1\\}$. This
implies that the number of vertices in $C$ belonging to
$\cup_{i=1}^{t_{1}}V(\mathcal{T}_{i})$ is odd and at least 3. Moreover, the
edges $a$ and $c$ must belong to $C$. We claim that $b\not\in E(C)$. For,
suppose that $b\in E(C)$. Since $\mathcal{X}$ is a 4-edge-cut, $d\in E(C)$ as
well. This implies that $n>1$ and there exist:

  * •

$t_{2}\in\\{t_{1}+1,\ldots,n\\}$, such that $|V(C)\cap
V(\mathcal{T}_{t_{2}})|=3$;

  * •

$s_{1}\in\\{n+1,\ldots,2n-1\\}$, such that $|V(C)\cap
V(\mathcal{T}_{s_{1}})|=3$; and

  * •

$s_{2}\in\\{s_{1}+1,\ldots,2n\\}$, such that $|V(C)\cap
V(\mathcal{T}_{s_{2}})|=3$.

Let
$\Omega=\\{1,\ldots,t_{1}\\}\cup\\{t_{2},\ldots,n,n+1,\ldots,s_{1}\\}\cup\\{s_{2},\ldots,2n\\}$.
If $\Omega\setminus\\{t_{1},t_{2},s_{1},s_{2}\\}\neq\emptyset$, then for any
$j\in\Omega\setminus\\{t_{1},t_{2},s_{1},s_{2}\\}$, $|V(C)\cap
V(\mathcal{T}_{j})|=4$. Additionally, for any $k\in[2n]\setminus\Omega$,
$|V(C)\cap V(\mathcal{T}_{k})|=0$. However, this means that $C$ has even
length, a contradiction. Thus, $\\{b,d\\}\cap E(C)=\emptyset$. As a result,
$C$ intersects none of the $C_{4}$-poles
$\mathcal{T}_{t_{1}+1},\ldots,\mathcal{T}_{n}$, but intersects each of the
$C_{4}$-poles $\mathcal{T}_{n+1},\ldots,\mathcal{T}_{n}$ in exactly 2 or 4
vertices. Hence, the length of $C$ is at least $2n+3$. When $n=1$,
$(u_{1},u_{2},v_{2},v_{4},u_{4})$ is a $5$-cycle, and when $n>1$,
$(u_{1},u_{2},v_{2},v_{2n+2},u_{2n+2},u_{2n+3},u_{2n+4},\ldots,u_{4n})$ is an
odd cycle of length exactly $2n+3$. Therefore, a shortest odd cycle in
$\mathcal{P}_{n}$ has length $2n+3$. By using similar arguments, a shortest
odd cycle in $\mathcal{P}_{r,\ell}$ has length $2r+3$.

######  Remark 2.2.

The papillon graph $\mathcal{P}_{r,\ell}$ is not bipartite and has a shortest
odd cycle of length $2r+3$.

Consequently, we can show that any two distinct papillon graphs
$\mathcal{P}_{r_{1},\ell_{1}}$ and $\mathcal{P}_{r_{2},\ell_{2}}$ are not
isomorphic, where by distinct we mean that
$(r_{1},\ell_{1})\neq(r_{2},\ell_{2})$. Suppose not, for contradiction. Since
$\mathcal{P}_{r_{1},\ell_{1}}\simeq\mathcal{P}_{r_{2},\ell_{2}}$, we must have
$r_{1}+\ell_{1}=r_{2}+\ell_{2}$, and so if $r_{1}=r_{2}$, then this implies
that $\ell_{1}=\ell_{2}$, and conversely. Hence, $r_{1}\neq r_{2}$ and
$\ell_{1}\neq\ell_{2}$. Thus, without loss of generality, we can assume that
$r_{1}<r_{2}$. However, this means that a shortest odd cycle in
$\mathcal{P}_{r_{1},\ell_{1}}$ (of length $2r_{1}+3$), is shorter than a
shortest odd cycle in $\mathcal{P}_{r_{2},\ell_{2}}$ (of length $2r_{2}+3$), a
contradiction.

We are now in a position to give our first result.

######  Theorem 2.3.

Every papillon graph $\mathcal{P}_{r,\ell}$ is E2F.

######  Proof 2.4.

Let $\mathcal{P}_{r,\ell}$ be a counterexample to the above statement, and let
$M$ be a perfect matching of $\mathcal{P}_{r,\ell}$ whose complementary
2-factor contains an odd cycle $C$. As previously discussed, $C$ must
intersect some $\mathcal{T}_{j}$, for some $j\in[r+\ell]$, in exactly 3
(consecutive) vertices. Without loss of generality, assume that these 3
vertices are $u_{2j-1},u_{2j},v_{2j}$. This means that both the left semiedges
($e_{1}^{j}$ and $e_{3}^{j}$) of $\mathcal{T}_{j}$ belong to this odd cycle.
However, since $C$ is in the complementary 2-factor of $M$, the two edges
$u_{2j-1}v_{2j-1}$ and $v_{2j-1}v_{2j}$ (which do not belong to $E(C)$) must
both belong to $M$, a contradiction.

##  3 The PMH-property in papillon graphs

###  3.1 The balanced case $r=\ell$

Let $M$ be a perfect matching of the balanced papillon graph
$\mathcal{P}_{n}$. Since $\mathcal{X}=\\{a,b,c,d\\}$ is a $4$-edge-cut of
$\mathcal{P}_{n}$, $|M\cap\mathcal{X}|\equiv 0\pmod{2}$, that is,
$|M\cap\mathcal{X}|$ is $0,2$ or $4$. The following is a useful lemma which
shall be used frequently in the results that follow.

######  Lemma 3.1.

Let $M$ be a perfect matching of the balanced papillon graph $\mathcal{P}_{n}$
and let $\mathcal{X}$ be its principal 4-edge-cut. If $|M\cap\mathcal{X}|=k$,
then $|M\cap\partial\mathcal{T}_{j}|=k$, for each $j\in[2n]$.

######  Proof 3.2.

Let $M$ be a perfect matching of $\mathcal{P}_{n}$. We first note that the
left semiedges of a $C_{4}$-pole are contained in a perfect matching if and
only if the right semiedges of the $C_{4}$-pole are contained in the same
perfect matching. The lemma is proved by considering three cases depending on
the possible values of $k$, that is, $0,2$ or $4$. When $n=1$, the result
clearly follows since $\mathcal{X}$ is made up by joining
$\partial\mathcal{T}_{1}$ and $\partial\mathcal{T}_{2}$ accordingly. So assume
$n\geq 2$.

Case I. $k=0$.
Since $a$ and $c$ do not belong to $M$, the left semiedges of
$\mathcal{T}_{1}$ are not contained in $M$, and so $M$ cannot contain its
right semiedges. Therefore, $|M\cap\partial\mathcal{T}_{1}|=0$. Consequently,
the left semiedges of $\mathcal{T}_{2}$ are not contained in $M$ implying
again that $|M\cap\partial\mathcal{T}_{2}|=0$. By repeating the same argument
up till the $n^{\textrm{th}}$ $C_{4}$-pole, we have that
$|M\cap\partial\mathcal{T}_{j}|=0$, for every $j\in[n]$. By noting that $c$
and $d$ do not belong to $M$ and repeating a similar argument to the 4-poles
in the left $n$-chain, we can deduce that $|M\cap\partial\mathcal{T}_{j}|=0$
for every $j\in[2n]$.

Case II. $k=4$.
Since $a$ and $c$ belong to $M$, the left semiedges of $\mathcal{T}_{1}$ are
contained in $M$, and so $M$ contains its right semiedges as well. Therefore,
$|M\cap\partial\mathcal{T}_{1}|=4$. Consequently, the left semiedges of
$\mathcal{T}_{2}$ are contained in $M$ implying again that
$|M\cap\partial\mathcal{T}_{2}|=4$. As in Case I, by noting that both $c$ and
$d$ belong to $M$ and repeating a similar argument to the 4-poles in the left
$n$-chain, we can deduce that $|M\cap\partial\mathcal{T}_{j}|=4$ for every
$j\in[2n]$.

Case III. $k=2$.
We first claim that when $k=2$, $M\cap\mathcal{X}$ must be equal to
$\\{a,d\\}$ or $\\{b,c\\}$. For, suppose that $M\cap\mathcal{X}=\\{a,c\\}$,
without loss of generality. This means that the right semiedges of
$\mathcal{T}_{1}$ are also contained in $M$, implying that
$|M\cap\partial\mathcal{T}_{1}|=4$. This implies that the left semiedges of
$\mathcal{T}_{2}$ are contained in $M$, which forces
$|M\cap\partial\mathcal{T}_{j}|$ to be equal to 4, for every $j\in[2n]$. In
particular, $|M\cap\partial\mathcal{T}_{n}|=4$, implying that the edges $b$
and $d$ belong to $M$, a contradiction since $M\cap\mathcal{X}=\\{a,c\\}$.
This proves our claim. Since the natural automorphism $\psi$ of
$\mathcal{P}_{n}$, which exchanges the outer- and inner-cycles, exchanges also
$\\{a,d\\}$ with $\\{b,c\\}$, without loss of generality, we may assume that
$M\cap\mathcal{X}=\\{a,d\\}$. Since $c\not\in M$,
$1\leq|M\cap\partial\mathcal{T}_{1}|<4$. But, $\partial\mathcal{T}_{1}$
corresponds to a 4-edge-cut in $\mathcal{P}_{n}$, and so, by using a parity
argument, $|M\cap\partial\mathcal{T}_{1}|$ must be equal to 2, implying that
exactly one of the right semiedges of $\mathcal{T}_{1}$ is contained in $M$.
This means that exactly one left semiedge of $\mathcal{T}_{2}$ is contained in
$M$, and consequently, by a similar argument now applied to $\mathcal{T}_{2}$,
we obtain $|M\cap\partial\mathcal{T}_{2}|=2$. By repeating the same argument
and noting that $\mathcal{T}_{n+1}$ has exactly one left semiedge
(corresponding to the edge $d$) contained in $M$, one can deduce that
$|M\cap\partial\mathcal{T}_{j}|=2$ for every $j\in[2n]$.

The following two results are two consequences of the above lemma and they
both follow directly from the proof of Case III. In a few words, if a perfect
matching $M$ of $\mathcal{P}_{n}$ intersects its principal 4-edge-cut in
exactly two of its edges, then these two edges are either the pair $\\{a,d\\}$
or the pair $\\{b,c\\}$, and, for every $j\in[2n]$, $M$ contains only one pair
of semiedges of $\mathcal{T}_{j}$ which does not consist of the pair of left
semiedges of $\mathcal{T}_{j}$ nor the pair of right semiedges of
$\mathcal{T}_{j}$.

######  Corollary 3.3.

Let $M$ be a perfect matching of $\mathcal{P}_{n}$ and let $\mathcal{X}$ be
its principal 4-edge-cut. If $|M\cap\mathcal{X}|=2$, then $M\cap\mathcal{X}$
is equal to $\\{a,d\\}$ or $\\{b,c\\}$.

######  Corollary 3.4.

Let $M$ be a perfect matching of $\mathcal{P}_{n}$ and let $\mathcal{X}$ be
its principal 4-edge-cut such that $|M\cap\mathcal{X}|=2$. For each
$j\in[2n]$, $M$ contains exactly one of the following sets of semiedges:
$\\{e_{1}^{j},e_{2}^{j}\\},\\{e_{3}^{j},e_{4}^{j}\\},\\{e_{1}^{j},e_{4}^{j}\\},\\{e_{2}^{j},e_{3}^{j}\\}$,
that is, of all possible pairs of semiedges of $\mathcal{T}_{j}$,
$\\{e_{1}^{j},e_{3}^{j}\\}$ and $\\{e_{2}^{j},e_{4}^{j}\\}$ cannot be
contained in $M$.

In the sequel, the process of traversing one path after another shall be
called _concatenation of paths_. If two paths $P$ and $Q$ have endvertices
$x,y$ and $y,z$, respectively, we write $PQ$ to denote the path starting at
$x$ and ending at $z$ obtained by traversing $P$ and then $Q$. Without loss of
generality, if $x$ is adjacent to $y$, that is, $P$ is a path on two vertices,
we may write $xyQ$ instead of $PQ$.

######  Lemma 3.5.

Let $M_{1}$ be a perfect matching of $\mathcal{P}_{n}$ such that
$|M_{1}\cap\mathcal{X}|=2$.

  1. (i)

There exists a perfect matching $M_{2}$ of $\mathcal{P}_{n}$ such that
$|M_{2}\cap\mathcal{X}|=2$ and $M_{1}\cap M_{2}=\emptyset$.

  2. (ii)

The complementary $2$-factors of $M_{1}$ and $M_{2}$ are both Hamiltonian
cycles.

######  Proof 3.6.

(i) Since $|M_{1}\cap\mathcal{X}|=2$, by Lemma 3.1 we get that
$|M_{1}\cap\partial\mathcal{T}_{j}|=2$ for every $j\in[2n]$. For each $j$, let
$P^{(j)}$ be the subgraph of $\mathcal{P}_{n}$ which is induced by
$E(\mathcal{T}_{j})-M_{1}$. Note that
$\cup_{j=1}^{2n}V(P^{(j)})=V(\mathcal{P}_{n})$. By Corollary 3.4, each
$P^{(j)}$ is a path of length 3. Letting $N$ be the unique perfect matching of
$\mathcal{P}_{n}$ which intersects each $E(P^{(j)})$ in exactly two edges, we
note that $M_{1}\cap N=\emptyset$. Let $M_{2}=E(\mathcal{P}_{n})-(M_{1}\cup
N)$. Since $M_{1}$ and $N$ are two disjoint perfect matchings, $M_{2}$ is also
a perfect matching of $\mathcal{P}_{n}$ and, in particular, $M_{2}$ contains
$\mathcal{X}-(M_{1}\cap\mathcal{X})$. Thus, $|M_{2}\cap\mathcal{X}|=2$ and
$M_{1}\cap M_{2}=\emptyset$, proving part (i).

Figure 7: Perfect matching $M_{1}$ (bold dashed edges) with
$|M_{1}\cap\mathcal{X}|=2$ and its complementary 2-factor (highlighted edges)

(ii) Let $M_{2}$ be as in part (i), that is, $|M_{2}\cap\mathcal{X}|=2$ and
$M_{1}\cap M_{2}=\emptyset$. When $n=1$, the result clearly follows. So assume
$n\geq 2$. For distinct $i$ and $j$ in $[2n]$, let $Q^{(i,j)}$ be the subgraph
of $\mathcal{P}_{n}$ which is induced by $M_{2}\cap\\{xy\in
E(\mathcal{P}_{n}):x\in V(\mathcal{T}_{i}),y\in V(\mathcal{T}_{j})\\}$, that
is, $E(Q^{(i,j)})$ is either empty or consists of exactly one edge, that is,
$Q^{(i,j)}$ is a path of length 1. When $M_{1}\cap\mathcal{X}=\\{a,d\\}$, we
can form a Hamiltonian cycle of $\mathcal{P}_{n}$ (not containing $M_{1}$) by
considering the following concatenation of paths:

$P^{(1)}Q^{(1,2)}\ldots
Q^{(n-1,n)}P^{(n)}Q^{(n,2n)}P^{(2n)}Q^{(2n,2n-1)}\ldots P^{(n+1)}Q^{(n+1,1)},$

where $Q^{(1,2)}$ and $Q^{(2n,2n-1)}$ are respectively followed by $P^{(2)}$
and $P^{(2n-1)}$, and, $Q^{(n,2n)}$ and $Q^{(n+1,1)}$ consist of the edges $b$
and $c$, respectively. On the other hand, when
$M_{1}\cap\mathcal{X}=\\{b,c\\}$, we can form a Hamiltonian cycle of
$\mathcal{P}_{n}$ (not containing $M_{1}$) by considering the following
concatenation of paths:

$P^{(1)}Q^{(1,2)}\ldots
Q^{(n-1,n)}P^{(n)}Q^{(n,n+1)}P^{(n+1)}Q^{(n+1,n+2)}\ldots P^{(2n)}Q^{(2n,1)},$

where $Q^{(1,2)}$ and $Q^{(n+1,n+2)}$ are respectively followed by $P^{(2)}$
and $P^{(n+2)}$, and, $Q^{(n,n+1)}$ and $Q^{(2n,1)}$ consist of the edges $d$
and $a$, respectively. Thus, the complementary 2-factor of $M_{1}$ is a
Hamiltonian cycle. This is depicted in Figure 7. The proof that the
complementary 2-factor of $M_{2}$ is a Hamiltonian cycle follows analogously.

######  Proposition 3.7.

Let $n$ be a positive odd integer. Then, the balanced papillon graph
$\mathcal{P}_{n}$ is not PMH.

######  Proof 3.8.

Consider the following perfect matching of the balanced papillon graph
$\mathcal{P}_{n}$:

$M=\cup_{i=1}^{2n}\\{u_{2i-1}u_{2i},v_{2i-1}v_{2i}\\}.$

It is clear that when $n=1$, the perfect matching $M$ cannot be extended to a
Hamiltonian cycle of the balanced papillon graph $\mathcal{P}_{1}$. So assume
that $n\geq 3$. We claim that $M$ cannot be extended to a Hamiltonian cycle of
$\mathcal{P}_{n}$. For, let $F$ be a $2$-factor of $\mathcal{P}_{n}$
containing $M$. Since $u_{1}u_{2}\in M$ and $\mathcal{P}_{n}$ is cubic, $F$
contains exactly one of the following two edges: $u_{1}u_{4n}$ or
$u_{1}v_{1}$. In the former case, if $u_{1}u_{4n}\in E(F)$, then,
$u_{2n}u_{2n+1}$ and all the edges of the outer- and inner-cycle will belong
to $F$ (at the same time, the choice of $u_{1}u_{4n}$ forbids all the spokes
of $\mathcal{P}_{n}$ to belong to $F$), yielding two disjoint cycles each of
length $4n$. In the latter case, if $u_{1}v_{1}\in E(F)$, then $F$ must also
contain all spokes $u_{i}v_{i}$, for $1<i\leq 4n$. In fact, the subgraph
induced by the set of spokes is exactly the complement of the 2-factor
obtained in the former case. Consequently, $F$ will consist of $2n$ disjoint
$4$-cycles.

Consider $\mathcal{P}_{n}$, with $n\geq 2$, and let $M$ be a perfect matching
of $\mathcal{P}_{n}$ with $M\cap\mathcal{X}=0$, which by Lemma 3.1 implies
that $|M\cap\partial\mathcal{T}_{j}|=0$ for all $j\in[2n]$. Now consider
$j\in[2n]\setminus\\{n,2n\\}$ and let $\mathcal{T}_{(j,j+1)}$ denote a
$2$-chain composed of $\mathcal{T}_{j}$ and $\mathcal{T}_{j+1}$. We say that
$\mathcal{T}_{(j,j+1)}$ is _symmetric with respect to $M$_ if exactly one of
the following occurs:

  1. (i)

$\\{u_{2j-1}v_{2j-1},u_{2j}v_{2j},u_{2j+1}v_{2j+1},u_{2j+2}v_{2j+2}\\}\subset
M$; or

  2. (ii)

$\\{u_{2j-1}u_{2j},v_{2j-1}v_{2j},u_{2j+1}u_{2j+2},v_{2j+1}v_{2j+2}\\}\subset
M$.

If neither (i) nor (ii) occur, $\mathcal{T}_{(j,j+1)}$ is said to be
_asymmetric with respect to $M$_. This is shown in Figure 8.

Figure 8: Symmetric and asymmetric $2$-chains with the bold dashed edges
belonging to $M$

######  Remark 3.9.

Let $n\geq 2$. Consider a perfect matching $M_{1}$ of $\mathcal{P}_{n}$ such
that $M_{1}$ does not intersect the principal 4-edge-cut $\mathcal{X}$ of
$\mathcal{P}_{n}$, that is, $M_{1}\cap\mathcal{X}=\emptyset$, and consider a
$2$-chain of $\mathcal{P}_{n}$, say $\mathcal{T}_{(j,j+1)}$ with
$j\in[2n]\setminus\\{n,2n\\}$, having semiedges $e_{1},e_{2},e_{3},e_{4}$,
where $e_{1}=e_{1}^{j},e_{2}=e_{2}^{j+1},e_{3}=e_{3}^{j}$ and
$e_{4}=e_{4}^{j+1}$. Assume there exists a perfect matching $M_{2}$ of
$\mathcal{P}_{n}$ such that $|M_{2}\cap\mathcal{X}|=2$ and $M_{1}\cap
M_{2}=\emptyset$ (see Figure 9). If $\mathcal{T}_{(j,j+1)}$ is symmetric with
respect to $M_{1}$, then we have exactly one of the following instances:

$M_{2}\cap\partial\mathcal{T}_{(j,j+1)}=\\{e_{1},e_{2}\\}\mbox{ (upper); \quad
or \quad}M_{2}\cap\partial\mathcal{T}_{(j,j+1)}=\\{e_{3},e_{4}\\}\mbox{
(lower)}.$

Otherwise, if $\mathcal{T}_{(j,j+1)}$ is asymmetric with respect to $M_{1}$,
then exactly one of the following must occur:

$M_{2}\cap\partial\mathcal{T}_{(j,j+1)}=\\{e_{1},e_{4}\\}\mbox{ (upper left,
lower right); or }$
$M_{2}\cap\partial\mathcal{T}_{(j,j+1)}=\\{e_{2},e_{3}\\}\mbox{ (upper right,
lower left)}.$

Notwithstanding whether $\mathcal{T}_{(j,j+1)}$ is symmetric or asymmetric
with respect to $M_{1}$, $(M_{1}\cup M_{2})\cap E(\mathcal{T}_{(j,j+1)})$
induces a path (see Figure 9) which contains all the vertices of
$V(\mathcal{T}_{(j,j+1)})$, and whose endvertices are the endvertices of the
semiedges in $M_{2}\cap\partial\mathcal{T}_{(j,j+1)}$.

Figure 9: $2$-chains when $M_{1}\cap\mathcal{X}=\emptyset$ and
$|M_{2}\cap\mathcal{X}|=2$ (bold dashed edges belong to $M_{1}$ and
highlighted edges to $M_{2}$)

######  Remark 3.10.

Let $n\geq 2$. Consider a perfect matching $M_{1}$ of $\mathcal{P}_{n}$ such
that $M_{1}$ does not intersect the principal 4-edge-cut $\mathcal{X}$ of
$\mathcal{P}_{n}$, that is, $M_{1}\cap\mathcal{X}=\emptyset$, and consider a
$2$-chain of $\mathcal{P}_{n}$, say $\mathcal{T}_{(j,j+1)}$ with
$j\in[2n]\setminus\\{n,2n\\}$. Let $M_{2}$ be the perfect matching of
$\mathcal{P}_{n}$ such that $|M_{2}\cap\mathcal{X}|=4$. Clearly $M_{1}\cap
M_{2}=\emptyset$. Notwithstanding whether $\mathcal{T}_{(j,j+1)}$ is symmetric
or asymmetric with respect to $M_{1}$, we have that $(M_{1}\cup M_{2})\cap
E(\mathcal{T}_{(j,j+1)})$ induces two disjoint paths of equal length (see
Figure 10) whose union contains all the vertices of $\mathcal{T}_{j}$ and
$\mathcal{T}_{j+1}$. Let $Q$ be one of these paths. We first note that $Q$
contains exactly one vertex from $\\{u_{j},v_{j+1}\\}$ and exactly one vertex
from $\\{u_{j+3},v_{j+2}\\}$. If $\mathcal{T}_{(j,j+1)}$ is symmetric with
respect to $M_{1}$, then $Q$ contains $u_{j}$ if and only if $Q$ contains
$u_{j+3}$. Otherwise, if $\mathcal{T}_{(j,j+1)}$ is asymmetric with respect to
$M_{1}$, then $Q$ contains $u_{j}$ if and only if $Q$ contains $v_{j+2}$.

Figure 10: $2$-chains when $M_{1}\cap\mathcal{X}=\emptyset$ and
$|M_{2}\cap\mathcal{X}|=4$ (bold dashed edges belong to $M_{1}$ and
highlighted edges to $M_{2}$)

######  Theorem 3.11.

Let $n$ be a positive even integer. Then, the balanced papillon graph
$\mathcal{P}_{n}$ is PMH.

######  Proof 3.12.

Let $M_{1}$ be a perfect matching of $\mathcal{P}_{n}$. We need to show that
there exists a perfect matching $M_{2}$ of $\mathcal{P}_{n}$ such that
$M_{1}\cup M_{2}$ induces a Hamiltonian cycle of $\mathcal{P}_{n}$. Three
cases, depending on the intersection of $M_{1}$ with the principal 4-edge-cut
$\mathcal{X}$ of $\mathcal{P}_{n}$, are considered. If
$|M_{1}\cap\mathcal{X}|=2$, then, by Lemma 3.5, there exists a perfect
matching $N$ of $\mathcal{P}_{n}$ such that $|N\cap\mathcal{X}|=2$ and
$M_{1}\cap N=\emptyset$. Moreover, the complementary 2-factor of $N$ is a
Hamiltonian cycle. Since $M_{1}$ is contained in the mentioned 2-factor, the
result follows. When $|M_{1}\cap\mathcal{X}|=4$, we can define $M_{2}$ to be
the following perfect matching:

$M_{2}=\\{u_{1}v_{1},u_{2}v_{2}\\}\bigcup\cup_{j=2}^{2n}\\{u_{2j-1}u_{2j},v_{2j-1}v_{2j}\\}.$

In fact, $M_{1}\cup M_{2}$ induces the following Hamiltonian cycle:
$(u_{1},v_{1},v_{4},\ldots,v_{2n},v_{2n-1},\linebreak
v_{4n-1},v_{4n},v_{4n-3},\ldots,v_{2n+1},v_{2n+2},v_{2},u_{2},u_{3},u_{4},\ldots,u_{4n})$,
where $v_{4}$ and $v_{4n-3}$ are respectively followed by $v_{3}$ and
$v_{4n-2}$.

What remains to be considered is the case when $|M_{1}\cap\mathcal{X}|=0$.
Clearly, $|M_{2}\cap\mathcal{X}|$ cannot be zero, because, if so, choosing
$M_{2}$ to be disjoint from $M_{1}$, $M_{1}\cup M_{2}$ induces $2n$ disjoint
$4$-cycles. Therefore, $|M_{2}\cap\mathcal{X}|$ must be equal to 2 or 4. Let
$\mathcal{R}=\\{\mathcal{T}_{(1,2)},\ldots,\mathcal{T}_{(n-1,n)}\\}$ and
$\mathcal{L}=\\{\mathcal{T}_{(n+1,n+2)},\ldots,\mathcal{T}_{(2n-1,2n)}\\}$ be
the sets of 2-chains within the left and right $n$-chains of
$\mathcal{P}_{n}$—namely the right and left $n$-chains each split into
$\frac{n}{2}$ $2$-chains. We consider two cases depending on the parity of the
number of $2$-chains in $\mathcal{L}$ and $\mathcal{R}$ which are asymmetric
with respect to $M_{1}$. Let the function
$\Phi:\mathcal{\mathcal{R}}\cup\mathcal{L}\rightarrow\\{-1,+1\\}$ be defined
on the $2$-chains $\mathcal{T}\in\mathcal{R}\cup\mathcal{L}$ such that:

$\Phi(\mathcal{T})=\begin{cases}+1&$if $\mathcal{T}$ is symmetric with respect
to $M_{1},\\\ -1&$otherwise.$\end{cases}$

Case 1. $\mathcal{L}$ and $\mathcal{R}$ each have an even number (possibly
zero) of asymmetric $2$-chains with respect to $M_{1}$.

We claim that there exists a perfect matching such that its union with $M_{1}$
gives a Hamiltonian cycle of $\mathcal{P}_{n}$. Since the number of asymmetric
$2$-chains in $\mathcal{R}$ is even,
$\prod_{\mathcal{T}\in\mathcal{R}}\Phi(\mathcal{T})=+1$, and consequently, by
appropriately concatenating paths as in Remark 3.9, there exists a path $R$
with endvertices $u_{1}$ and $u_{2n}$ whose vertex set is
$\cup_{i=1}^{2n}\\{u_{i},v_{i}\\}$ such that it contains all the edges in
$M_{1}\cap(\cup_{i=1}^{n}E(\mathcal{T}_{i}))$. We remark that this path
intersects exactly one edge of $\\{xy\in E(\mathcal{P}_{n}):x\in
V(\mathcal{T}_{j}),y\in V(\mathcal{T}_{j+1})\\}$, for each $j\in[n-1]$. By a
similar reasoning, since
$\prod_{\mathcal{T}\in\mathcal{L}}\Phi(\mathcal{T})=+1$, there exists a path
$L$ with endvertices $u_{2n+1}$ and $u_{4n}$ whose vertex set is
$\cup_{i=2n+1}^{4n}\\{u_{i},v_{i}\\}$, such that it contains all the edges in
$M_{1}\cap(\cup_{i=n+1}^{2n}E(\mathcal{T}_{i}))$. Once again, this path
intersects exactly one edge of $\\{xy\in E(\mathcal{P}_{n}):x\in
V(\mathcal{T}_{j}),y\in V(\mathcal{T}_{j+1})\\}$, for each
$j\in\\{n+1,\ldots,2n-1\\}$. These two paths, together with the edges $a$ and
$d$ form the required Hamiltonian cycle of $\mathcal{P}_{n}$ containing
$M_{1}$, proving our claim. We remark that this shows that there exists a
perfect matching $M_{2}$ of $\mathcal{P}_{n}$ such that
$M_{2}\cap\mathcal{X}=\\{a,d\\}$, $M_{1}\cap M_{2}=\emptyset$ and with
$M_{1}\cup M_{2}$ inducing a Hamiltonian cycle of $\mathcal{P}_{n}$. One can
similarly show that there exists a perfect matching $M_{2}^{\prime}$ of
$\mathcal{P}_{n}$ such that $M_{2}^{\prime}\cap\mathcal{X}=\\{b,c\\}$,
$M_{1}\cap M_{2}^{\prime}=\emptyset$ and with $M_{1}\cup M_{2}^{\prime}$
inducing a Hamiltonian cycle of $\mathcal{P}_{n}$.

Case 2. One of $\mathcal{L}$ and $\mathcal{R}$ has an odd number of asymmetric
$2$-chains with respect to $M_{1}$.

Without loss of generality, assume that $\mathcal{R}$ has an odd number of
asymmetric $2$-chains with respect to $M_{1}$, that is,
$\prod_{\mathcal{T}\in\mathcal{R}}\Phi(\mathcal{T})=-1$. Let $M_{2}$ be the
perfect matching of $\mathcal{P}_{n}$ such that $|M_{2}\cap\mathcal{X}|=4$. We
claim that $M_{1}\cup M_{2}$ induces a Hamiltonian cycle of $\mathcal{P}_{n}$.
Since $\prod_{\mathcal{T}\in\mathcal{R}}\Phi(\mathcal{T})=-1$, by
appropriately concatenating paths as in Remark 3.10 we can deduce that
$M_{1}\cup M_{2}$ contains the edge set of two disjoint paths $R_{1}$ and
$R_{2}$, such that:

  1. (i)

$|V(R_{1})|=|V(R_{2})|=2n$;

  2. (ii)

$V(R_{1})\cup V(R_{2})=\cup_{i=1}^{2n}\\{u_{i},v_{i}\\}$;

  3. (iii)

the endvertices of $R_{1}$ are $u_{1}$ and $v_{2n-1}$; and

  4. (iv)

the endvertices of $R_{2}$ are $v_{2}$ and $u_{2n}$.

Next, we consider two subcases depending on the value of
$\prod_{\mathcal{T}\in\mathcal{L}}\Phi(\mathcal{T})$. We shall be using the
fact that
$\\{u_{1}u_{4n},v_{2n-1}v_{4n-1},v_{2}v_{2n+2},u_{2n}u_{2n+1}\\}=\\{a,b,c,d\\}=\mathcal{X}\subset
M_{2}$.

Case 2a) $\prod_{\mathcal{T}\in\mathcal{L}}\Phi(\mathcal{T})=-1$

As above, by Remark 3.10, we can deduce that $M_{1}\cup M_{2}$ contains the
edge set of two disjoint paths $L_{1}$ and $L_{2}$, such that:

  1. (i)

$|V(L_{1})|=|V(L_{2})|=2n$;

  2. (ii)

$V(L_{1})\cup V(L_{2})=\cup_{i=2n+1}^{4n}\\{u_{i},v_{i}\\}$;

  3. (iii)

the endvertices of $L_{1}$ are $u_{2n+1}$ and $v_{4n-1}$; and

  4. (iv)

the endvertices of $L_{2}$ are $v_{2n+2}$ and $u_{4n}$.

The concatenation of the following paths and edges gives a Hamiltonian cycle
of $\mathcal{P}_{n}$ containing $M_{1}$:

$R_{1}v_{2n-1}v_{4n-1}L_{1}u_{2n+1}u_{2n}R_{2}v_{2}v_{2n+2}L_{2}u_{4n}u_{1}.$

Case 2b) $\prod_{\mathcal{T}\in\mathcal{L}}\Phi(\mathcal{T})=+1$.

Once again, by Remark 3.10 we can deduce that $M_{1}\cup M_{2}$ contains the
edge set of two disjoint paths $L_{1}$ and $L_{2}$, such that:

  1. (i)

$|V(L_{1})|=|V(L_{2})|=2n$;

  2. (ii)

$V(L_{1})\cup V(L_{2})=\cup_{i=2n+1}^{4n}\\{u_{i},v_{i}\\}$;

  3. (iii)

the endvertices of $L_{1}$ are $u_{2n+1}$ and $u_{4n}$; and

  4. (iv)

the endvertices of $L_{2}$ are $v_{2n+2}$ and $v_{4n-1}$.

The concatenation of the following paths and edges gives a Hamiltonian cycle
of $\mathcal{P}_{n}$ containing $M_{1}$:

$R_{1}v_{2n-1}v_{4n-1}L_{2}v_{2n+2}v_{2}R_{2}u_{2n}u_{2n+1}L_{1}u_{4n}u_{1}.$

This completes the proof.

###  3.2 The unbalanced case $r<\ell$ and final remarks

By following the proofs in Section 2, the results obtained for balanced
papillon graphs are now extended to unbalanced papillon graphs.

######  Theorem 3.13.

The unbalanced papillon graph $\mathcal{P}_{r,\ell}$ is PMH if and only if $r$
and $\ell$ are both even.

######  Proof 3.14.

This is an immediate consequence of Proposition 3.7 and Theorem 3.11. In
particular, when at least one of $r$ and $\ell$ is odd, $\mathcal{P}_{r,\ell}$
is not PMH because the perfect matching
$\cup_{i=1}^{r+\ell}\\{u_{2i-1}u_{2i},v_{2i-1}v_{2i}\\}$ of
$\mathcal{P}_{r,\ell}$ (illustrated in Figure 11) cannot be extended to a
Hamiltonian cycle.

######  Corollary 3.15.

The papillon graph $\mathcal{P}_{r,\ell}$ is PMH if and only if $r$ and $\ell$
are both even.

Figure 11: $\mathcal{P}_{1,3}$ and $\mathcal{P}_{3,4}$: unbalanced papillon
graphs are not always PMH. The above perfect matchings do not extend to a
Hamiltonian cycle.

Finally, we remark that since $\mathcal{P}_{n}$ is PMH for every even
$n\in\mathbb{N}$, balanced papillon graphs provide us with examples of non-
bipartite PMH cubic graphs which are cyclically 4-edge-connected and have
girth 4 such that their order is a multiple of $16$. Additionally, by
considering unbalanced papillon graphs, say $\mathcal{P}_{2,\ell}$, for some
even $\ell>2$, we can obtain non-bipartite PMH cubic graphs having the above
characteristics (that is, cyclically 4-edge-connected and having girth $4$)
such that their order is $8\nu$, for odd $\nu\geq 3$.

It would also be very compelling to see whether there exist other $4$-poles
instead of the $C_{4}$-poles that can be used as building blocks when
constructing papillon graphs and which yield non-bipartite PMH or just E2F
cubic graphs.

## References

  * [1] M. Abreu, J.B. Gauci, D. Labbate, G. Mazzuoccolo and J.P. Zerafa, Extending perfect matchings to Hamiltonian cycles in line graphs, _Electron. J. Combin._ 28(1) (2021), #P1.7.
  * [2] M. Abreu, J.B. Gauci and J.P. Zerafa, _Saved by the rook: a case of matchings and Hamiltonian cycles_ , submitted, arXiv:2104.01578.
  * [3] A. Alahmadi, R.E.L. Aldred, A. Alkenani, R. Hijazi, P. Solé and C. Thomassen, Extending a perfect matching to a Hamiltonian cycle, _Discrete Math. Theor. Comput. Sci._ , 17(1) (2015), 241–254.
  * [4] R. Diestel, _Graph Theory_ , Graduate Texts in Mathematics 173, Springer-Verlag, New York, 2000.
  * [5] M. Funk, B. Jackson, D. Labbate and J. Sheehan, 2-Factor hamiltonian graphs, _J. Combin. Theory Ser. B_ 87 (2003), 138–144.
  * [6] M. Funk and D. Labbate, On minimally one-factorable r-regular bipartite graphs, _Discrete Math._ 216 (2000), 121–137.
  * [7] J.B. Gauci and J.P. Zerafa, Perfect Matchings and Hamiltonicity in the Cartesian Product of Cycles, _Ann. Comb._ 25 (2021), 789–796, https://doi.org/10.1007/s00026-021-00548-1.
  * [8] J.B. Gauci and J.P. Zerafa, Accordion graphs: Hamiltonicity, matchings and isomorphism with quartic circulants, _Discrete Appl. Math._ 321 (2022), 126–137.
  * [9] R. Häggkvist, On $F$-Hamiltonian graphs, in: J.A. Bondy, U.S.R. Murty (eds.), _Graph Theory and Related Topics_ , Academic Press, New York, 1979, 219–231.
  * [10] D.A. Holton and J. Sheehan, The Petersen Graph, Cambridge Univ. Press, Cambridge, 1993.
  * [11] D. Labbate, Characterizing minimally 1-factorable r-regular bipartite graphs, _Discrete Math._ 248 (2002), 109–123.
  * [12] D. Labbate, On 3-cut reductions of minimally 1-factorable cubic bigraphs, _Discrete Math._ 231 (2001), 303–310.
  * [13] D. Labbate, On determinants and permanents of minimally 1-factorable cubic bipartite graphs, _Note Mat._ 20 (2000/01), 37–42.
  * [14] M. Las Vergnas, _Problèmes de couplages et problèmes hamiltoniens en théorie des graphes_ , Thesis, University of Paris 6, Paris, 1972.
  * [15] F. Romaniello and J.P. Zerafa, _Betwixt and between 2-factor Hamiltonian and Perfect-Matching-Hamiltonian graphs_ , submitted, arXiv:2109.03060.