###### Abstract

A graph is 2-factor Hamiltonian (2FH) if each one of its 2-factors is a
Hamiltonian cycle. A similar, but weaker, property is the Perfect-Matching-
Hamiltonian property (PMH-property): a graph is said to admit this property if
each one of its perfect matchings (1-factors) can be extended to a Hamiltonian
cycle. In [_J. Combin. Theory Ser. B_ 87 (2003)], Funk _et al._ introduce the
_star product_ and show that this graph operation between two bipartite 2FH-
graphs is a necessary and sufficient condition for a bipartite graph admitting
a 3-edge-cut to be 2FH. The same cannot be said when dealing with the PMH-
property, and in this work we discuss how one can use star products to obtain
graphs (which are not necessarily bipartite, regular and 2FH) admitting the
PMH-property from smaller graphs, with the help of _malleable_ vertices which
we introduce here. The presence of a malleable vertex in a graph implies that
the graph has the PMH-property, but does not necessarily imply that it is 2FH.
Funk _et al._ also conjecture that if a graph is a bipartite cubic 2FH-graph,
then it can only be obtained from the complete bipartite graph $K_{3,3}$ and
the Heawood graph by using star products. Here, we show that a cubic graph
(not necessarily bipartite) is 2FH if and only if all of its vertices are
malleable. We also show that the above conjecture is equivalent to saying that
every bipartite cyclically 4-edge-connected cubic graph having the PMH-
property, except for the Heawood graph, admits a perfect matching which can be
extended to a Hamiltonian cycle in exactly one way. Finally, we also give
necessary and sufficient conditions for a graph admitting a 2-edge-cut to be
2FH or PMH.

###### keywords:

Cubic graph, $2$-factor, perfect matching, Hamiltonian cycle

Betwixt and between 2-factor Hamiltonian and Perfect-Matching-Hamiltonian
graphs

Federico Romaniello Dipartimento di Matematica, Informatica ed Economia
Università degli Studi della Basilicata<EMAIL_ADDRESS>
Jean Paul Zerafa Department of Technology and Entrepreneurship Education
University of Malta, Malta<EMAIL_ADDRESS>
05C45, 05C70, 05C76

##  1 Introduction

Graphs considered in the sequel are connected (unless otherwise stated) and
are allowed to have multiedges but no loops. The vertex set and the edge set
of a graph $G$ are denoted by $V(G)$ and $E(G)$, respectively, and the number
of neighbours of a vertex $v$ is denoted by $\textrm{deg}(v)$. For some
integer $t\geq 1$, a _$t$ -factor_ of a graph $G$ is a $t$-regular spanning
subgraph of $G$ (not necessarily connected). In particular, a _perfect
matching_ of a graph is the edge set of a 1-factor, and a connected 2-factor
of a graph is a _Hamiltonian cycle_. For $k\geq 3$, a _cycle_ of length $k$
(or a $k$-cycle), denoted by $(v_{1},\ldots,v_{k})$, is a sequence of mutually
distinct vertices $v_{1},v_{2},\ldots,v_{k}$ with corresponding edge set
$\\{v_{1}v_{2},\ldots,v_{k-1}v_{k},v_{k}v_{1}\\}$. For other definitions not
explicitly stated here we refer the reader to [5]. A graph $G$ admitting a
perfect matching is said to have the _Perfect-Matching-Hamiltonian property_
(for short, the PMH-property) if every perfect matching $M$ of $G$ can be
_extended_ to a Hamiltonian cycle of $G$, that is, there exists a perfect
matching $N$ of $G$ such that $M\cup N$ induces a Hamiltonian cycle of $G$.
For simplicity, a graph admitting the PMH-property is said to be PMH or a PMH-
graph. This property was introduced in the 1970s by Las Vergnas [15] and
Häggkvist [11] and for recent results in this area we suggest the following
non-exhaustive list [1, 2, 3, 4, 6, 10, 9, 12]. If we restrict ourselves to
the class of $3$-regular graphs (cubic graphs), there is already a known and
well-studied class which are naturally PMH (as we shall see in Theorem 2.2).
This is the class of cubic $2$-factor Hamiltonian graphs. The term _2-factor
Hamiltonian_ (2FH) was coined by Funk _et al._ in [8], where the authors study
Hamiltonian graphs with the property that all their $2$-factors are
Hamiltonian. In their work, the authors prove that if a graph $G$ is a
bipartite $t$-regular 2FH-graph, then $G$ is either a cycle or $t=3$.

Before proceeding, we define what a star product is. Let $G_{1}$ and $G_{2}$
be two graphs each containing a vertex of degree $3$, say, $v_{1}\in V(G_{1})$
and $v_{2}\in V(G_{2})$. Let $x_{1},y_{1},z_{1}$ be the neighbours of $v_{1}$
in $G_{1}$, and $x_{2},y_{2},z_{2}$ be the neighbours of $v_{2}$ in $G_{2}$. A
_star product_ on $v_{1}$ and $v_{2}$, denoted by
$G_{1}(x_{1}y_{1}z_{1})*G_{2}(x_{2}y_{2}z_{2})$, is a graph operation that
consists in constructing the new graph
$(G_{1}-v_{1})\cup(G_{2}-v_{2})\cup\\{x_{1}x_{2},y_{1}y_{2},z_{1}z_{2}\\}$.
The $3$-edge-cut $\\{x_{1}x_{2},y_{1}y_{2},z_{1}z_{2}\\}$ is referred to as
the _principal $3$-edge-cut_ of the resulting graph (see for instance [7]).
Other graphs can be obtained by a star product on $v_{1}$ and $v_{2}$, for
example,
$(G_{1}-v_{1})\cup(G_{2}-v_{2})\cup\\{x_{1}z_{2},y_{1}y_{2},z_{1}x_{2}\\}$,
but, unless otherwise stated, if it is not important how the adjacencies in
the principal 3-edge cut look like, we use the notation
$G_{1}(v_{1})*G_{2}(v_{2})$ and we say that it is a graph obtained by a star
product on $v_{1}$ and $v_{2}$. For simplicity, we shall also say that the
resulting graph has been obtained by applying a star product _between_ $G_{1}$
and $G_{2}$. Since a star product between a graph $G$ and the unique cubic
graph on two vertices results in $G$ itself, in the sequel we shall tacitly
assume that when considering a star product between two graphs, neither one of
the two graphs is the cubic graph on two vertices.

######  Proposition 1.1.

[8] Let $G=G_{1}(v_{1})*G_{2}(v_{2})$ be a bipartite graph which is obtained
by a star product on $v_{1}\in V(G_{1})$ and $v_{2}\in V(G_{2})$, both of
degree $3$. Then, $G$ is 2FH if and only if $G_{1}$ and $G_{2}$ are both 2FH.

We note that in the above proposition, $G_{1}$ and $G_{2}$ are not necessarily
cubic graphs, and only need to admit a vertex of degree $3$ each, denoted
above by $v_{1}$ and $v_{2}$, respectively. Moreover, we remark that, in the
above proposition, the hypothesis that $G$ is bipartite is needed, because
although the complete graph $K_{4}$ is a 2FH-graph, the graph obtained by
applying a star product between two copies of $K_{4}$ is not 2FH (and neither
PMH). By using Proposition 1.1, the authors construct an infinite family of
bipartite cubic 2FH-graphs by taking repeated star products of $K_{3,3}$ and
the Heawood graph. They also conjecture that these are the only such graphs,
and this conjecture is still widely open.

######  Conjecture 1.2 (Funk _et al._ , 2003 [8]).

A bipartite cubic 2FH-graph can be obtained from the complete bipartite graph
$K_{3,3}$ and the Heawood graph by repeated star products.

##  2 Malleable vertices

Let $\partial v$ be the set of edges incident to a vertex $v$.

######  Definition 2.1.

Let $G$ be a graph admitting a perfect matching and let $v$ be a vertex of $G$
having degree $t\geq 2$. The vertex $v$ is said to be _$t$ -malleable_ (or
just _malleable_) if for every perfect matching $M$ of $G$, there exist
Hamiltonian cycles $H_{1},\ldots,H_{t-1}$ all extending $M$, such that
$\partial v-M\subset\cup_{i=1}^{t-1}E(H_{i})$.

Therefore, if $G$ admits a $t$-malleable vertex $v$, given a perfect matching
$M$ of $G$, there exist $t-1$ distinct Hamiltonian cycles, such that each
Hamiltonian cycle extends $M$ and contains a different edge of $\partial v-M$,
implying that the $t-1$ Hamiltonian cycles cover all edges incident to $v$
(since every Hamiltonian cycle contains the edge in $\partial v\cap M$).
Moreover, if a graph admits a malleable vertex, then it clearly is PMH. In
particular, if $|V(G)|>2$ and $v\in V(G)$ is malleable, then the number of
neighbours of $v$ must be equal to $\textrm{deg}(v)$, that is, there cannot be
any multiedges incident to $v$. Although the definition of malleable vertices
seems quite strong, in even cycles and cubic graphs, the presence of a
malleable vertex is equivalent to saying that the graph is 2FH.

###  2.1 Even cycles and cubic graphs

A (connected) 2-regular graph admitting a 2-malleable vertex, must be
bipartite, otherwise it does not admit a perfect matching. One can easily see
that cycles on an even number of vertices are 2FH and all the vertices are
2-malleable. So consider cubic graphs.

######  Theorem 2.2.

A cubic graph $G$ is 2FH if and only if $G$ admits a 3-malleable vertex.

######  Proof 2.3.

($\Rightarrow$) Let $u$ be a vertex of $G$ and let $M$ be a perfect matching
of $G$. Moreover, let $\overline{M}=E(G)-M$, that is, the edge set of the
complementary $2$-factor of $M$. Since $G$ is 2FH, $\overline{M}$ gives a
Hamiltonian cycle, and since $G$ is of even order, $E(\overline{M})=N_{1}\cup
N_{2}$, where $N_{1}$ and $N_{2}$ are edge-disjoint perfect matchings of $G$.
Once again, since $G$ is 2FH, $M\cup N_{1}$ and $M\cup N_{2}$ are both
Hamiltonian cycles of $G$. Thus, $u$ is a 3-malleable vertex.

