Abstrakt:

Petersen's seminal work in 1891 asserts that the edge-set of a cubic graph can be covered by distinct perfect matchings if and only if it is bridgeless. Actually, it is known that for a very large fraction of bridgeless cubic graphs, every edge belongs to at least two distinct perfect matchings. Here we study the class of non-double covered cubic graphs, i.e. graphs having an edge, called lonely edge, which belongs to exactly one perfect matching. First of all, we provide a reduction of the problem to the subclass U of 3-connected cubic graphs. Then, we furnish an inductive characterization of U and we study properties related to the count of lonely edges. In particular, denoting by U_k the subclass of graphs of U with exactly k lonely edges, we prove that U_k is empty for k>6, and we present a complete characterization for k=3,4,5,6. We conclude with some insights on U_1 and U_2.

♦ ♦ ♦

Abstrakt:

In my presentation, I will report on the project I participated on during the mobility stay on University of Lleida. In that project, we study inner metric parameters of digraphs (such as inner diameter, inner radius, ...) and how these values change considering the line digraph of the considered digraph. Our focus is also on integer sequences that are generated by inner metric parameters of iterated line digraphs. We show recurrence relation for the number of vertices in k-iterated line digraph. With the recurrence equation, we are able to solve a problem of finding the number of words over a given alphabet by avoiding a given set of subwords. The results are shown on the graph families, whose vertices are represented as words over some finite alphabet: De Bruijn, Kautz, Cyclic-Kautz, Square-Free.

Joint work with N. H. Bong, C. Dalfó, and M. A. Fiol

♦ ♦ ♦

Abstrakt:

The famous cage problem consists in finding k-regular graphs of girth g with minimal order. We know some lower bounds (Moore-bound) but in general this is a barely solved problem. In my talk, I will introduce an alternative problem. An egr graph is a k-regular graph of girth g such that every edge is contained in exactly lambda distinct girth cycles. With the incidence graph some finite geometrical structures we can construct egr graphs. However, since the initial graphs are bipartite we obtain egr graphs of even girth. At the end of my talk, I will talk about some techniques to obtain new families of (almost) egr graphs of girth 5.

♦ ♦ ♦

Abstrakt:

An edge-girth-regular(v,k,g,lambda) graph is a k-regular graph of order v and girth g such that each edge is contained in precisely lambda girth cycles. These graphs generalize several well known classes of graphs such as edge-regular graphs, edge-transitive graphs and arc-transitive graphs. In this seminar, we discuss an algorithm to exhaustively generate all edge-girth-regular graphs of a fixed order and improve several bounds on the minimum order of these graphs for certain tuples (k,g,lambda). Full paper: https://arxiv.org/pdf/2401.08271.pdf

♦ ♦ ♦

Abstrakt:

In this talk, we shall discuss connections between these two research topics, which have been widely studied but mostly separately. The cyclic edge-connectivity of a graph G is the smallest cardinality of an edge-cut that separates two cycles in G. It proved to be an important invariant of mostly cubic graphs and it emerges in various proofs and the study of smallest counter-examples. On the other hand, a (k,g)-cage is a smallest k-regular graph with girth g. We will show how cages and similar structures emerge in decomposing two cubic graphs with cyclic edge-connectivity k into two smaller cyclically k-connected cubic graphs. Moreover, we propose a conjecture that all (k, g)-cages are cyclically (k-2)g-edge connected, which is the larges possible value of cyclic connectivity. We prove this conjecture for (k,g)-cages with order at most roughly twice the Moore bound. This implies that the conjecture holds for some small pairs of (k,g) for which the order of a cage is not known including the famous hypothetical Moore graph of degree 57 and girth 5.

This is a joint work with Robert Lukoťka and Edita Máčajová.

♦ ♦ ♦

Abstrakt:

We prove that the Petersen graph is the only snark (i.e., non-3-edge-colourable connected cubic graph) in which every edge lies in a cycle of length at most five. This talk is based on a joint work with František Kardoš and Robert Lukoťka.

♦ ♦ ♦

Abstrakt:

The notion of "defining set" is an important concept in studying combinatorial structures. Roughly speaking, when we talk about a defining set for a particular object, we mean a part of it that uniquely extends to the entire object. As an example, a defining set for a particular perfect matching M of a graph (known as a "forcing set") is a subset of M such that M is the unique perfect matching of the graph containing it. The size of the smallest forcing sets of a perfect matching is called the "forcing number" of it.

In this talk, we introduce the notion of the forcing function of fractional perfect matchings, which is continuous analogous to forcing sets defined over the perfect matching polytope of graphs. Our defined object is a continuous and concave function extension of the integral forcing set. Then, we use our results about this extension to conclude new bounds and results about the integral case of forcing sets for the family of edge and vertex-transitive graphs, and in particular, hypercube graphs.

♦ ♦ ♦

Abstrakt:

The cycle double cover conjecture states that for every bridgeless graph G, there exists a family F of cycles such that each edge of the graph is contained in exactly two members of F. Given an embedding of a graph G, an edge e is called a bad edge if it is visited twice by the boundary of one face. CDC conjecture is equivalent to bridgeless cubic graphs having an embedding with no bad edge. In this talk, we introduce non-trivial upper bounds on the minimum number of bad edges in an embedding of a cubic graph.

♦ ♦ ♦

Abstrakt:

We will introduce the concept of a parallel product of groups and the associated concept of a parallel product of regular and orientably-regular maps, and present several applications of such types of products to construction of highly symmetric maps with extra requirements on their external symmetries.

♦ ♦ ♦

Abstrakt:

A graphical regular representation (GRR for short) of a group G is a Cayley graph of G whose full automorphism group is equal to the right regular permutation representation of G. In this talk, we study cubic GRRs of some families of classical groups and, based on some previously known results, confirm a conjecture made by Fang and Xia which asserts that with finitely many exceptions, every finite non-abelian simple group admits a cubic GRR.

♦ ♦ ♦

♦ ♦ ♦

Abstrakt:

Tutte's 5-flow conjecture states that "Every bridgeless multigraph has a nowhere-zero 5-flow." Only partial results of the conjecture are known thus far, the closest being Seymour's 6-flow theorem, which states that "Every bridgeless multigraph has a nowhere-zero 6-flow." This talk does not introduce new results but aims to highlight some interesting proofs of Seymour's 6-flow theorem. In particular, we will discuss in detail a relatively new proof of Seymour's 6-flow theorem by Matt DeVos, Jessica McDonald, and Kathryn Nurse.

♦ ♦ ♦

Abstrakt:

This is not a talk about new results but rather a gentle introduction to another way of thinking. We will review Ramsey's theorem in its infinite form and deduce the finite from it and then use the result to show the existence of another graph number. The latter is not provable by finite methods. Time permitting we mention other results where the infinite is needed to prove the finite.

♦ ♦ ♦

28.9.2023 o 9:50 v posluchárni F-skleník v pavilóne F1