Source author record

Jean Paul Zerafa

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

7works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Accordion graphs: Hamiltonicity, matchings and isomorphism with quartic circulants

Let $G$ be a graph of even order and let $K_{G}$ be the complete graph on the same vertex set of $G$ . A pairing of a graph $G$ is a perfect matching of the graph $K_{G}$ . A graph $G$ has the Pairing-Hamiltonian property (for short, the PH-property) if for each one of its pairings, there exists a perfect matching of $G$ such that the union of the two gives rise to a Hamiltonian cycle of $K_G$ . In 2015, Alahmadi \emph{et al.} gave a complete characterisation of the cubic graphs having the PH-property. Most naturally, the next step is to characterise the quartic graphs that have the PH-property. In this work we propose a class of quartic graphs on two parameters, $n$ and $k$ , which we call the class of accordion graphs $A[n,k]$ . We show that an infinite family of quartic graphs (which are also circulant) that Alahmadi \emph{et al.} stated to have the PH-property are, in fact, members of this general class of accordion graphs. We also study the PH-property of this class of accordion graphs, at times considering the pairings of $G$ which are also perfect matchings of $G$ . Furthermore, there is a close relationship between accordion graphs and the Cartesian product of two cycles. Motivated by a recent work by Bogdanowicz (2015), we give a complete characterisation of those accordion graphs that are circulant graphs. In fact, we show that $A[n,k]$ is not circulant if and only if both $n$ and $k$ are even, such that $k\geq 4$ .

preprint2022arXiv

Ban--Linial's Conjecture and treelike snarks

A bridgeless cubic graph $G$ is said to have a 2-bisection if there exists a 2-vertex-colouring of $G$ (not necessarily proper) such that: (i) the colour classes have the same cardinality, and (ii) the monochromatic components are either an isolated vertex or an edge. In 2016, Ban and Linial conjectured that every bridgeless cubic graph, apart from the well-known Petersen graph, admits a 2-bisection. In the same paper it was shown that every Class I bridgeless cubic graph admits such a bisection. The Class II bridgeless cubic graphs which are critical to many conjectures in graph theory are known as snarks, in particular, those with excessive index at least 5, that is, whose edge set cannot be covered by four perfect matchings. Moreover, in [J. Graph Theory, 86(2) (2017), 149--158], Esperet et al. state that a possible counterexample to Ban--Linial's Conjecture must have circular flow number at least 5. The same authors also state that although empirical evidence shows that several graphs obtained from the Petersen graph admit a 2-bisection, they can offer nothing in the direction of a general proof. Despite some sporadic computational results, until now, no general result about snarks having excessive index and circular flow number both at least 5 has been proven. In this work we show that treelike snarks, which are an infinite family of snarks heavily depending on the Petersen graph and with both their circular flow number and excessive index at least 5, admit a 2-bisection.

preprint2022arXiv

Disjoint odd circuits in a bridgeless cubic graph can be quelled by a single perfect matching

Let $G$ be a bridgeless cubic graph. The Berge--Fulkerson Conjecture (1970s) states that $G$ admits a list of six perfect matchings such that each edge of $G$ belongs to exactly two of these perfect matchings. If answered in the affirmative, two other recent conjectures would also be true: the Fan--Raspaud Conjecture (1994), which states that $G$ admits three perfect matchings such that every edge of $G$ belongs to at most two of them; and a conjecture by Mazzuoccolo (2013), which states that $G$ admits two perfect matchings whose deletion yields a bipartite subgraph of $G$ . It can be shown that given an arbitrary perfect matching of $G$ , it is not always possible to extend it to a list of three or six perfect matchings satisfying the statements of the Fan--Raspaud and the Berge--Fulkerson conjectures, respectively. In this paper, we show that given any $1^+$ -factor $F$ (a spanning subgraph of $G$ such that its vertices have degree at least 1) and an arbitrary edge $e$ of $G$ , there always exists a perfect matching $M$ of $G$ containing $e$ such that $G\setminus (F\cup M)$ is bipartite. Our result implies Mazzuoccolo's conjecture, but not only. It also implies that given any collection of disjoint odd circuits in $G$ , there exists a perfect matching of $G$ containing at least one edge of each circuit in this collection.

preprint2022arXiv

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

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.

preprint2021arXiv

The Erdős--Faber--Lovász Conjecture revisited

The Erdős--Faber--Lovász Conjecture, posed in 1972, states that if a graph $G$ is the union of $n$ cliques of order $n$ (referred to as defining $n$ -cliques) such that two cliques can share at most one vertex, then the vertices of $G$ can be properly coloured using $n$ colours. Although still open after almost 50 years, it can be easily shown that the conjecture is true when every shared vertex belongs to exactly two defining $n$ -cliques. We here provide a quick and easy algorithm to colour the vertices of $G$ in this case, and discuss connections with clique-decompositions and edge-colourings of graphs.

preprint2020arXiv

An equivalent formulation of the Fan-Raspaud Conjecture and related problems

In 1994, it was conjectured by Fan and Raspaud that every simple bridgeless cubic graph has three perfect matchings whose intersection is empty. In this paper we answer a question recently proposed by Mkrtchyan and Vardanyan, by giving an equivalent formulation of the Fan-Raspaud Conjecture. We also study a possibly weaker conjecture originally proposed by the first author, which states that in every simple bridgeless cubic graph there exist two perfect matchings such that the complement of their union is a bipartite graph. Here, we show that this conjecture can be equivalently stated using a variant of Petersen-colourings, we prove it for graphs having oddness at most four and we give a natural extension to bridgeless cubic multigraphs and to certain cubic graphs having bridges.

preprint2020arXiv

Perfect matchings and Hamiltonicity in the Cartesian product of cycles

A pairing of a graph $G$ is a perfect matching of the complete graph having the same vertex set as $G$ . If every pairing of $G$ can be extended to a Hamiltonian cycle of the underlying complete graph using only edges from $G$ , then $G$ has the PH-property. A somewhat weaker property is the PMH-property, whereby every perfect matching of $G$ can be extended to a Hamiltonian cycle of $G$ . In an attempt to characterise all 4-regular graphs having the PH-property, we answer a question made in 2015 by Alahmadi et al. by showing that the Cartesian product $C_p\square C_q$ of two cycles on $p$ and $q$ vertices does not have the PMH-property, except for $C_4\square C_4$ which is known to have the PH-property.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Jean Paul Zerafa

Research overview

Is this your work?

7 publications

Accordion graphs: Hamiltonicity, matchings and isomorphism with quartic circulants

Ban--Linial's Conjecture and treelike snarks

Disjoint odd circuits in a bridgeless cubic graph can be quelled by a single perfect matching

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

The Erdős--Faber--Lovász Conjecture revisited

An equivalent formulation of the Fan-Raspaud Conjecture and related problems

Perfect matchings and Hamiltonicity in the Cartesian product of cycles

See the researcher in context

Building this map preview