($\Leftarrow$) Let $v$ be a 3-malleable vertex of $G$ and let $M_{1}$ be a
perfect matching of $G$. We are required to show that $\overline{M_{1}}$ (the
edge set of the complementary 2-factor of $M_{1}$) gives a Hamiltonian cycle.
Since $G$ contains a 3-malleable vertex, it is PMH, and so there exists a
perfect matching $M_{2}$ such that $M_{1}\cup M_{2}$ gives a Hamiltonian cycle
of $G$. Let $M_{3}=E(G)-(M_{1}\cup M_{2})$ and let $\partial
v=\\{e_{1},e_{2},e_{3}\\}$, such that $e_{i}\in M_{i}$, for each
$i\in\\{1,2,3\\}$. Since $v$ is 3-malleable, there exists a Hamiltonian cycle
of $G$ which extends $M_{3}$ and contains the edge $e_{2}$. Since $M_{1}\cup
M_{2}$ forms a Hamiltonian cycle and $(M_{1}\cup M_{2})\cap M_{3}=\emptyset$,
the only perfect matching of $G-M_{3}$ containing $e_{2}$ is $M_{2}$, and so
$M_{2}\cup M_{3}$ (which is equal to $\overline{M_{1}}$) forms a Hamiltonian
cycle, as required.

Since the vertex $u$ in the first part of the above proof was arbitrary, the
next result clearly follows.

######  Corollary 2.4.

Let $G$ be a cubic graph admitting a 3-malleable vertex. Then, $G$ is 2FH and
all its vertices are 3-malleable.

Consequently, Theorem 2.2 can be restated as follows: a cubic graph is 2FH if
and only if all its vertices are malleable. In other words, a cubic graph
either admits a 3-malleable vertex or not. Figure 1 depicts a perfect matching
of the cube $\mathcal{Q}_{3}$ which can only be extended to a Hamiltonian
cycle in exactly one way, and so, there is no vertex in $\mathcal{Q}_{3}$
which is 3-malleable. In fact, the cube is not 2FH (although it is PMH).

Figure 1: $\mathcal{Q}_{3}$ does not admit any 3-malleable vertex since the
dashed edges can be extended to a Hamiltonian cycle in exactly one way.

In general, if a cubic PMH-graph $G$ (not necessarily bipartite) admits a
perfect matching $M$ which extends to a Hamiltonian cycle in exactly one way
(that is, there exists a unique perfect matching $N$ for which $M\cup N$ gives
a Hamiltonian cycle), then the vertices of $G$ are not malleable, and so the
graph is not 2FH (by Theorem 2.2). The converse of this statement is also
true.

######  Lemma 2.5.

Let $G$ be a cubic PMH-graph (not necessarily bipartite). The graph $G$ is not
2FH if and only if it admits a perfect matching which can be extended to a
Hamiltonian cycle in exactly one way.

######  Proof 2.6.

By the comment prior to the statement of the lemma, it suffices to prove the
forward direction. Since $G$ is not 2FH, by Theorem 2.2, no vertex in $G$ is
malleable. Let $v\in V(G)$ and let $\partial v=\\{e_{1},e_{2},e_{3}\\}$. Since
$v$ is not malleable, there exists a perfect matching of $G$, say $M_{1}$,
such that for every perfect matching $M_{2}$ of $G$ for which $M_{1}\cup
M_{2}$ is a Hamiltonian cycle, $|M_{2}\cap(\partial v-M_{1})|=1$. Let $M_{2}$
be such a perfect matching and, without loss of generality, assume that
$e_{1}$ and $e_{2}$ belong to $M_{1}$ and $M_{2}$, respectively. Since
$M_{1}\cup M_{2}$ is a Hamiltonian cycle, $E(G)-(M_{1}\cup M_{2})$ is a
perfect matching, say $M_{3}$, containing the edge $e_{3}$. Since $G$ is PMH,
there exists a perfect matching $N$ of $G-M_{3}$, such that $N\cup M_{3}$ is a
Hamiltonian cycle of $G$. Since $G-M_{3}$ is a connected even cycle, the
perfect matching $N$ is either equal to $M_{1}$ or to $M_{2}$. By our
assumption, $N$ cannot be equal to $M_{1}$, because otherwise there exists a
Hamiltonian cycle extending $M_{1}$ which contains the edge $e_{3}$.
Therefore, $N$ must be equal to $M_{2}$. Consequently, $M_{3}$ is a perfect
matching of $G$ which can be extended to a Hamiltonian cycle of $G$ in exactly
one way.

Before proceeding, the following notions dealing with the cyclic connectivity
of a graph require defining. An edge-cut $X$ is said to be _cycle-separating_
if at least two components of $G-X$ contain cycles. A (connected) graph $G$ is
said to be cyclically $k$-edge-connected if $G$ admits no set with less than
$k$ edges which is cycle-separating. Consider once again Conjecture 1.2. As
stated in [8], a smallest counterexample to this conjecture must be cyclically
4-edge-connected (see [14]), and such a counterexample must have girth at
least 6 (see [13]). The authors state that to prove this conjecture it
suffices to show that the Heawood graph is the only bipartite cyclically
4-edge-connected cubic 2FH-graph of girth at least 6. However, thinking about
cubic 2FH-graphs through malleable vertices and Lemma 2.5 suggest another way
how one can look at Conjecture 1.2. In fact, a smallest counterexample to this
conjecture can be searched for in the class of bipartite cubic PMH-graphs
(recall that Conjecture 1.2 deals with bipartite cubic graphs). By Lemma 2.5,
Conjecture 1.2 of Funk _et al._ can be restated equivalently in terms of a
strictly weaker property than 2-factor Hamiltonicity: the PMH-property.

######  Conjecture 2.7.

Every bipartite cyclically 4-edge-connected cubic PMH-graph with girth at
least 6, except the Heawood graph, admits a perfect matching which can be
extended to a Hamiltonian cycle in exactly one way.

###  2.2 Non-cubic graphs admitting a malleable vertex

Even though Section 2.1 may suggest otherwise, the existence of a malleable
vertex in a graph does not necessarily imply that the graph is 2FH. In fact,
we note that for every $t>3$, there exists a $t$-regular graph whose vertices
are all $t$-malleable, but the graph itself is not 2FH (recall that in [8] it
was shown that there are no bipartite $t$-regular 2FH-graphs). Consider, for
example, the complete bipartite graphs $K_{t,t}$ for every $t>3$. Also, for
every odd $t>3$, the vertices of the complete graph $K_{t+1}$ are all
$t$-malleable, but the graph is not 2FH.

Graphs admitting a malleable vertex which are not 2FH are not necessarily
regular. In fact, consider the graph $\mathcal{Y}_{2n+1}$ obtained by adding a
new vertex $v_{0}$ to the complete graph $K_{2n+1}$, for some $n\geq 2$, such
that $v_{0}$ is adjacent to exactly three vertices of $K_{2n+1}$ (see Figure
2). Let $V(K_{2n+1})=\\{v_{1},\ldots,v_{2n+1}\\}$ and, without loss of
generality, let the neighbours of $v_{0}$ in $\mathcal{Y}_{2n+1}$ be
$v_{1},v_{2},v_{3}$. Then, the two disjoint cycles $(v_{0},v_{1},v_{2})$ and
$(v_{3},v_{4},\ldots,v_{2n+1})$ form a 2-factor, making the graph not 2FH. We
also claim that the vertex $v_{0}$ is a 3-malleable vertex. In fact, let $M$
be a perfect matching of $\mathcal{Y}_{2n+1}$ and, without loss of generality,
assume that $v_{0}v_{1}\in M$. If one can show that
$\mathcal{Y}_{2n+1}-v_{0}v_{2}$ and $\mathcal{Y}_{2n+1}-v_{0}v_{3}$ each admit
a Hamiltonian cycle extending $M$, then this would imply that $v_{0}$ is a
3-malleable vertex. We do this by utilising the following theorem.

######  Theorem 2.8 (Häggkvist, 1979 [11]).

Let $G$ be a graph, such that the order of $G$ is even and at least four. If
for each pair of non-adjacent vertices $u$ and $v$ we have
$\textrm{deg}(u)+\textrm{deg}(v)\geq|V(G)|+1$, then $G$ has the PMH-property.

Figure 2: The graph $\mathcal{Y}_{5}$.

In our case, the only pairs of vertices in the graph
$\mathcal{Y}_{2n+1}-v_{0}v_{2}$ which are not adjacent are $v_{0}$ and some
vertex $v$ from $\\{v_{2},v_{4},\ldots,v_{2n+1}\\}$. However,
$\textrm{deg}(v_{0})+\textrm{deg}(v)=2+2n=|V(\mathcal{Y}_{2n+1}-v_{0}v_{2})|+1$,
and so, by Theorem 2.8, $\mathcal{Y}_{2n+1}-v_{0}v_{2}$ is PMH. Consequently,
there exists a Hamiltonian cycle of $\mathcal{Y}_{2n+1}$ extending $M$ which
contains the edge $v_{0}v_{3}$. By a similar reasoning,
$\mathcal{Y}_{2n+1}-v_{0}v_{3}$ is PMH and so there exists a Hamiltonian cycle
of $\mathcal{Y}_{2n+1}$ extending $M$ which contains the edge $v_{0}v_{2}$.
Since $M$ was arbitrary, the vertex $v_{0}$ is 3-malleable.

The above construction also provides us with graphs which are not 2FH, admit a
malleable vertex, but not all of its vertices are as such (unlike even cycles
and cubic graphs). In fact, let $M$ be a perfect matching of
$\mathcal{Y}_{2n+1}$ containing the edges $v_{0}v_{1}$ and $v_{2}v_{3}$. Any
Hamiltonian cycle of $\mathcal{Y}_{2n+1}$ extending $M$ cannot contain
$v_{1}v_{2}$ or $v_{1}v_{3}$, and so, in particular, the vertex $v_{1}$ is not
$(2n+1)$-malleable.

Figure 3: The graph $\mathcal{B}_{3}$.

We can also obtain examples of graphs which are not 2FH and admit a malleable
vertex which are less dense (with respect to the number of edges) in the
following way. For every $n\geq 3$, let $\mathcal{B}_{n}$ be the bipartite
graph with partite sets $\\{u_{0},u_{1},\ldots,u_{n}\\}$ and
$\\{v_{0},v_{1},\ldots,v_{n}\\}$, such that
$E(\mathcal{B}_{n})=\\{u_{0}v_{1},u_{0}v_{2},u_{0}v_{3}\\}\cup\\{v_{0}u_{1},v_{0}u_{2},v_{0}u_{3}\\}\cup\\{u_{i}v_{j}:\textrm{
for any }i,j\in[n]\\}$, where $[n]=\\{1,\ldots,n\\}$. The graph
$\mathcal{B}_{n}$ is not 2FH because the cycles:

  1. (i)

$(u_{0},v_{1},u_{2},v_{2})$ and $(v_{0},u_{1},v_{3},u_{3})$, when $n=3$; and

  2. (ii)

$(u_{0},v_{1},u_{2},v_{2})$ and
$(v_{0},u_{1},v_{3},u_{4},v_{4},\ldots,v_{n},u_{3})$, when $n>3$,

form a 2-factor of $\mathcal{B}_{n}$, where, in particular, $v_{4}$ is
followed by $u_{5}$ when $n>4$. Next, we show that $\mathcal{B}_{n}$ is PMH
and that $u_{0}$ and $v_{0}$ are 3-malleable, for every $n\geq 3$. Let $M$ be
a perfect matching of $\mathcal{B}_{n}$, and without loss of generality,
assume that $\\{u_{0}v_{1},v_{0}u_{1}\\}\subset M$. Due to the symmetry of
$\mathcal{B}_{n}$, without loss of generality, we can further assume that
exactly one of the following occurs:

  1. (i)

$\\{u_{2}v_{2},u_{3}v_{3}\\}\subset M$;

  2. (ii)

$u_{2}v_{2}\in M$ and $u_{3}v_{3}\not\in M$; and

  3. (iii)

$u_{2}v_{2},u_{2}v_{3},u_{3}v_{3},u_{3}v_{2}$ do not belong to $M$.

We note that the last two instances only occur when $n>3$.

Let $M^{\prime}=M-\\{u_{0}v_{1},v_{0}u_{1}\\}$. The graph
$\mathcal{B}^{\prime}=\mathcal{B}_{n}-\\{u_{0},u_{1},v_{0},v_{1}\\}$ is
isomorphic to the complete bipartite graph $K_{n-1,n-1}$ and $M^{\prime}$ is
one of its perfect matchings. Since every vertex in $\mathcal{B}^{\prime}$ is
$(n-1)$-malleable, there exist Hamiltonian cycles $H_{1}^{\prime}$ and
$H_{2}^{\prime}$ of $\mathcal{B}^{\prime}$, both extending $M^{\prime}$ in
such a way that $u_{2}v_{3}\in E(H_{1}^{\prime})$ and $u_{3}v_{2}\in
E(H_{2}^{\prime})$. In the first case, the following set of edges gives a
Hamiltonian cycle of $\mathcal{B}_{n}$ which extends $M$ and contains
$u_{2}v_{0}$ and $u_{0}v_{3}$:
$\left(E(H_{1}^{\prime})-\\{u_{2}v_{3}\\}\right)\cup\\{u_{2}v_{0},v_{0}u_{1},u_{1}v_{1},v_{1}u_{0},u_{0}v_{3}\\}$.
In the second case,
$\left(E(H_{2}^{\prime})-\\{u_{3}v_{2}\\}\right)\cup\\{u_{3}v_{0},v_{0}u_{1},u_{1}v_{1},v_{1}u_{0},u_{0}v_{2}\\}$
is the edge set of a Hamiltonian cycle of $\mathcal{B}_{n}$ which extends $M$
and contains $u_{3}v_{0}$ and $u_{0}v_{2}$. Hence, $u_{0}$ and $v_{0}$ are
both 3-malleable. We note that the 3-malleability of $u_{0}$ and $v_{0}$
cannot be proved by using Las Vergnas’ Theorem [15], and that Theorem 2 in
[18] can only be used for the cases when $n=3$ or $4$. Furthermore, the graph
$\mathcal{B}_{n}$ can be turned into a non-bipartite non-regular graph which
is not 2FH and admits a 3-malleable vertex by adding the edge $v_{n-1}v_{n}$.

Finally, we also remark that if a graph is 2FH, it does not mean that all its
vertices are malleable (as in the case of even cycles and cubic graphs). An
example of such a graph is $K_{3,3}$ with an edge $e$ added between two
vertices of the same partite set—we denote this graph by $K_{3,3}+e$. Since
there is no perfect matching of $K_{3,3}+e$ which contains $e$, the graph
$K_{3,3}+e$ is 2FH (since $K_{3,3}$ is 2FH). However, the endvertices of the
edge $e$ are not 4-malleable.

The reason why the construction of the graphs $\mathcal{B}_{n}$ and
$\mathcal{Y}_{2n+1}$ was given is because the two classes of graphs contain
3-malleable vertices and so can be used in the general results proven in
Section 3.2 to obtain PMH-graphs with arbitrarily large maximum degree by
using star products.

##  3 Star products and PMH-graphs

In this section, we study what happens when we look at star products between
PMH-graphs which are not necessarily bipartite and 2FH as in [8]. We find
general ways how one can obtain PMH-graphs (not necessarily cubic) from
smaller graphs by using star products. This is done by the help of malleable
vertices. Although there is a clear connection between 2FH-graphs and PMH-
graphs, an analogous result to Proposition 1.1 for PMH-graphs is not possible,
as the following section on cubic graphs shows.

###  3.1 Cubic graphs revisited

######  Proposition 3.1.

Let $G_{1}$ and $G_{2}$ be two cubic graphs, and let $u\in V(G_{1})$ and $v\in
V(G_{2})$.

  1. (i)

If $G_{1}(u)*G_{2}(v)$ is PMH, then $G_{1}$ and $G_{2}$ are PMH.

  2. (ii)

The converse of (i) is not true.

######  Proof 3.2.

(i) First assume that $G_{1}(u)*G_{2}(v)$ is PMH and let
$X=\\{u_{1}v_{1},u_{2}v_{2},u_{3}v_{3}\\}$ be the principal $3$-edge-cut of
$G_{1}(u)*G_{2}(v)$, where $u_{1},u_{2},u_{3}$ are the neighbours of $u$ in
$G_{1}$, and $v_{1},v_{2},v_{3}$ are the neighbours of $v$ in $G_{2}$. Let $M$
be a perfect matching of $G_{1}$, and without loss of generality, assume that
$u_{1}u\in M$. Let $M^{\prime}$ be a perfect matching of $G_{1}(u)*G_{2}(v)$
containing $u_{1}v_{1}$ and $M-\\{u_{1}u\\}$. We remark that such a perfect
matching exists, since, in particular, every edge of a bridgeless cubic graph
is contained in a perfect matching (see [17]). Furthermore, since
$G_{1}(u)*G_{2}(v)$ is PMH, $M^{\prime}$ (and every other perfect matching of
this graph) intersects $X$ in exactly one edge, and there exists a Hamiltonian
cycle $H$ of $G_{1}(u)*G_{2}(v)$ extending $M^{\prime}$ and containing exactly
one of the edges $u_{2}v_{2}$ and $u_{3}v_{3}$. Assume $u_{2}v_{2}\in E(H)$.
This means that $H$ induces a path in $G_{1}$ having end-vertices $u_{1}$ and
$u_{2}$, passes through all the vertices in $V(G_{1})-\\{u\\}$ and contains
$M-\\{u_{1}u\\}$. This path together with the edges $u_{1}u$ and $u_{2}u$
forms a Hamiltonian cycle of $G_{1}$ extending $M$. Hence, $G_{1}$ is PMH, and
by a similar reasoning, one can show that $G_{2}$ is also PMH.

(ii) Let $G_{1}$ and $G_{2}$ be two copies of the cube, and let $u\in
V(G_{1})$ and $v\in V(G_{2})$. Both $G_{1}$ and $G_{2}$ are PMH (by [6]), but
$G_{1}(u)*G_{2}(v)$ is not. In fact, consider the perfect matching of
$G_{1}(u)*G_{2}(v)$ shown in Figure 4. One can clearly see that it cannot be
extended to a Hamiltonian cycle.

Figure 4: A star product between two copies of the cube. The dashed edges
cannot be extended to a Hamiltonian cycle.

The second part of the above proof shows that unlike Proposition 1.1, a star
product between two bipartite PMH-graphs does not guarantee that the resulting
graph is PMH.

######  Corollary 3.3.

If $G$ is a cubic PMH-graph having a $3$-edge-cut, then $G$ can be obtained by
an appropriate star product between two cubic PMH-graphs $G_{1}$ and $G_{2}$.

The above corollary (and also Conjecture 2.7) are the main reasons why in [2],
the study of cubic graphs which are PMH or just even-2-factorable was
restricted to graphs having girth at least $4$. In [2], a graph $G$ is defined
to be _even-2-factorable_ (for short E2F) if each of its 2-factors consist
only of even cycles. When $G$ is cubic, $G$ is E2F if and only if each of its
perfect matchings can be extended to a 3-edge-colouring. We note that if a
cubic graph is PMH then it is even-2-factorable as well, but the converse is
not necessarily true. As in Corollary 3.3, a cubic graph having girth 3 which
is also even-2-factorable (not necessarily PMH), can be obtained by applying a
star product between an even-2-factorable cubic graph and the complete graph
$K_{4}$. Applying a star product between a graph and $K_{4}$ is also known as
applying a $Y$-extension, which can be seen as expanding a vertex into a
triangle (see Figure 5). We remark that the results given in the sequel do not
necessarily yield PMH-graphs having girth 3, as Remark 3.12 shows.

Figure 5: $Y$-extension.

Despite the discouraging statement of Proposition 3.1, one can still obtain
PMH-graphs from smaller PMH-graphs by using a star product (or repeated star
products) and 3-malleable vertices, as we shall see in the following section.

###  3.2 Obtaining PMH-graphs from smaller graphs

Before proceeding we give the following definition. Following the notation in
[16], an edge-cut in a graph $G$ admitting a perfect matching is said to be
_tight_ if every perfect matching of $G$ intersects it in exactly one edge
(not necessarily the same).

######  Lemma 3.4.

Let $G_{1}$ be a PMH-graph admitting a vertex $u$ of degree 3 and let $G_{2}$
be a graph admitting a 3-malleable vertex $v$. The principal $3$-edge-cut of
$G_{1}(u)*G_{2}(v)$ is tight if and only if $G_{1}(u)*G_{2}(v)$ is PMH.

######  Proof 3.5.

Since any 3-edge-cut in a PMH-graph is tight it suffices to prove the forward
direction. Let $X=\\{u_{1}v_{1},u_{2}v_{2},u_{3}v_{3}\\}$ be the principal
$3$-edge-cut of $G_{1}(u)*G_{2}(v)$, and assume that $X$ is tight. Let $M$ be
a perfect matching of $G_{1}(u)*G_{2}(v)$, and let $u_{1},u_{2},u_{3}$ and
$v_{1},v_{2},v_{3}$, be the neighbours of $u\in V(G_{1})$ and $v\in V(G_{2})$,
respectively. Without loss of generality, assume that $M\cap
X=\\{u_{1}v_{1}\\}$. Consequently, $M$ respectively induces perfect matchings
$M_{1}$ and $M_{2}$ in $G_{1}$ and $G_{2}$, such that $u_{1}u\in M_{1}\subset
E(G_{1})$, $v_{1}v\in M_{2}\subset E(G_{2})$, $M_{1}-\\{u_{1}u\\}\subset M$
and $M_{2}-\\{v_{1}v\\}\subset M$. Since $G_{1}$ is PMH, $M_{1}$ can be
extended to a Hamiltonian cycle $H_{1}$ of $G_{1}$. Without loss of
generality, we assume that $u_{2}u\in E(H_{1})$. Since $v$ is a 3-malleable
vertex, $M_{2}$ can be extended to a Hamiltonian cycle $H_{2}$ of $G_{2}$
whose edge set intersects $v_{2}v$. Consequently,
$(E(H_{1})-\\{u_{1}u,u_{2}u\\})\cup(E(H_{2})-\\{v_{1}v,v_{2}v\\})\cup\\{u_{1}v_{1},u_{2}v_{2}\\}$
is a Hamiltonian cycle of $G_{1}(u)*G_{2}(v)$ extending $M$, as required.

This lemma shall be needed in the sequel when considering star products
between PMH-graphs. The graph $G_{1}$ (similarly $G_{2}$) in Lemma 3.4 can
either be bipartite or not, and in what follows we shall consider star
products in two instances:

  1. (i)

between bipartite PMH-graphs (Section 3.2.1); and

  2. (ii)

between PMH-graphs with at least one being non-bipartite (Section 3.2.2).

####  3.2.1 Star products between bipartite PMH-graphs

Whilst a star product between two bipartite 2FH-graphs yields a 2FH-graph,
Figure 4 shows that a star product between two bipartite PMH-graphs is not
necessarily PMH. The example given in the figure is a star product between two
copies of $\mathcal{Q}_{3}$, where the graph $\mathcal{Q}_{3}$ is itself PMH,
but does not admit any 3-malleable vertex. The following proposition shows
that the presence of a 3-malleable vertex in at least one of the two graphs
between which a star product is applied guarantees the PMH-property in the
resulting graph, given that at least one of the two initial graphs is
bipartite.

######  Proposition 3.6.

Let $G_{1}$ be a PMH-graph admitting a vertex $u$ of degree 3 and let $G_{2}$
be a graph admitting a 3-malleable vertex $v$. If at least one of $G_{1}$ and
$G_{2}$ is bipartite, then $G_{1}(u)*G_{2}(v)$ is PMH.

######  Proof 3.7.

Since at least one of $G_{1}$ and $G_{2}$ is bipartite, the principal
$3$-edge-cut of $G_{1}(u)*G_{2}(v)$ is tight. Result follows by Lemma 3.4.

######  Corollary 3.8.

Let $G_{1}$ and $G_{2}$ be two bipartite graphs having the PMH-property such
that $u$ is a vertex of degree 3 in $G_{1}$ and $v$ is a 3-malleable vertex in
$G_{2}$. Then, $G_{1}(u)*G_{2}(v)$ is a bipartite PMH-graph.

We can extend the above corollary further. Let $G_{0}$ be a bipartite PMH-
graph admitting $2$ vertices of degree 3, say $u_{1}$ and $u_{2}$.
Furthermore, let $G_{1}$ and $G_{2}$ be bipartite PMH-graphs each admitting a
3-malleable vertex, say $v_{1}\in V(G_{1})$ and $v_{2}\in V(G_{2})$. By the
previous theorem, $G_{0}(u_{1})*G_{1}(v_{1})$ is PMH. This graph is also
bipartite, and so, reapplying a star product on the vertex corresponding to
$u_{2}$ in $G_{0}(u_{1})*G_{1}(v_{1})$ and the vertex $v_{2}$ in $G_{2}$ gives
a bipartite PMH-graph once again (by Corollary 3.8). For simplicity, we shall
say that the resulting graph has been obtained by applying a star product on
$u_{i}$ and $v_{i}$, for each $i\in\\{1,2\\}$. By repeating this argument we
can state the following more general result.

######  Theorem 3.9.

Let $G_{0}$ be a bipartite PMH-graph admitting $t$ vertices of degree 3, for
some $t\in\\{1,\ldots,|V(G_{0})|\\}$, say $u_{1},\ldots,u_{t}$. Let
$\mathcal{I}\subseteq\\{i:\textrm{deg}(u_{i})=3\\}$. For each
$i\in\mathcal{I}$, let $G_{i}$ be a bipartite graph admitting a 3-malleable
vertex $v_{i}$. The bipartite graph obtained by applying a star product on
$u_{i}$ and $v_{i}$, for each $i\in\mathcal{I}$, is PMH.

We remark that Theorem 3.9 is best possible, in the sense that we cannot
exchange the roles of the $u_{i}$s and the $v_{i}$s. In fact, if we assume
that the $t$ vertices $u_{1},\ldots,u_{t}$ of $G_{0}$ are 3-malleable, and
that, for each $i\in\mathcal{I}$, the graphs $G_{i}$ are PMH-graphs with the
vertex $v_{i}$ being just a degree 3 vertex (and not 3-malleable), the same
conclusion about the resulting graph cannot be obtained, as the following
example in the class of cubic graphs shows. Let $G_{0}$ be the graph
$K_{3,3}$, and let $G_{1}$ and $G_{2}$ be two copies of the graph
$\mathcal{Q}_{3}$. Let $u_{1}$ and $u_{2}$ be two vertices in $G_{0}$
belonging to the same partite set, and let $v_{1}\in V(G_{1})$ and $v_{2}\in
V(G_{2})$. By Corollary 3.8, $G_{0}(u_{1})*G_{1}(v_{1})$ is PMH. However,
reapplying a star product on the vertex corresponding to $u_{2}$ in
$G_{0}(u_{1})*G_{1}(v_{1})$ and the vertex $v_{2}$ of $G_{2}$ (that is, the
final graph is obtained by applying a star product on $u_{i}$ and $v_{i}$, for
each $i\in\\{1,2\\}$) does not yield a PMH-graph. Indeed, the dashed perfect
matching portrayed in Figure 6 cannot be extended to a Hamiltonian cycle.

Figure 6: The dashed edges cannot be extended to a Hamiltonian cycle.

The absence of 3-malleable vertices in $\mathcal{Q}_{3}$ ($G_{1}$ and $G_{2}$)
does not help in obtaining a resulting PMH-graph, even though the vertices of
$K_{3,3}$ ($G_{0}$) are all 3-malleable, and all three graphs ($G_{0}$,
$G_{1}$ and $G_{2}$) are PMH and bipartite. We thus move onto the next section
and look at a star product between two PMH-graphs with at least one being non-
bipartite.

####  3.2.2 Star products between PMH-graphs with at least one being non-
bipartite

In Section 3.2.1, Proposition 3.6 already tells us that a star product between
two PMH-graphs with exactly one being bipartite results in a PMH-graph (given
that one of them admits a 3-malleable vertex). But what happens when both are
non-bipartite? As already stated before, the graph obtained after applying a
star product between two copies of the complete graph $K_{4}$ is not PMH, even
though the graphs we started with, that is, the two copies of $K_{4}$, are
both PMH. Given that $K_{4}$ is also 2FH, the previous example tells us that
the presence of 3-malleable vertices alone does not guarantee the PMH-property
in the resulting graph when both the PMH-graphs we start with are non-
bipartite. In order to attain a general result about PMH-graphs obtained by
applying a star product between two non-bipartite PMH-graphs, we extend
Proposition 3.6 in a similar way as in Theorem 3.9.

######  Theorem 3.10.

Let $G_{0}$ be a bipartite PMH-graph of order $2n$ and with bipartition
$U=\\{u_{i}:i\in[n]\\}$ and $V=\\{v_{i}:i\in[n]\\}$, for some $n>1$. Let
$\mathcal{I}\subseteq\\{i:\textrm{deg}(v_{i})=3\\}$. For each
$i\in\mathcal{I}$, let $G_{i}$ be a graph admitting a 3-malleable vertex
$z_{i}$. The resulting graph $G$ obtained by applying a star product on
$v_{i}$ and $z_{i}$, for each $i\in\mathcal{I}$, is PMH.

######  Proof 3.11.

For each $i\in\mathcal{I}$, let $X_{i}$ be the (principal) $3$-edge-cut of $G$
arising from a star product on $v_{i}$ and $z_{i}$. This means that if $e\in
X_{i}$, then one of the endvertices of $e$ belongs to $U$ and the other
endvertex belongs to $V(G_{i}-z_{i})$. If $\mathcal{I}=\emptyset$, then $G$ is
equal to $G_{0}$, and consequently, $G$ is PMH. So we can assume that
$\mathcal{I}\neq\emptyset$. Let $M$ be a perfect matching of $G$, and let
$E_{\mathcal{I}}$ be the collection of edges in $M$ having one endvertex in
$U$ and one endvertex in some $V(G_{i}-z_{i})$, for $i\in\mathcal{I}$. Since
$G_{0}$ is bipartite, each $X_{i}$ is tight, and so, $|M\cap X_{i}|=1$ for
each $i\in\mathcal{I}$. Consequently, $|E_{\mathcal{I}}|=|\mathcal{I}|$. Let
$E_{\mathcal{I}}=\\{e_{i}:i\in\mathcal{I}\\}$, such that for each
$i\in\mathcal{I}$, $e_{i}=x_{i}y_{i}$ for some $x_{i}\in\mathcal{U}$ and
$y_{i}\in V(G_{i}-z_{i})$. Moreover, for every $i\in\mathcal{I}$, let
$f_{i}=x_{i}v_{i}$. The set of edges $M_{0}=\\{f_{i}:i\in\mathcal{I}\\}\cup
M-\left(E_{\mathcal{I}}\bigcup\cup_{i\in\mathcal{I}}E(G_{i}-z_{i})\right)$ is
a perfect matching of $G_{0}$, and since $G_{0}$ is PMH, there exists a
Hamiltonian cycle $H_{0}$ of $G_{0}$ extending $M_{0}$. Without loss of
generality, assume that $H_{0}$ is equal to
$(u_{1},v_{1},u_{2},\ldots,v_{n})$, where $u_{2}$ is followed by $v_{2}$, and
$v_{n}$ is preceded by $u_{n}$. Without loss of generality, assume further
that $M_{0}=\\{u_{i}v_{i}:i\in[n]\\}$. In particular, this implies that for
each $i\in\mathcal{I}$, $x_{i}=u_{i}$.

Before continuing, we remark that operations in the indices of the vertices
$u_{i}$ are taken modulo $n$, with complete residue system $\\{1,\ldots,n\\}$.
Let $j\in\mathcal{I}$, and let the neighbours of $u_{j}$ and $u_{j+1}$
belonging to $V(G_{j}-z_{j})$ be $\alpha_{j}$ and $\omega_{j}$. We note that
$\alpha_{j}$ is equal to what we previously denoted by $y_{j}$. Given that
$z_{j}$ is a 3-malleable vertex of $G_{j}$, there exists a Hamiltonian cycle
$H_{j}$ of $G_{j}$ extending the perfect matching $\left(M\cap
E(G_{j}-z_{j})\right)\cup\\{z_{j}\alpha_{j}\\}$, such that $z_{j}\alpha_{j}$
and $z_{j}\omega_{j}$ belong to $E(H_{j})$. Let $P_{j}$ be the path obtained
after deleting the vertex $z_{j}$ from the cycle $H_{j}$. This process is
repeated for every other integer in $\mathcal{I}$. We note that $\alpha_{j}$
and $\omega_{j}$ are the endvertices of $P_{j}$, and, in particular, by our
assumption on $M_{0}$, we have $u_{j}\alpha_{j}\in M$, for every
$j\in\mathcal{I}$. By recalling that the edge set of the Hamiltonian cycle
$H_{0}$ is $\cup_{i=1}^{n}\\{u_{i}v_{i},v_{i}u_{i+1}\\}$ and the above
considerations, one can deduce that the following edge set induces a
Hamiltonian cycle of $G$ extending $M$:

$\cup_{i\in[n]-\mathcal{I}}\\{u_{i}v_{i},v_{i}u_{i+1}\\}\bigcup\cup_{j\in\mathcal{I}}\left(\\{u_{j}\alpha_{j},\omega_{j}u_{j+1}\\}\cup
E(P_{j})\right),$

as required.

When $|\mathcal{I}|>1$, say $|I|=2$, and $G_{1}$ and $G_{2}$ are chosen to be
non-bipartite, the above theorem shows that there do exist non-bipartite
graphs such that when a star product is applied between them, the resulting
graph is PMH. This follows because the graph obtained after appropriately
applying a star product between $G$ and $G_{1}$ is non-bipartite.

We also remark that the reason why we cannot apply a star product on two
adjacent vertices in $G$ is because the resulting graph is not necessarily
PMH, as Figure 7 shows. In fact, applying a $Y$-extension to two adjacent
vertices of $K_{3,3}$ results in a graph which does not have the PMH-property.
Recall that $Y$-extensions can be explained in terms of a star product between
a graph and $K_{4}$

Figure 7: The dashed edges cannot be extended to a Hamiltonian cycle.

####  3.2.3 Examples of cubic PMH-graphs having small order

In [2], it is stated that the papillon graph on 8 vertices is the smallest
(with respect to the number of vertices) non-bipartite cubic graph with girth
at least 4 which is even-2-factorable (E2F) and not PMH (recall that if a
cubic graph is PMH then it is E2F). However, there are other non-bipartite
cubic graphs on 4, 6, or 8 vertices which are PMH, and consequently E2F—these
have girth strictly less than 4. Apart from $K_{4}$, there is another cubic
graph on 4 vertices which is PMH. Let $G$ be the unique bipartite cubic graph
on 4 vertices (see Figure 8). The graph $G$ is PMH, and by using the procedure
outlined in Theorem 3.10, with $G_{0}=G$, $\mathcal{I}=\\{1,2\\}$ and
$G_{1}=G_{2}=K_{4}$, we obtain a non-bipartite cubic PMH-graph on 8 vertices.
This is equivalent to applying a $Y$-extension to two vertices belonging to
the same partite set of $G$. Note that applying a $Y$-extension to a single
vertex in $G$ also gives a PMH-graph, which is the unique non-bipartite cubic
PMH-graph on 6 vertices (the second graph in Figure 8).

Figure 8: Using Theorem 3.10 to obtain non-bipartite cubic PMH-graphs.

Having said this, the graphs obtained by the methods given in the previous
sections do not necessarily have girth 3, as the following remark shows.

######  Remark 3.12.

An easy way to obtain cubic PMH-graphs with girth at least $4$ is the
following. Let $F$ be the graph obtained by applying a $Y$-extension to a
bipartite cubic 2FH-graph $F_{0}$ (see, for example, Figure 9). Let $G$ be a
bipartite cubic PMH-graph having no multiedges and let $v$ be a vertex of $F$
lying on its triangle. Since $F$ is a cubic 2FH-graph, $v$ is 3-malleable, and
so, for any $u\in V(G)$, the graph $G(u)*F(v)$ is PMH by Proposition 3.6.
Moreover, $G(u)*F(v)$ has girth $4$. In fact, $G$ and $F_{0}$ do not have any
multiedges and, since they are both bipartite, a cycle of length $3$ in
$G(u)*F(v)$ can only occur if the edges of the cycle intersect (twice) the
principal $3$-edge-cut of $G(u)*F(v)$, which is impossible.

Figure 9: Applying a $Y$-extension to $F_{0}=K_{3,3}$ from Remark 3.12.

Graphs obtained using this method are not necessarily 2FH. In fact, by letting
$G=Q_{3}$ and $F_{0}=K_{3,3}$, the resulting graph depicted in Figure 10 is
not 2FH, since the complementary 2-factor of the dashed perfect matching does
not form a Hamiltonian cycle.

Figure 10: A non-bipartite cubic PMH-graph having girth $4$ which is not 2FH.

Although the above examples are cubic, we recall that the results in Section
3.2 can generate PMH-graphs (both bipartite and not) with arbitrarily large
maximum degree. This can be done by using graphs admitting a 3-malleable
vertex as the ones portrayed after the proof of Theorem 2.2 in Section 1.

We also remark that despite the encouraging general methods obtained above,
there are PMH-graphs admitting a 3-edge-cut, that is, obtained by using a star
product (see Corollary 3.3), which cannot be described by the methods
portrayed so far. Such an example is given in Figure 11. The graph denoted by
$G_{1}*G_{2}$ (obtained by an appropriate star product on $u\in V(G_{1})$ and
$v\in V(G_{2})$) is PMH. The graphs $G_{1}$ (bipartite) and $G_{2}$ (non-
bipartite) are both PMH-graphs as well, however, $G_{1}$ and $G_{2}$ do not
have any 3-malleable vertices and so, the reason why the resultant graph is
PMH is not because of the above results, in particular, Theorem 3.10 (see also
Lemma 3.4).

Figure 11: The graphs $G_{1}$, $G_{2}$ and $G_{1}*G_{2}$ are all PMH.

The three graphs given in Figure 11 contain 2-edge-cuts which we discuss in
the next section with regards to PMH- and 2FH-graphs. In particular, although
the PMH-property in the third graph given in Figure 11 cannot be explained by
the previous theorems dealing with the star product, the reason behind it
being PMH can be explained by Theorem 4.1 which gives a necessary and
sufficient condition for a graph admitting a 2-edge-cut to be PMH.

##  4 2-edge-cuts in PMH- and 2FH-graphs

Let $G_{1}$ and $G_{2}$ be two graphs (not necessarily regular), and let
$e_{1}$ and $e_{2}$ be two edges such that $e_{1}=x_{1}y_{1}\in E(G_{1})$ and
$e_{2}=x_{2}y_{2}\in E(G_{2})$. A _$2$ -cut connection_ on $e_{1}$ and $e_{2}$
is a graph operation that consists of constructing the new graph
$(G_{1}-e_{1})\cup(G_{2}-e_{2})\cup\\{x_{1}x_{2},y_{1}y_{2}\\}$, and denoted
by $G_{1}(x_{1}y_{1})\\#G_{2}(x_{2}y_{2})$. The $2$-edge-cut
$\\{x_{1}x_{2},y_{1}y_{2}\\}$ is referred to as the _principal $2$-edge-cut_
of the resulting graph. It is clear that another possible graph obtained by a
2-cut connection on $e_{1}$ and $e_{2}$ is
$G_{1}(x_{1}y_{1})\\#G_{2}(y_{2}x_{2})$. Unless otherwise stated, if it is not
important which of these two graphs is obtained, we use the notation
$G_{1}(e_{1})\\#G_{2}(e_{2})$ and we say that it is a graph obtained by a
$2$-cut connection on $e_{1}$ and $e_{2}$. As in the case of star products,
when this occurs, we say that the resulting graph has been obtained by
applying a 2-cut connection _between_ $G_{1}$ and $G_{2}$. Given that graphs
on an odd number of vertices do not admit a perfect matching, they cannot be
studied with regards to the PMH-property. Since we shall be looking at the
PMH-property of $G_{1}(e_{1})\\#G_{2}(e_{2})$, $|V(G_{1})|$ and $|V(G_{2})|$
are either both odd or both even. This is the reason why in the next theorem
we shall assume that the graphs $G_{1}$ and $G_{2}$ are both of even order, as
we are not only interested in whether $G_{1}(e_{1})\\#G_{2}(e_{2})$ admits the
PMH-property, but also whether $G_{1}$ and $G_{2}$ admit it.

######  Theorem 4.1.

Let $G=G_{1}(e_{1})\\#G_{2}(e_{2})$ be a graph obtained by applying a 2-cut
connection on $e_{1}\in E(G_{1})$ and $e_{2}\in E(G_{2})$, such that $G_{1}$
and $G_{2}$ are of even order. Then, $G$ is PMH if and only if, for each
$i\in\\{1,2\\}$, every perfect matching in $G_{i}$ can be extended to a
Hamiltonian cycle of $G_{i}$ which contains $e_{i}$.

######  Proof 4.2.

($\Rightarrow$) Let $e_{1}=x_{1}y_{1}$ and $e_{2}=x_{2}y_{2}$ be such that the
principal 2-edge-cut of $G$ is $X=\\{x_{1}x_{2},y_{1}y_{2}\\}$, and let
$M_{1}$ be a perfect matching of $G_{1}$. Since $G$ is PMH, $G$ contains a
perfect matching $M$, such that $M_{1}-\\{e_{1}\\}\subset M$, and, in
particular, there exists a perfect matching $N$ of $G$ such that $M\cup N$
gives a Hamiltonian cycle of $G$. If $e_{1}\in M_{1}$, then $X\subset M$ and
$N\cap X=\emptyset$. Consequently, the set of edges $N_{1}=N\cap E(G_{1})$ is
a perfect matching of $G_{1}$, and $M_{1}\cup N_{1}$ gives a Hamiltonian cycle
of $G_{1}$ containing $e_{1}$. Otherwise, if $e_{1}\not\in M_{1}$, then $M\cap
X=\emptyset$ and $X\subset N$. Consequently, the set of edges
$N_{1}=\left(N\cap E(G_{1})\right)\cup\\{e_{1}\\}$ is a perfect matching of
$G_{1}$, and $M_{1}\cup N_{1}$ gives a Hamiltonian cycle of $G_{1}$ containing
$e_{1}$, once again. By a similar argument one can show that every perfect
matching of $G_{2}$ can be extended to a Hamiltonian cycle of $G_{2}$
containing $e_{2}$.

($\Leftarrow$) Conversely, assume that $M$ is a perfect matching of $G$.
Notwithstanding whether $M$ contains the edges in
$X=\\{x_{1}x_{2},y_{1}y_{2}\\}$ or not, $M$ induces two perfect matchings
$M_{1}\in E(G_{1})$ and $M_{2}\in E(G_{2})$ such that
$M_{i}-\\{e_{i}\\}\subset M$, for each $i\in\\{1,2\\}$. Let $i\in\\{1,2\\}$.
Note that $M\cap X=X$ if and only if $e_{i}\in M_{i}$. By our assumption,
$G_{i}$ admits a Hamiltonian cycle $H_{i}$ which extends $M_{i}$ and contains
$e_{i}$, and so, since $G_{i}$ is of even order, it admits a perfect matching
$N_{i}$ such that $M_{i}\cup N_{i}=E(H_{i})$. Consequently, the edge set
$M_{1}\cup N_{1}\cup M_{2}\cup N_{2}\cup X-\\{e_{1},e_{2}\\}$ gives a
Hamiltonian cycle of $G$ containing $M$. Thus, $G$ is PMH as required.

The above theorem explains the reason behind the PMH-property in all the three
graphs shown in Figure 11, not only the third. The graph $G_{1}$ is obtained
by applying a 2-cut connection between two copies of the cubic graph on two
vertices. The graph $G_{2}$ is obtained by applying a 2-cut connection between
the cubic graph on two vertices and the graph $K_{4}$. The third graph denoted
by $G_{1}*G_{2}$ in Figure 11 is obtained by applying an appropriate 2-cut
connection between the cubic graph on two vertices and the graph $G_{2}$.

We also note that the condition in Theorem 4.1 that every perfect matching in
$G_{i}$ has to be extended to a Hamiltonian cycle of $G_{i}$ containing the
edge $e_{i}$ is required because, for example, a 2-cut connection between the
cube $\mathcal{Q}_{3}$ (which is PMH) and any other appropriate PMH-graph does
not yield a PMH-graph, since any perfect matching of the resulting graph
containing the dashed edges cannot be extended to a Hamiltonian cycle, as can
be seen in Figure 12.

Figure 12: A perfect matching containing the dashed edges cannot be extended
to a Hamiltonian cycle.

Next, we give a similar result to Theorem 4.1 but for 2FH-graphs. Before
proceeding we note that, in general, if every 2-factor of a graph $G$ is a
Hamiltonian cycle containing a particular edge $e\in E(G)$, then every
2-factor of $G$ containing $e$ is a Hamiltonian cycle. However, the converse
of this statement is not necessarily true, because $G$ can admit 2-factors
which do not contain the edge $e$. An example of such a graph is $K_{3,3}$.

######  Theorem 4.3.

Let $G_{1}$ and $G_{2}$ be two graphs such that $e_{1}\in E(G_{1})$ and
$e_{2}\in E(G_{2})$. The graph $G=G_{1}(e_{1})\\#G_{2}(e_{2})$ is 2FH if and
only if we have that every 2-factor of $G_{1}$ is a Hamiltonian cycle
containing $e_{1}$ and every 2-factor of $G_{2}$ containing $e_{2}$ is a
Hamiltonian cycle (or vice-versa).

######  Proof 4.4.

($\Rightarrow$) Let the principal 2-edge-cut of $G$ be $X$. Since $G$ is 2FH,
we cannot have that both $G_{1}$ and $G_{2}$ admit a 2-factor $F_{1}$ and
$F_{2}$, respectively, such that $e_{1}\not\in E(F_{1})$ and $e_{2}\not\in
E(F_{2})$, because otherwise, $F_{1}\cup F_{2}$ is a 2-factor of $G$ which
does not intersect its principal 2-edge-cut, and so is not a Hamiltonian
cycle. We proceed by considering two cases. First consider the case when every
2-factor of $G_{i}$ contains $e_{i}$, for each $i\in\\{1,2\\}$. Let
$i\in\\{1,2\\}$. We claim that every 2-factor of $G_{i}$ is a Hamiltonian
cycle containing $e_{i}$ (and consequently, every 2-factor of $G_{i}$
containing $e_{i}$ is a Hamiltonian cycle). For, suppose not, and let $F_{i}$
be a 2-factor of $G_{i}$ which is not a Hamiltonian cycle. In particular, let
$C$ be a component of $F_{i}$ not intersecting $e_{i}$. Since $F_{i}$ is a
2-factor, $C$ is a cycle. As a result, $F_{1}\cup F_{2}\cup
X-\\{e_{1},e_{2}\\}$ is a 2-factor of $G$ containing the cycle $C$, implying
that $G$ admits a 2-factor which is not a Hamiltonian cycle, a contradiction.
Therefore, every 2-factor of $G_{i}$ is a Hamiltonian cycle containing
$e_{i}$.

Secondly, we consider the case when exactly one of the $G_{i}$s admits a
2-factor which does not contain $e_{i}$. Without loss of generality, assume
that $G_{2}$ admits such a 2-factor, that is, a 2-factor which does not
contain $e_{2}$. Since $G$ is 2FH, $G_{2}$ must also admit a 2-factor $F_{2}$
containing $e_{2}$. We claim that $F_{2}$ must be a Hamiltonian cycle. For,
suppose not, and let $C$ be a component (a cycle) of $F_{2}$ such that
$e_{2}\not\in E(C)$. On the other hand, let $F_{1}$ be a 2-factor of $G_{1}$
containing $e_{1}$. This means that $F_{1}\cup F_{2}\cup X-\\{e_{1},e_{2}\\}$
is a 2-factor of $G$ containing the cycle $C$, implying that $G$ admits a
2-factor which is not a Hamiltonian cycle, a contradiction. Therefore, every
2-factor of $G_{2}$ containing $e_{2}$ is a Hamiltonian cycle. Since $G_{1}$
cannot admit a 2-factor not containing $e_{1}$, every 2-factor of $G_{1}$ must
contain $e_{1}$, and must also be a Hamiltonian cycle, given that $G$ is 2FH.
Thus, every 2-factor of $G_{1}$ is a Hamiltonian cycle containing $e_{1}$.

($\Leftarrow$) Consider a 2-factor $F$ of $G$. Due to the condition on
$G_{1}$, any 2-factor of $G$ must contain the principal 2-edge-cut of $G$,
because otherwise, this would create a 2-factor in $G_{1}$ not containing the
edge $e_{1}$, a contradiction. Thus, $X\subset E(F)$. Suppose that $F$ is not
a Hamiltonian cycle, and let $C$ be a component of $F$ intersecting $X$. Since
$C$ is a cycle, $X\subset E(C)$. Let $C_{1}=C\cup\\{e_{1}\\}-\left(X\cup
E(G_{2})\right)$ and let $C_{2}=C\cup\\{e_{2}\\}-\left(X\cup E(G_{1})\right)$.
By definition, it follows that $C_{1}$ and $C_{2}$ are cycles in $G_{1}$ and
$G_{2}$, respectively. Furthermore, since $F$ is not a Hamiltonian cycle of
$G$, one of the following must occur (possibly both): $C_{1}$ is not a
Hamiltonian cycle of $G_{1}$, or $C_{2}$ is not a Hamiltonian cycle of
$G_{2}$. Assume first that $C_{1}$ is not a Hamiltonian cycle of $G_{1}$.
Since $C_{1}$ is a subgraph of $F\cup\\{e_{1}\\}-X$, we have that
$F\cup\\{e_{1}\\}-\left(X\cup E(G_{2})\right)$ is a 2-factor of $G_{1}$
containing $C_{1}$, implying that $G_{1}$ admits a 2-factor which is not a
Hamiltonian cycle containing $e_{1}$, a contradiction. Therefore, we must have
that $C_{2}$ is not a Hamiltonian cycle of $G_{2}$. However, this means that
since $C_{2}$ is a subgraph of $F\cup\\{e_{2}\\}-X$, we have that
$F\cup\\{e_{2}\\}-\left(X\cup E(G_{1})\right)$ is a 2-factor of $G_{2}$
containing $e_{2}$ which is not a Hamiltonian cycle, a contradiction once
again. Hence, $F$ is a Hamiltonian cycle, as required.

We first note that the graph $G_{2}$ in the above theorem is not necessarily
2FH, and can admit a 2-factor which is not a Hamiltonian cycle. In fact, there
exist 2FH-graphs which are obtained by applying a 2-cut connection between
graphs which are not both 2FH. Let $G_{1}$ be the cycle on four vertices, and
let $e_{1}$ be one of its edges. Let $G_{2}$ be the graph obtained by applying
a star product between two copies of $K_{4}$, and let $e_{2}$ be one of the
edges of the principal 3-edge-cut. The graph $G_{1}$ is 2FH, whilst $G_{2}$ is
not, as already stated above. However, $G_{1}(e_{1})\\#G_{2}(e_{2})$ is still
2FH (see Figure 13).

Figure 13: A 2FH-graph arising from a 2-cut connection between two graphs one
of which is not 2FH.

We further remark that we cannot do without the conditions imposed on $G_{1}$
and $G_{2}$ in the above theorem. In fact, the graphs $G_{1}$ and $G_{2}$
cannot both be just 2FH-graphs without any further properties, because a 2-cut
connection between two copies of $K_{3,3}$ is not 2FH. Moreover, the condition
on $G_{1}$ (that is, every 2-factor of $G_{1}$ is a Hamiltonian cycle
containing $e_{1}$) cannot be relaxed to be equivalent to the condition on
$G_{2}$ (that is, every 2-factor of $G_{2}$ containing $e_{2}$ is a
Hamiltonian cycle). In fact, let $G_{1}$ and $G_{2}$ be two copies of the
graph obtained by applying a star product between two copies of $K_{4}$, and
let $e_{1}$ and $e_{2}$ be one of the edges of the principal 3-edge-cut of
$G_{1}$ and $G_{2}$, respectively. For each $i\in\\{1,2\\}$, every 2-factor of
$G_{i}$ containing $e_{i}$ is a Hamiltonian cycle of $G_{i}$, however, the
graph $G_{1}(e_{1})\\#G_{2}(e_{2})$, portrayed in Figure 14, is not 2FH.

Figure 14: A graph arising from a 2-cut connection which is not 2FH.

## Acknowledgements

The authors would like to thank Marién Abreu, John Baptist Gauci, Domenico
Labbate and Giuseppe Mazzuoccolo for useful discussions about the topic.

## 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, D. Labbate, F. Romaniello and J.P. Zerafa, _Papillon graphs: perfect matchings, Hamiltonian cycles and edge-colourings in cubic graphs_ , submitted, arXiv:2106.00513.
  * [3] M. Abreu, J.B. Gauci and J.P. Zerafa, _Saved by the rook: a case of matchings and Hamiltonian cycles_ , submitted, arXiv:2104.01578.
  * [4] 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.
  * [5] J.A. Bondy and U.S.R. Murty, _Graph Theory_ , Grad. Texts in Math. 244. Springer-Verlag London, 2008.
  * [6] J. Fink, Perfect matchings extend to Hamilton cycles in hypercubes, _J. Combin. Theory Ser. B_ , 97 (2007), 1074–1076.
  * [7] J.L. Fouquet and J.M. Vanherpe, On the perfect matching index of bridgeless cubic graphs, (2009), hal-00374313.
  * [8] M. Funk, B. Jackson, D. Labbate and J. Sheehan, 2-Factor hamiltonian graphs, _J. Combin. Theory Ser. B_ 87 (2003), 138–144.
  * [9] J.B. Gauci and J.P. Zerafa, _On a family of quartic graphs: Hamiltonicity, matchings and isomorphism with circulants_ , submitted, arXiv:2011.04327.
  * [10] 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.
  * [11] 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.
  * [12] G. Kreweras, Matchings and Hamiltonian cycles on hypercubes, _Bull. Inst. Combin. Appl._ 16 (1996), 87–91.
  * [13] D. Labbate, Characterizing minimally 1-factorable r-regular bipartite graphs, _Discrete Math._ 248 (2002), 109–123.
  * [14] D. Labbate, On 3-cut reductions of minimally 1-factorable cubic bigraphs, _Discrete Math._ 231 (2001), 303–310.
  * [15] M. Las Vergnas, _Problèmes de couplages et problèmes hamiltoniens en théorie des graphes_ , Thesis, University of Paris 6, Paris, 1972.
  * [16] L. Lovász, Matching structure and the matching lattice, _J. Combin. Theory Ser. B_ 43 (1987), 187–222.
  * [17] T. Schönberger, Ein Beweis des Petersenschen Graphensatzes, _Acta Sci. Math. (Szeged)_ 7 (1934), 51–57.
  * [18] Z. Yang, On $F$-Hamiltonian graphs, _Discrete Math._ 196 (1999), 281–286.


# Large finite products of small fractions

Arnaldo Mandel  Computer Science Department, Instituto de Matemática e
Estatística, Universidade de São Paulo
_São Paulo, SP, Brazil 05508-970_
Orcid: 0000-0003-0661-4495<EMAIL_ADDRESS>
###### Abstract.

Fix positive reals $a,b,c,d$, and let $h(x)$ be a real function behaving sort
of like $\sin x$ near 0. Then, provided $m$ grows linearly with $n$. there
exists a positive constant $C$ such that

$\prod_{j=0}^{m}\frac{h\left((cj+a)\frac{d}{n}\right)}{h\left((cj+b)\frac{d}{n}\right)}\sim
Cn^{\frac{a-b}{c}}.$

###### 2010 Mathematics Subject Classification:

Primary: 41A60; Secondary: 33B15

This work was partially supported by Conselho Nacional de Desenvolvimento
Científico e Tecnológico – CNPq (Proc. 423833/2018-9).

Let $n\geq 4$ be an integer, denote $\theta=\frac{\pi}{2n}$, and consider the
finite product

$D_{n}=\frac{\sin 5\theta}{\sin 3\theta}\cdot\frac{\sin 9\theta}{\sin
7\theta}\cdot\frac{\sin 13\theta}{\sin 11\theta}\cdots$

where the terms go on while the arguments of $\sin$ stay below
$\frac{\pi}{2}$. The proof of an important result in [3] hinges on showing
that $D_{n}$ grows unboundedly with $n$. It is shown there that
$D_{n}=\Omega(n^{\frac{1}{2}-\varepsilon})$, which is enough; here we remove
the annoying $-\varepsilon$ from the exponent and determine the precise order
of growth.

Here is an outrageous idea, just do some obvious cancellations:
$\prod_{j}\frac{\sin(4j+5)\theta}{\sin(4j+3)\theta}=\
\prod_{j}\frac{\cancel{\sin}(4j+5)\theta}{\cancel{\sin}(4j+3)\theta}=\prod_{j}\frac{(4j+5)\cancel{\theta}}{(4j+3)\cancel{\theta}}=\prod_{j}\frac{4j+5}{4j+3}$,
and proceed from there.

Some people will have an issue with that, of course; however, this dumb idea
turns out to be useful! Indeed, we will tackle a strong generalization of the
product above, presenting good asymptotics, and the product obtained by
illegal cancellation will be a major tool.

The $\sin$ function is not very special in this context. The following
encapsulates what about it is relevant here. We use primes to denote
derivatives.

######  Proposition 1.

For a real function $h$, analytic around $0$, the following are equivalent:

  1. (1)

$h(0)=h^{\prime\prime}(0)=0$, $h^{\prime}(0)>0$, and $h^{\prime\prime}(x)\leq
0$ for positive $x$ close to $0$.

  2. (2)

$h(x)$ is the identity function or there exist reals $\alpha,\lambda>0$ and
integer $k\geq 3$ such that $h(x)=\alpha(x-\lambda x^{k})+O(x^{k+1})$.

###### Proof.

Exercise. ∎

For convenience, call a function as above an _S-function_ (a generalized sine,
so to speak).

Let $a,b,c,d$ be positive reals; they are supposed to be constant, throughout.
We consider an additional positive real parameter $\varepsilon$, subject to
the following _compatibility condition_ : $\varepsilon\leq cd$, and, if
$\varepsilon=cd$, then $cd>1$; this weird condition will only surface in 7.
Finally, given $n\in\mathbb{N}$, let $m=m(n)\in\mathbb{N}$ be maximum such
that both
$(cm+a)\frac{d}{n}\mathbin{\raisebox{2.15277pt}{,}}(cm+b)\frac{d}{n}\leq\varepsilon$,
that is $m=\lfloor\frac{n\varepsilon}{cd}-\frac{\max(a,b)}{c}\rfloor$. Given a
real function $h$, we define two products:

$\displaystyle D_{n}(a,b,c,d,\varepsilon;h)$
$\displaystyle=\prod_{j=0}^{m}\frac{h\left((cj+a)\frac{d}{n}\right)}{h\left((cj+b)\frac{d}{n}\right)}\mathbin{\raisebox{2.15277pt}{,}}$
$\displaystyle K_{n}(a,b,c,\varepsilon)$
$\displaystyle=\prod_{j=0}^{m}\frac{cj+a}{cj+b}\cdot$

Note that if one chooses $h(x)=x$, then
$K_{n}(a,b,c,\varepsilon)=D_{n}(a,b,c,d,\varepsilon;h)$, just a special case –
or, as mentioned before, by silly cancellation of $h$’s on the expression of
$D_{n}$. Note that there is no loss of generality in taking $d=1$, but we keep
the extra parameter to cater for the looks of the motivating example.

######  Theorem 2.

Suppose that $h$ is an S-function, and let $H(x)=\frac{h(x)}{x}$. Assume that
a compatible $\varepsilon$ is such that in $[0,\varepsilon]$ we have that
$H(x)>0$ and $H^{\prime\prime}(x)\leq 0$. Then, there exists a constant
$C=C(a,b,c,\varepsilon;h)$ such that

$D_{n}(a,b,c,\varepsilon;h)\sim Cn^{\frac{a-b}{c}}.$

Notice that, given $h$, one can always choose $\varepsilon$ as required, since
$H(x)=1-\lambda x^{k-1}+O(x^{k})$.

The motivating example in [3] is $D_{n}(5,3,4,\pi/2,\pi/2;\sin)$; some routine
algebraic manipulation show that $\varepsilon=\frac{\pi}{2}$ conforms to the
requirements of the Theorem, and we obtain $D_{n}\sim C\sqrt{n}$ for some
constant $C$.

The result will be obtained by comparing $D_{n}$ and $K_{n}$. The asymptotics
for $K_{n}$ is well known (it essentially appears in [1, $11^{\text{th}}$
formula line]).

######  Proposition 3.

$K_{n}(a,b,c,\varepsilon)\sim\frac{\Gamma(b/c)}{\Gamma(a/c)}\left(\frac{\varepsilon}{c}\right)^{\frac{a-b}{c}}n^{\frac{a-b}{c}}$.

###### Proof.

We can rewrite

$K_{n}(a,b,c,\varepsilon)=\prod_{j=0}^{m}\frac{j+a/c}{j+b/c}=\frac{\Gamma(b/c)}{\Gamma(a/c)}\frac{\Gamma(m+1+a/c)}{\Gamma(m+1+b/c)}\cdot$

The last quotient is asymptotic to $m^{\frac{a-b}{c}}$ (this follows easily
from Stirling’s formula; it falls into “well known”, see [4], [2, eq.
5.11.12]). The result follows by noticing that $m\sim\frac{\varepsilon n}{c}$.
∎

Without loss of generality, we will assume $d=1$ from now on, and remove it
altogether from the notation. Define

(1)
$E_{n}(a,b,c,\varepsilon;h)=\frac{D_{n}(a,b,c,\varepsilon;h)}{K_{n}(a,b,c,\varepsilon)}=\prod_{j=0}^{m}\frac{H\left(\frac{cj+a}{n}\right)}{H\left(\frac{cj+b}{n}\right)}\cdot$

Our goal will be met by showing that $\lim_{n\rightarrow\infty}E_{n}$ exists
and is positive. This result is as interesting as 2 itself, so we state it in
full, granting $H$ first class status, in parallel with 1.

######  Proposition 4.

For a nonconstant real function $H$, analytic around $0$, the following are
equivalent:

  1. (1)

$H(0)>0$,$H^{\prime}(0)=0$, and $H^{\prime\prime}(x)\leq 0$ for positive $x$
close to $0$.

  2. (2)

There exist reals $\alpha,\lambda>0$ and integer $k\geq 2$ such that
$H(x)=\alpha(1-\lambda x^{k})+O(x^{k+1})$.

Motivated as before, we call such a function a _C-function_. Clearly, $h(x)$
is an S-function if and only if $h(x)/x$ is a C-function. Therefore,
$E_{n}(a,b,c,\varepsilon;h)=D_{n}(a,b,c,\varepsilon;H)$ if $H(x)=h(x)/x$.

######  Theorem 5.

Suppose that $H$ is a C-function. Assume that a compatible $\varepsilon$ is
such that in $[0,\varepsilon]$ we have that $H(x)>0$ and
$H^{\prime\prime}(x)\leq 0$. Then
$\lim_{n\rightarrow\infty}D_{n}(a,b,c,\varepsilon;H)$ exists and is positive.

Noting that $D_{n}(a,b,c,d,\varepsilon;h)=D_{n}(b,a,c,d,\varepsilon;h)^{-1}$,
we will assume, in what follows, that $b<a$, as this will entail both theorems
in full. The hypotheses of either Theorem are assumed in the following lemmas,
and $h(x)=xH(x)$.

######  Lemma 6.

For all sufficiently large $n$, $D_{n}(a,b,c,\varepsilon;H)$ is bounded away
from $0$ – that is, $D_{n}(a,b,c,\varepsilon;h)=\Omega(n^{\frac{a-b}{c}})$.

###### Proof.

We will prove below that there exists a positive constant $A$ (independent of
$n$) such that for all relevant $j$, and sufficiently large $n$,

(2) $\frac{H\left(\frac{cj+a}{n}\right)}{H\left(\frac{cj+b}{n}\right)}\geq
1-\frac{A}{m}\cdot$

Having proved that, it follows that

$D_{n}(a,b,c,\varepsilon;H)\geq\left(1-\frac{A}{m}\right)^{m+1}\mathbin{\raisebox{2.15277pt}{,}}$

and the right hand side converges to $e^{-A}$, proving the Lemma.

It remains to prove 2. For that matter, consider parameters $\delta,\alpha>0$,
and define

$g_{\delta}(x,y)=\frac{1}{x}\left(1-\frac{H\big{(}(y+\delta)x\big{)}}{H(yx)}\right)\mathbin{\raisebox{2.15277pt}{,}}$

for $x>0,y\geq\alpha,yx\leq\varepsilon$, and with $g_{\delta}(0,y)=0$. One
easily verifies that $g_{\delta}$ is continuous: from the expression, this is
only an issue for $x=0$, and that is quickly handled using the Taylor
approximation for $H$ (this is also where the requirement that $k\geq 2$ in
the definition of C-function shows its hand). It follows that $g_{\delta}$
attains a maximum $A(\delta)$, hence, for all $x,y$ in the domain,

$\frac{H\big{(}(y+\delta)x\big{)}}{H(yx)}\geq 1-A(\delta)x.$

To obtain 2 we take $x=\frac{1}{n}\mathbin{\raisebox{2.15277pt}{,}}$
$\alpha=b$, $y=cj+b$, $\delta=a-b$. We are almost done, except that the right
hand side reads $1-\frac{A(\delta)}{n}$. Since $m=\lfloor\frac{\varepsilon
n}{c}-a\rfloor\geq\frac{\varepsilon n}{c}-a-1$,
$\frac{m}{n}\geq\frac{\varepsilon}{c}-\frac{a+1}{n}\geq\frac{\varepsilon}{2c}$
for sufficiently large $n$. Choosing now $A=A(\delta)\frac{\varepsilon}{2c}$
yields 2.

∎

######  Lemma 7.

For all relevant $j$ and sufficiently large $n$,

$\frac{H\left(\frac{cj+a}{n}\right)}{H\left(\frac{cj+b}{n}\right)}\geq\frac{H\left(\frac{c(j+1)+a}{n+1}\right)}{H\left(\frac{c(j+1)+b}{n+1}\right)}\cdot$

###### Proof.

This is clearly equivalent to proving that

(3)
$\frac{H\left(\frac{cj+a}{n}\right)}{H\left(\frac{c(j+1)+a}{n+1}\right)}>\frac{H\left(\frac{cj+b}{n}\right)}{H\left(\frac{c(j+1)+b}{n+1}\right)}\cdot$

Let $\delta(t)=\frac{c(j+1)+t}{n+1}-\frac{cj+t}{n}=\frac{(n-j)c-t}{n(n+1)}$
and $f(x)=\frac{H(x)}{H(x+\delta(a))}$; notice that
$n(n+1)\delta(a)\geq(n-m)c-a\geq n(c-\varepsilon)+a(c-1)>0$ for all
sufficiently large n, by compatibility. Let us show that $f$ is increasing; it
is enough to show that its logarithmic derivative, that is

$\frac{d}{dx}\log
f(x)=\frac{H^{\prime}(x)}{H(x)}-\frac{H^{\prime}(x+\delta(a))}{H(x+\delta(a))}\mathbin{\raisebox{2.15277pt}{,}}$

is positive. Since $\delta(a)>0$, this will follow if we show that
$\frac{H^{\prime}(x)}{H(x)}$ is decreasing; that follows, as its derivative is
$\frac{HH^{\prime\prime}-H^{\prime 2}}{H^{2}}$, which, by the choice of
$\varepsilon$, is negative. So, we have proved that $f$ is increasing. Taking
$X=\frac{cj+a}{n},\,Y=\frac{cj+b}{n}$, we have that $X>Y$, hence $f(X)>f(Y)$,
that is,

$\frac{H(X)}{H(X+\delta(a))}>\frac{H(Y)}{H(Y+\delta(a))}>\frac{H(Y)}{H(Y+\delta(b))}\mathbin{\raisebox{2.15277pt}{,}}$

where the last inequality follows since $\delta(b)>\delta(a)$ and $H$ is
decreasing. Expanding $X$ and $Y$, we obtain 3. ∎

###### Proof of 2.

It follows from 7 that for sufficiently large $n$
$E_{n+1}(a,b,c,\varepsilon;h)$ is a product of terms smaller than the
corresponding terms of $E_{n}$, and a few more terms, all of them $<1$. So,
the products $E_{n}$ form a decreasing sequence, which by 6 is bounded above
$0$. Therefore, it has a positive limit $C_{0}$, so
$D_{n}(a,b,c,\varepsilon;h)\sim C_{0}K_{n}(a,b,c,\varepsilon)\sim
Cn^{\frac{a-b}{c}}.$ ∎

It would be nice to describe $C=C(a,b,c,\varepsilon;h)$ in terms of the
parameters. Maybe a precise estimate of $A$ in 6 would cinch it. We present an
upper bound for $C$, assuming $a>b$:

######  Proposition 8.

$C(a,b,c,\varepsilon;h)\leq\frac{\Gamma(b/c)}{\Gamma(a/c)}\left(\frac{\varepsilon}{c}\right)^{\frac{a-b}{c}}.$

###### Proof.

Since $H(x)$ is decreasing, $E_{n}$ is a product of terms $<1$, hence
$E_{n}<1$. The result follows from 3. ∎

There are several common functions in each of the two classes: $\sin$,
$\arctan$, $\tanh$, $\sinh^{(-1)}$, erf are S-functions, while $\cos$,
$\cot^{(-1)}$, sech, $e^{-x^{2}}$, $(1+x^{2})^{-1}$ are C-functions, and one
can produce plenty of rational functions on each class. Besides, the
C-functions form a semiring with pointwise sum and product, and the
S-functions are a semimodule over that semiring; also the derivative of an
S-funtion is a C-function. All together, one can write very impressive
products, provided one can come with a nicely expressed $\varepsilon$ (for
instance, if $h(x)=\sin x$, one can take $\varepsilon=\frac{\pi}{2}$). It may
happen that for some suitable choice of parameters, coincidence happens, a
slick proof is forthcoming and even an exact result can be provided. That
could become an interesting exercise or competition question. For instance:

Exercise: Prove that, for $k\geq 2$,
$\lim_{n\rightarrow\infty}D_{n}\left(a,b,c,d,\left(\frac{k-1}{k}\right)^{\frac{1}{k}},e^{-x^{k}}\right)=e^{-\frac{k-1}{k}\frac{a-b}{c}}$.
Notice that $e^{-x^{k}}$ is a C-function and the choice of $\varepsilon$ was
driven by the conditions of 5. Never mind about compatibility, which in this
specific case is not necessary.

We close with two open problems:

Problem 1: Find an insightful expression for $C$ as in 2 or the limit in 5 in
terms of the parameters.

Problem 2: Estimate the rate of convergence to the limit in 5. A little
computational experimentation suggests that it is slow, the difference between
$D_{n}$ and the limit behaving as $O(1/\log n)$.

## References

  * [1] A. Dieckmann  “Collection of Infinite Product and Series”, 2018  URL: http://www-elsa.physik.uni-bonn.de/~dieckman/InfProd/InfProd.html
  * [2] “NIST Digital Library of Mathematical Functions”, http://dlmf.nist.gov/, Release 1.0.21 of 2018-12-15  URL: http://dlmf.nist.gov/5.11.12
  * [3] Arnaldo Mandel and Sinai Robins  “Dragging the roots of a polynomial to the unit circle”  In _arXiv e-prints_ , 2019, pp. arXiv:1908.03208  arXiv:1908.03208 [math.CV]
  * [4] J.. Wendel  “Note on the gamma function”  In _Amer. Math. Monthly_ 55, 1948, pp. 563–564  DOI: 10.2307/2304460