Abstrakty 2020

13. července     Dalibor Froček: Γ-supermagic Labeling of Cartesian Products of Two Cycles

(joint work with Lincoln Sorensen and Peter Paananen)

A graph G=(V,E) with |V|=p, |E|=q is called Γ-supermagic if there exists a bijection f from E to an Abelian group Γ of order q such that the weight w(x) of each vertex x, defined as the sum of labels of all edges incident with x, is equal to the same magic element μ. In other words,

      w(x)=∑_{xy ∈ E} f(xy)=μ.

for all x ∈ V and some μ ∈ Γ. The labeling is called a Γ-supermagic labeling.

It was proved by DF, James McKeown, John McKeown, and Michael McKeown, that a Z_{2mn}-supermagic labeling of the Cartesian product C_m × C_n exists for all m, n ≥ 3.

We present some further results on Γ-supermagic labeling of C_m × C_n by other Abelian groups.

Keywords: Γ-supermagic labeling, group supermagic labeling

Pozvánka v PDF


25. června     Jakub Závada: On Scheduling of Incomplete Tournaments

Tournament in which n participants play each other in n-1 rounds is called a round robin tournament. This type of tournament is quite fair for each participant but for instance in lots of chess tournaments the number of participants is too large to play all n-1 rounds. So, how can we schedule a tournament with n participants into k, k < n-1 rounds if we want the tournament to be as fair as possible? Swiss system is often used but it cannot be used when we need to schedule the whole tournament ahead. We can try to use graph theory to find the best possible schedule.

Pozvánka v PDF


3. února     Róbert Jajcay: Algebraic constructions of cages

A cage with parameters (k,g) is a k-regular graph of girth g of the smallest possible order. Networks based on the use of cages often prove to be among the most efficient and reliable, and the search for cages (the Cage Problem) is an important part of Extremal Graph Theory as well as a widely studied optimization problem. Even though cages do not necessarily have to be algebraic objects, the majority of the known cages and of the smallest known (k,g)-graphs come from algebraic constructions. In our talk we will present a brief overview of the Cage Problem, describe some of the most successful algebraic constructions of small graphs of given degree and girth, and also address the question of the limitations of algebraic constructions.

Pozvánka v PDF


3. února     Tatiana Jajcayová: Partial automorphisms of graphs and algebraic tools to study them

The problem of determining the full automorphism group of a graph is one of the well-known hard problems. The focus of our recent joint project with Maria Szendrei, Nora Szakacs, and Robert Jajcay is on an extension of the automorphism group problem to that of inverse monoid problem. The full inverse monoid of partial automorphisms of a combinatorial structure is a much richer algebraical structure that contains more detailed local information about the underlying object. The goal is to apply the algebraic methods of partial permutation semigroup theory to the class of structures that admit none or only very few automorphisms and typically resist the use of methods from permutation group theory. The results involving partial automorphisms and use of inverse monoids may offer new insights into some well known and long open problems from Graph Theory, as we will illustrate with some examples.

A partial automorphism of a graph is an isomorphism between its induced subgraphs. The set of all partial automorphisms of a given structure forms an inverse monoid under composition of partial maps. In our presentation, we describe the algebraic structure of such inverse monoids by the means of the standard tools of inverse semigroup theory, and give a characterization of inverse monoids which arise as inverse monoids of partial graph (digraph and edge-colored digraph) automorphisms.

Pozvánka v PDF


3. února     Mária Mériová: Inverse monoids for certain classes of graphs

In order to better understand a specific combinatorial structure (for instance a graph) it is recommended to study, investigate and analyze the symmetries of this combinatorial structure. Up to recently, the main tools to study these symmetries were tools of Group Theory, that is full automorphisms and groups of full automorphisms. In cases where structures have no global symmetries and full automorphisms can not be used, these tools are rather limited. But the structures may still exhibit some local symmetries and thus their partial automorphisms are interesting.

Based on theoretical results published about local symmetries, we know that induced subgraphs need to be studied for graphs, and we have developed software that makes a list and analyzes the induced subgraphs of a given graph. Then, using these induced subgraphs, we studied the structure of inverse monoids related to the partial automorphisms of these graphs. At the beginning of our project, we have dealt with simple families of graphs: paths, cycles and trees, but we believe that our results can be generalized to other classes of graphs as well. As J. Nešetřil, M. Konečný et al. research suggests, another interesting class of graphs could be tournaments.

Pozvánka v PDF


3. února     Slobodan Filipovski: On bipartite cages of excess 4

The Moore bound M(k,g) is a lower bound on the order of k-regular graphs of girth g (denoted (k,g)-graphs). The excess e of a (k,g)-graph of order n is the difference n-M(k,g). In this talk we consider the existence of (k,g)-bipartite graphs of excess 4 via studying spectral properties of their adjacency matrices.

Pozvánka v PDF


3. února     Tom Raiman: Conditions for vertex removal in (k,g)-graphs

For almost sixty years there has been thorough research about properties of k,g)-graphs and (k,g)-cages. There have been a lot of attempts to improve lower and upper bounds for (k,g)-graphs given some qualities of these graphs. We want to show new ideas how to find smaller (k,g)-graphs from existing ones, while preserving the regularity and girth and show how these ideas may help to find new upper bounds that could be smaller than the existing ones.

Pozvánka v PDF


18. února     Tom Raiman: Conditions for vertex removal in (k,g)-graphs

A (k,g)-graph is graph with regularity k and girth g. Since 1960's it is known that (k,g)-graphs exists for every pair of k and g. Since then the goal is to find (k,g)-cages (cage is smallest possible (k,g)-graph). Although some cages had been found it very much unexplored territory. People try to at least improve currently best known lower bounds of so called records.

In this lecture we will look at the ways how people try to improve these records and how our methods differ from the currently know methods.

Pozvánka v PDF


30. ledna     Petr Kovář: Vertex in-out-antimagic total labeling of digraphs

This is a joint workjoint work with Martin Bača, Tereza Kovářová, and Andrea Semaničová-Feňovčíková

A vertex in-out-antimagic total labeling of a directed graph (digraph) D=(V,A) with n vertices and m arcs is a bijection from the set V ∪ A to the set of integers {1, 2, ..., m+n } such that all n vertex in-weights are pairwise distinct and simultaneously all n vertex out-weights are pairwise distinct, where the vertex in-weight is the sum of the vertex label and the labels of all incoming arcs and the vertex out-weight is the sum of the vertex label and the labels of all outgoing arcs.

In this talk we conjecture that all digraphs allow such labeling and provide a general way how to label dense digraphs and certain sparse digraphs.

Pozvánka v PDF


14. ledna     Ján Karabáš: Cycles and perfect matchings in snarks

The lecture is based on the results of the joint work with Roman Nedela and Martin Škoviera.

Every 3-edge-colourable cubic graph has a set of three perfect matchings that cover all of its edges. Conversely, if the edge set of a cubic graph can be covered with three perfect matchings, the matchings must be disjoint and the graph 3-edge-colourable. The cubic graphs not possesing any regular 3-edge-colourings are called snarks. It follows in snarks any collection of three perfect matchings misses some edges of a graph. The minimum number of edges of a cubic graph G left uncovered by any three perfect matchings will be called the colouring defect (shortly defect) of G and will be denoted by df(G). Clearly, a cubic graph has defect zero if and only if it is 3-edge-colourable and the number is grater than zero for snarks. This invariant has been introduced by E. Steffen in 2015 [3] and it appears to be interesting invariant of snarks.

We try to exhibit relationships of the defect of a snark to other invariants such as (colouring) resistance, oddness, girth, criticality, irreducibility [2] and others. It is quite easy to show that defect of snarks is greater or equal to three. Far the most of the snarks have defect equal to three, which implies a strong structural constraint – the existence of a six-cycle. We will show the smallest snark with defect greater than 3 and discuss the consequences of this observation. We will set the colouring defect for several families of snarks or, at least, we will present the working hypotheses on them. We will also exhibit the close relationship of the study of snarks with small defect and well-known hypotheses e.g. Berge-Fulkerson Conjecture and 6-decomposition theorem [1,2] (Jaeger Conjecture).
  1. J. Karabáš, E. Máčajová, R. Nedela, 6-decomposition of snarks, European J. Combin. 34 (2013), 111–122.
  2. R. Nedela and M. Škoviera, Decompositions and reductions of snarks, J. Graph Theory 22 (1996), 253–279
  3. E. Steffen, 1-Factor and cycle covers of cubic graphs, J. Graph Theory 78 (2015), 195–206

Pozvánka v PDF


Abstrakty 2019

1. listopadu     Petr Gregor: Symmetric chain decompositions and the central levels problem

A symmetric chain in the n-dimensional cube Qn is a path of length n-2k that starts on level k and ends on level n-k for some k. Greene and Kleitman in 1970's described a decomposition of V(Qn) into symmetric chains. The central levels problem asserts that the subgraph of the (2m+1)-dimensional cube induced by all vertices between levels m+1-l and m+l (i.e. the central 2l levels) has a Hamilton cycle for all m ≥ 1 and 1 ≤ l ≤ m+1. This problem raised by Savage is a common generalization of the well-known middle levels problem and classical binary Gray codes.

In the first part we give introduction to symmetric chain decompositions (SCDs) and Gray codes with their applications. In the second part we present a constructive solution to the central levels problem that is based on the Greene-Kleitman SCDs. In particular, we show that the Greene-Kleitman SCD extends to a Hamilton cycle of Qn and there is a loopless algorithm to generate it. This is a joint work with Torsten Mütze and Ondřej Mička.

Pozvánka v PDF


10. září     Martin Škoviera: Point-line configurations in projective spaces and the structure of cubic graphs

We propose a unifying approach to several important conjectures in graph theory in terms of nowhere-zero flows on cubic graphs where flow-values are points of a configuration of lines in a projective space and outflow-patterns are triples of points sharing a line of the configuration. We then focus on the conjecture of Claude Berge suggesting that every bridgeless cubic graph can have its edges covered with at most five perfect matchings. It turns out that cubic graphs that require five (or more) perfect matchings to cover their edges are extremely rare and hence difficult to find. We show that they can be efficiently studied by means of flows whose outflow patterns form a configuration of six lines spanned by four points of the 3-dimensional projective geometry PG(3,2) in general position. We employ this knowledge to provide a great variety of constructions of cubic graphs that cannot be covered with four perfect matchings. We finally show that one of our constructions provides counterexamples to a conjecture of Brinkmann et al. about the length of a shortest cycle cover of a cyclically 4- edge-connected cubic graph.

This is a joint work with Edita Máčajová.

Pozvánka v PDF


10. září     Edita Máčajová: Smallest counterexample to the Fulkerson conjecture must be cyclically 5-edge-connected

The Fulkerson conjecture belongs to one of the most prominent open problems in Graph theory. It suggests that the edges of any bridgeless cubic graph can be covered with six perfect matchings in such a way that each edge belongs to exactly two of them. The origin of this conjecture lies in mathematical programming and the conjecture itself has close connections to configurations of points and lines in the projective space. Despite the fact that Berge and Fulkerson made this conjecture almost half a century ago, it has been verified only for several explicitly defined families of graphs. During the talk we will present the current state of this conjecture as well as its connections to other important conjectures in graph theory. As the main result we show that Fulkerson’s conjecture can be reduced to cyclically 5-edge-connected cubic graphs.

This is a joint work with Giuseppe Mazzuoccolo.

Pozvánka v PDF


10. září     Tom Raiman: Use of generalized truncation for computer search for (k,g)-graphs

A (k,g)-graph is a graph with regularity k and girth g. We investigate the use of generalized truncation in improving the upper bound of (k,6) and (k,8)-bound, where k=q+2 and q a is prime power. We also discuss conditions under which one can reverse generalized truncation. We have done this with the aim of obtaining a tool for proving the existence or non-existence of the (57,5)-Moore graph.

Pozvánka v PDF


10. září     Petr Kovář: Supermagic graphs with arbitrary degree differences

We present a recent result on constructing supermagic graphs that have a degree sequence d1, d2, ..., dn, , with an arbitrary seqlist of differences of

Pozvánka v PDF


Abstrakty 2019

20. srpna     Dalibor Froček: Supermagic graphs with many different degrees

(joint work with Petr Kovář)

A graph G=(V,E) is called supermagic if there exists a bijection f: E → {1, 2, ..., |E|} called supermagic labeling such the weight of every vertex x ∈ V defined as the sum of labels f(xy) of all edges xy incident with x is equal to the same number m, called the supermagic constant. That is,

∃ m ∈ N ∀ x ∈ V: w(x) = ∑xy ∈ E f(xy) = m.

Typically, the classes of graphs studied in this context are vertex-regular or even vertex-transitive. Recently, Kovář et al. affirmatively answered a question by Madaras:

Does there exist a supermagic graph with k different degrees for any positive integer k?

Because their construction provided only graphs where all degrees were even, they asked the following more specific question:

Does there exist a supermagic graph with k different odd degrees for any positive integer k?

We answer this question in the affirmative by providing a construction based on the use of 3-dimensional magic rectangles.

The obvious next step is to ask the following:

Let k>1 be an integer and s_1, s_2, ..., s_{k-1} a sequence of positive integers. Is there a positive integer a_1 such that there exists a supermagic graph with degrees a_1, a_2, ..., a_k where a_{i+1}=a_i+s_i for i=1, 2, ..., k-1?

We also present a sketch of two proposed constructions of graphs hopefully answering the above question in the affirmative.

Keywords: Supermagic graphs, magic-type labeling, edge labeling

Pozvánka v PDF


2. listopadu     Petr Kovář: Highly irregular supermagic graphs

(joint work with Michal Kravčenko, Matěj Krbeček, and Adam Silber)

Let G = (V, E) be a graph with m edges. A bijection f : F → { a, a+1, ..., a+m-1 } for some integer a is called a supermagic labeling of G if for every vertex v the sum of edge-labels of all edges adjacent to v is equal to the same integer k. The constant k is the \emph{magic constant} of f and any graph which admits a supermagic labeling is a supermagic graph. The concept of magic graphs (with arbitrary real labels) is one on the oldest labeling concepts. It originated by Sedláček in 1963. Supermagic labelings were introduced by Stewart in 1967.

Dozens of papers have been published on supermagic labelings, mostly providing constructions of supermagic labelings of a specific class of graphs as well as some necessary conditions for the graph to allow a supermagic labeling. The proofs are mostly constructive, usually providing a labeling technique for regular or almost regular graphs. Some supermagic graphs with different degrees were provided by Ivančo and Semaničová in 2005 or Ivančo and Polláková in 2012 and 2014. Recently we obtained a general construction of supermagic graphs with arbitrarily many different degrees. Today we present the result as well as some open problems this area.

Pozvánka v PDF


1. června     Dalibor Fronček: How close to being platonic can you get?

(joint work with Jiangyi Qiu)

A Platonic graph is a vertex-regular planar graph with all faces of the same size. It is well known that there exist exactly five such graphs: tetrahedron, octahedron, hexahedron, icosahedron, and dodecahedron. Recently, William Keith asked whether there exist nearly Platonic graphs that would differ from Platonic in just one face. That is, vertex-regular planar graphs with all faces except one having the same size. W. Keith, D. Kreher and the speaker then showed (or at least believed that they had shown) that no such graphs exist [1]. On the other hand, there are well known classes of 2-nearly Platonic graphs with exactly two exceptional faces, both of the same size. We will and ask (and partially answer) some questions about 2- and 3-nearly Platonic graphs. In other words, about vertex-regular planar graphs with exactly two or three exceptional faces.

[1] W. Keith, D. Froncek, D. Kreher, A note on nearly Platonic graphs, Australas. J. Combin. (2017), 86-103.

Pozvánka v PDF


5. května     Tom Raiman: Conditions for adding vertices to (k,g)-graphs

A (k,g)-graph is a k-regular graph of girth g. A (k,g)-graph of the smallest possible order is called a (k,g)-cage. The Cage Problem is the problem of finding such smallest graphs and their orders for all pairs k,g ≥ 3. This problem has been extensively studied since the 1960's when Erdös and Sachs proved the existence of infinitely many (k,g)-graphs for any pair (k,g). Their original upper bound on the order of cages has been later improved by Sauer. In each case, an order was found with the property that a (k,g)-graph exists for each admissible order larger than this bound. We present a different approach and study the properties of (k,g)-graphs that can be extended into larger (k,g)-graphs by adding vertices. This approach may potentially give rise to recursive constructions based on smaller graphs than those identified by Erdös, Sachs, and Sauer.

Pozvánka v PDF


Abstrakty 2017

8. listopadu     Dalibor Fronček: Some cycle products are more magic than others

A Cartesian product CmCn of two cycles Cm and Cn can be seen as a toroidal m × n grid with mn vertices of degree four and 2mn edges. We can bijectively label the edges, vertices, or both by consecutive positive integers 1, 2, . . . , s or by elements of an Abelian group Γ of order (where s is the number of labeled elements) and define the weight of an element (that is, an edge or a vertex) as the sum of labels of the adjacent and/or incident elements. When the weights of all elements in question are equal, we call the labeling magic (of some kind). When the weights are all different, the labeling is called antimagic. I will present some old and new results on various kinds of magic labelings of cycle products and pose several open questions. The results are based on collaboration with several co-authors, including Tereza Kovářová, Petr Kovář, Jack McKeown, James McKeown, Michael McKeown, and Yichen Wei.

Pozvánka v PDF


23. října     Michael Kubesa: Faktorizace kompletních grafů na kostry

Kostra grafu je souvislý faktor grafu G, který neobsahuje cykly. Nejdříve se seznámíme s pojmem semisurjektivní a bicyklická faktorizace kompletního grafu, uvedeme jednoduché nutné podmínky pro faktorizace z názvu přednášky. Pak objasníme pojmy symetrický ρ-labeling, blended labeling a swapping labeling, což jsou postačující podmínky pro semisurjektivní faktorizace kompletních grafů na kostry.

TATO PŘEDNÁŠKA je 2. PŘEDNÁŠKA trojpřednáškového cyklu a je určena doktorandům a výzkumníkům, kteří se zabývají problémy diskrétní matematiky.

Pozvánka v PDF


9. října     Michael Kubesa: Základy dekompozic a faktorizací kompletních a kompletních bipartitních grafů

Řekneme si, co je dekompozice a faktorizace grafů. Dále se zaměříme na postačující podmínky dekompozice a faktorizace kompletních a kompletních bipartitních grafů, které uvedeme ve formě tzv. labelingu. Budeme hovořit o graceful labelingu, ρ-labelingu a bipartitním ρ-labelingu. Budeme tedy hovořit jen o nejzákladnějších labelinzích týkajících se dekompozic a faktorizací. Kdo by se o nich chtěl dovědět více, doporučujeme: Joseph A. Gallian, A Dynamic Survey of Graph Labeling.

TATO PŘEDNÁŠKA je 1. PŘEDNÁŠKA trojpřednáškového cyklu a je určena především doktorandům, kteří se v rámci postgraduálního studia zabývají problémy diskrétní matematiky.

Pozvánka v PDF


3. října     Štefan Gyürki: Directed strongly regular graphs

Since the main objects of interest in algebraic graph theory are highly symmetric graphs, strongly regular graphs are playing a central role in this area. One of their possible generalization for directed graphs was given by Duval in 1988. A directed strongly regular graph (DSRG) with parameters (n, k, t, λ, μ) is a regular directed graph on vertices with valency k such that every vertex is incident with t undirected edges; the number of directed paths of length 2 directed from a vertex x to another vertex y is λ, if there is an arc from x to y and μ otherwise. In this talk we mention their basic properties and several constructions of such graphs

Pozvánka v PDF


27. června     Tom Raiman: Grafy geometrických designů (2)-([28,3,21])

(t)-([q^n,k,λ]) design na (n)-dimenzionálním vektorovém prostoru stupně (q) je množina (B) (k)-dimenzionálních podprostorů ((k)-podprostory), nazývané bloky, takové, že libovolný (t)-dimenzionální podprostor ((t)-podprostor) je podprostorem přesně (λ) bloků. Takový design označujeme jako ((V,B)). Je-li (t)-podprostor podprostorem (k)-podprostoru jsou tyto podprostory incidentní. Graf poté vyjadřuje incidenci mezi (k)- a (t)-podprostorem. Zaměříme se na grafy, které vzniknou z designu (2)-([28,3,21]).

Pozvánka v PDF


12. ledna     Dalibor Fronček: Decompositions of complete bipartite graphs into prisms revisited

A generalized prism, or more specifically an (0,j)-prism of order 2n (where n is even) is a cubic graph consisting of two cycles u0, u1, ..., un-1 and v0, v1, ..., vn-1 joined by two sets of spokes, namely u1v1, u3v3, ..., un-1vn-1 and u0vj, u2vj+2, ..., un-2vj-2. The question of factorization of complete bipartite graphs into (0,j)-prisms was completely settled by the author and S. Cichacz. Some partial results on decompositions of complete bipartite graphs have also been obtained by S. Cichacz, DF, and P. Kovar, and on decompositions of complete graphs S. Cichacz, S. Dib, and DF. The problem of decomposition of complete graphs into prisms of order 12 and 16 was completely solved by S. Cichacz, DF and M. Meszka. In June 2014 I presented what I had believed was a complete solution for the decomposition of complete bipartite graphs into (0,0)-prisms (that is, the usual prisms). In the same talk I mentioned my presentation in March 2014 in Boca Raton, Florida, where I had to admit that the results I had promised in my abstract were not covering any new cases, but rather just re-proved previously known results. This time, I will retract what I have retracted, and order what I have ordered.

Pozvánka v PDF


Abstrakty 2016

12. prosince     Robert Jajcay: Counting cycles in graphs with small excess

A (k,g)-cage is a k-regular graph of girth g that has the smallest number of vertices among all graphs with the parameters k and g. The orders of cages are bounded from below by the well-known Moore bounds, however, the exact orders are not known for the majority of cages. The excess of a cage is the difference between its order and the Moore bound, and a systematic study of the excesses of cages leads to improved lower bounds on their orders. We present some of the most recent improvements based on counting cycles.

Pozvánka v PDF


20. dubna     Wilfried Imrich: Symmetry breaking in graphs

In a graph, a set of vertices that is stabilized setwise by only the trivial automorphism is called a distinguishing set. Tom Tucker conjectured that every connected, infinite locally finite graph G has such a set if each nontrivial automorphism of G moves infinitely many vertices. The conjecture is know as the Infinite Motion Conjecture. It is still open despite the fact that numerous large classes of graphs have been shown to satisfy it.

In finite graphs distinguishing sets, if they exist, can be very small in comparison to the size of the graph, and in infinite graphs such sets can be finite. If they are not finite, their density can be zero. This talk presents classes of graphs that have distinguishing sets of zero density. Moreover, it is shown that the Infinite Motion Conjecture is true for cubic graphs.

Pozvánka v PDF


12. dubna     Tom Raiman: Faktorizace grafů na pulce

Faktorizace kompletních grafů představuje klasický problém nejen z teorie grafů, ale i teorie designů. Toto téma je zkoumáno od 60. let 20. století. Co se týče faktorizace kompletních grafů byly známy pouze zřejmé výsledky (faktorizace na hamiltonovské cesty a dvojhvězdy). V poslední době byly nalezeny třídy koster, které faktorizují a které ne. Mezi ně patří některé housenky a langusty. Momentálně jsou zkoumány faktorizace kompletních grafů na unicyklické grafy zvané pulci. Unicykly lze faktorizovat pouze kompletní grafy s lichým počtem vrcholů, tzn. K2n+1. Pro faktorizace kompletních grafů na pulce používáme modifikované metody faktorizací kompletních grafů na kostry. Zejména smíšené ohodnocení pro n liché a přepínací ohodnocení pro n sudé. Nyní je výzkum veden pro n liché, protože smíšené ohodnocení je jednodušší.

Pozvánka v PDF


25. ledna     Tomáš Gavenčiak: Hry na grafech

Seznámení s hrami na četníky a lupiče zaměřené na geometrické grafy (jako jsou třeba rovinné, intervalové či křivkové) a se zajímavými výsledky poslední doby.

Hry na četníky a lupiče mají mnohem blíže k abstraktním deskovým hrám a (snad trochu překvapivě) k strukturální a výpočetní složitosti, než k aplikované bezpečnosti, a jsou elegantní kapitolou (už tak hravé) teorie kombinatorických her.

Pozvánka v PDF


5. ledna     Dalibor Fronček: Group distance magic labelings of hypercubes and Cartesian products of cycles

Let G be a graph with n vertices and f a bijection f:V(G) -> {1,2,...,n}. We define the weight of vertex x as the sum of the labels of its neighbors, that is, w(x)=∑_{xy∈E(G)}f(y).

When all vertices have the same weight, say w(x)=m for every x, then f is called distance magic labeling and G is a distance magic graph.

However, it turns out that this type of magic labeling is very restrictive and consequently even many classes of vertex transitive graphs are not distance magic.

As an example, we prove that for d≡0,1,3 mod 4 the hypercube Q_d with 2^d vertices is not distance magic. On the other hand, we disprove a conjecture by Acharya, Rao, Singh and Parameswaran, who believed that hypercubes are not distance magic except Q_2 and present a distance magic labeling for Q_6. This was recently generalized by Gregor and Kovar who found a distance magic labeling for of Q_d for any d≡2 mod 4.

Such negative results then rise a question whether it would not be more natural to perform the addition in Z_n rather than in Z. Graphs that satisfy the above definition with the provision that the addition is performed in Z_n will be called Z_n-distance magic.

To support this idea, we show some examples of graphs that are not distance magic yet are Z_n-distance magic. We show that when we perform addition Z_{2^d} rather than in Z, then Q_d is Z_{2^d}-distance magic if and only if d is even.

We present some results on Γ-distance magic labelings of products of cycles and pose several open problems.

Pozvánka v PDF


Abstrakty 2014

6. listopadu     Kateřina Volná, Matěj Krbeček: Arboricita, Orientace planárního grafu

První část semináře bude věnována arboricitě grafu. Kateřina Volná zavede pojem arboricity, neboli stromovitosti, kterou lze využít při hledání nejmenšího odchozího stupně vrcholu v grafu. Uvede jednotlivé druhy arboricity a také souvislost s chromatickým číslem grafu. Závěr prezentace je pak věnován algoritmům a jejich složitosti.

Druhá část seminář bude o 3-bounded orientaci v planárním grafu. Matěj Krbeček se bude věnovat problematice d-bounded orientace, konkrétně 3-bounded a jejímu nalezení v planárních grafech. Nadefinujeme základní pojmy a zmíníme věty týkající se dané problematiky. Popíšeme si algoritmus s lineární složitostí, který využívá tzv. reducibilních vrcholů.

Pozvánka v PDF


30. října     Jiří Fiala: Hledání Hamiltonovských cest v intervalových grafech

V přednášce se budeme zabývat problémem, zdali lze množinu reálných intervalů uspořádat do posloupnosti tak, že každé dva po sobě následující intervaly mají neprázdný průnik. Pro tento problém bude představen algoritmus a s jeho pomocí se ukáže, že jistá zřejmá nutná podmínka pro existenci takového uspořádání je zároveň i postačující.

Jinými slovy, buď daná posloupnost existuje, pak ji lze nalézt a ověřit patřičné vlastnosti; nebo neexistuje a i v tomto případě lze relativně snadno nalézt argument proč ani existovat nemůže. To je jeden z mála případů, kdy má obecně výpočetně těžký problém stručné důkazy pro případy kladných i záporných odpovědí.

Přednáška je určená široké veřejnosti, žádné odborné znalosti z kombinatoriky ani výpočetní složitosti nejsou nutné k porozumění tématu.

Pozvánka v PDF


20. června     Dalibor Fronček: Decompositions of complete bipartite graphs into prisms

A generalized prism, or more specifically an (0,j)-prism of order 2n (where n is even) is a cubic graph consisting of two cycles u_0,u_1,...,u_{n-1} and v_0,v_1,..,v_{n-1} joined by two sets of spokes, namely u_1 v_1, u_3 v_3,...,u_{n-1}v_{n-1} and u_0 v_j, u_2 v_{j+2},...,u_{n-2}v_{j-2}.

The question of factorization of complete bipartite graphs into (0,j)-prisms was completely settled by the author and S. Cichacz. Some partial results on decompositions of complete bipartite graphs and complete graphs have also been obtained by them and P. Kovar and S. Dib, respectively. The problem of decomposition of complete graphs into prisms of order 12 and 16 was completely solved by the author with S. Cichacz and M. Meszka and presented at IWONT 2012.

We will present a complete solution for the decomposition of complete bipartite graphs into (0,0)-prisms (that is, the usual prisms).

Pozvánka v PDF


2. června     Michael Kubesa: 15 školaček podruhé, Kirkmanovy trojúhelníkové systémy (KTS) vyšších řádů

V první přednášce bude dokončen výklad k rho- a bipartitnímu rho-ohodnocení. Dále bude vyřešen problém 15 školaček pomocí faktorizace kompletního grafu. Ukážeme, že touto metodou jsme schopni vytvořit KTS(15). Ve druhé části bude předvedena rekurzivní konstrukce KTS(6n+3), je-li n větší než 2.

Pozvánka v PDF


26. května     Michael Kubesa: Problém 15 školaček aneb Kirkmanovy trojúhelníkové systémy (KTS)

15 školaček v internátní škole se má procházet každý den po trojicích v pěti řadách. Naplánujte jejich rozdělení do trojic na každý den v týdnu (7 dnů) tak, že každá dvojice se v rámci trojic potká právě jednou. Ukážeme si řešení tohoto úkolu, přičemž ozřejmíme souvislost mezi tvorbou seskupitelných designů a faktorizací kompletních grafů. Čili si ukážeme konstrukci KTS pro 9 a 15 prvků. Konstrukce KTS vyšších řádů budou uvedeny v další přednášce.

Pozvánka v PDF


21. května     Tereza Kovářová, Kateřina Volná: Teorie designů (část 4)

Teorie designů je matematická disciplína na pomezí kombinatoriky, teorie grafů a teorie množin. Zkoumá systémy podmnožin s předepsanými parametry. Aplikace teorie designů najdeme především v plánování (organizace experimentů s mnoha nezávislými parametry, plánování sportovních turnajů) nebo při rozkladů grafů na podgrafy. Ve čtvrtém z řady seminářů, koncipovaném především pro studenty předmětu Metody diskrétní matematiky, si ukážeme konstrukce Balanced Tournament Designu v souvislosti s aplikací tohoto designu při vytváření rozpisu turnaje s speciálním požadavkem na umístění zápasů.

Pozvánka v PDF


25. dubna     Petr Kovář: Teorie designů (část 3)

Teorie designů je matematická disciplína na pomezí kombinatoriky, teorie grafů a teorie množin. Zkoumá systémy podmnožin s předepsanými parametry. Aplikace teorie designů najdeme především v plánování (organizace experimentů s mnoha nezávislými parametry, plánování sportovních turnajů) nebo při rozkladů grafů na podgrafy. Ve třetím z řady seminářů, koncipovaném především pro studenty předmětu Metody diskrétní matematiky, se budeme věnovat konstrukcím Steinerovských systémů trojic.

Pozvánka v PDF


24. dubna     Róbert Jajcay: Symmetric cages (Symetrické klietky)

A (k,g)-cage is a smallest k-regular graph of girth g. Finding a (k,g)-cage for given parameters k and g is thus an optimization problem in which one looks for an extremal graph in an infinite search space of all k-regular graphs of girth g. The search for cages started in earnest in the 1960's, but turned out to be too hard in general, and has only recently been revived due to the introduction of algebraic and topological methods in the area. In our talk, we present an overview of the contributions stemming of the use of Cayley and vertex-transitive graphs as well as some recent results concerning the restriction of the original cage problem to these two classes of symmetric graphs. The talk is aimed at general mathematical audience including students.

Pozvánka v PDF


11. dubna     Petr Kovář: Teorie designů (část 2)

Teorie designů je matematická disciplína na pomezí kombinatoriky, teorie grafů a teorie množin. Zkoumá systémy podmnožin s předepsanými parametry. Aplikace teorie designů najdeme především v plánování (organizace experimentů s mnoha nezávislými parametry, plánování sportovních turnajů) nebo při rozkladů grafů na podgrafy. V druhém z řady seminářů, koncipovaném především pro studenty předmětu Metody diskrétní matematiky, se budeme věnovat Steinerovským systémům trojic.

Pozvánka v PDF


4. dubna     Petr Kovář: Teorie designů (část 1)

Teorie designů je matematická disciplína na pomezí kombinatoriky, teorie grafů a teorie množin. Zkoumá systémy podmnožin s předepsanými parametry. Aplikace teorie designů najdeme především v plánování (organizace experimentů s mnoha nezávislými parametry, plánování sportovních turnajů) nebo při rozkladů grafů na podgrafy. V prvním z řady seminářů, koncipovaném především pro studenty předmětu Metody diskrétní matematiky, zavedeme základní pojmy a zformulujeme hlavní problém teorie designů.

Pozvánka v PDF


13. ledna     Tereza Kovářová: Handicapové grafy vyšších pravidelností

(spoluautor Petr Kovář)

Handicapové ohodnocení grafů má potenciál při sestavování neúplných turnajů ve kterých součet sil protihráčů každého týmu je tím větší čím silnější tým je. Na semináři byly dříve prezentovány výsledky týkající se konstrukcí handicapových ohodnocení 3-pravidelných a 5-pravidelných grafů. Jedním z nevyřešených problémů bylo nalezení handicapového ohodnocení pro grafy s vyšší pravidelností. V této navazující přednášce budou ukázány možnosti konstrukcí tohoto ohodnocení r-pravidelných grafů na n vrcholech, pro všechna přípustná r < n-10.

Pozvánka v PDF


Abstrakty 2013

13. prosince     Michael Kubesa: Orientace rovinných grafů

Chceme orientovat jednoduchý konečný rovinný graf tak, aby největší odchozí stupeň grafu byl co nejmenší. Tento problém souvisí s vhodnou paralelizací výpočtu v numerických úlohách.

Pozvánka v PDF


6. prosince     Pavla Hrušková: Několik vybraných aplikací spektrální teorie grafů

V úvodu přednášky se seznámíme s pojmem spektrum grafu. Spektrem grafu je myšlena množina vlastních čísel a vlastních vektorů grafu, který pro tyto účely reprezentujeme maticí. Jako vhodná maticová reprezentace se pro tyto účely používá nejčastěji matice sousednosti, případně Laplaceova matice. Ukážeme známá spektra některých vybraných typů grafů, konkrétně cesty a kartézského produktu dvou cest, což v numerické matematice odpovídá 1D, resp. 2D čtvercové síti.

V další části připomeneme aplikaci na využití spektra grafů pro důkaz neexistence faktorizace kompletního grafu pomocí 3 Petersenových grafů, pro který ale potřebujeme znalost kompletního spektra a dále se budeme zabývat aplikacemi využívající pouze část spektra (zpravidla vlastní vektory odpovídající několika největším, resp. nejmenším, vlastním číslům).

Nejdříve ukážeme nejběžnější použití vlastních vektorů Lapaceovy matice na spektrální dělení grafů poprvé zmíněné již Prof. Fiedlerem v 70. letech (první aplikace pochází z 80.-90.let). Dále ukážeme použití vlastních vektorů Laplaceovy matice pro nalezení optimální volby tzv. fixujících vrcholů používaných při řešení některých typů numerických úloh pomocí FETI metod, konkrétně úloh se semidefinitní maticí tuhosti. Obdobné myšlenky se uplatňují v obecných aplikacích typu (spektrální) kreslení grafů případně clusterování grafů. Jedna z nejznámnějších aplikací spektrální teorie grafů je Google ranking algoritmus používaný ve vyhledávacím enginu Googlu. Mnohé z těchto aplikací se v dnešní době s úspěchem používají také v různých sociálních sítích (clustering, eigenvector centrality apod.).

Pozvánka v PDF


26. listopadu     Tereza Kovářová: Postupy diskrétní matematiky při losování reálné sportovní soutěže

(spoluautorka Kateřina Volná)

Pro plánování amatérské soutěže ve sportovní střelbě, kdy se na různých střeleckých drahách utkají vždy dvojice střelců, je nutno uvážit:

  • počet účastníků soutěže,
  • omezení počtu střeleckých drah,
  • dostatečné, avšak nepříliš dlouhé přestávky mezi jednotlivými koly pro každého hráče,
  • pravidelné střídání drah a na každé dráze střídání pozice vlevo či vpravo.
V rámci přednášky bude ukázáno, jak lze pro sestavení rozpisu s výhodou využít nástrojů diskrétní matematiky, jako jsou rozklady kompletních grafů nebo latinské čtverce a další.

Pozvánka v PDF


22. listoadu     Michael Kubesa: Neplanarita grafu, Toky v sítích

Seminář bude didakticky zaměřen. Bude prodiskutováno použití Kuratowského věty k zjištění neplanarity grafu, užití Ford Fulkersonova algoritmu k vyhledání největšího toku a nejmenšího řezu v síti.

Pozvánka v PDF


8. listoadu     Petr Kovář: Hranová barvení grafů

Při paralelizaci numerického výpočtu vyvstala úloha, kterou je možno zformulovat v řeči teorie grafů: máme různě ohodnocené vrcholy a hledáme takové hranové ohodnocení, kdy hodnota přiřazená každé hraně odpovídá hodnotě jednoho koncového vrcholu. Ukážeme teoretické ohraničení počtu barev (myšlenku existenčního důkazu). Na tomto pracovním semináři uvedeme problém hledání konstruktivního důkazu, který by bylo možno použít pro rychlé nalezení takového ohodnocení.

Pozvánka v PDF


29. října     Michael Kubesa: Princip inkluze, exkluze a jeho nevhodné použití

V přednášce si ukážeme chybné použití principu inkluze a exkluze, chybu identifikujeme, rozebereme a ukážeme správné řešení.

Pozvánka v PDF


2. května     Pavla Kabelíková: Využití spektrálních vlastností grafů pro ověření (ne)existence faktorizací

Faktorizace grafu H na množinu hranově disjunktních navzájem izomorfních podgrafů G_1, G_2, ..., G_k je takový rozklad grafu H, kdy každá hrana grafu H patří do právě jednoho podgrafu G_i, každý podgraf G_i obsahuje všechny vrcholy původního grafu H a žádný vrchol není izolovaný. Problém nalezení faktorizace grafu na podgrafy je předpokládán za NP-úplný a pro některé třídy grafů je jeho NP-úplnost dokázána. K nalezení faktorizací některých tříd grafů se využívá různých grafových technik.

Vzhledem k tomu, že jsou podgrafy G_i izomorfní, jsou jejich matice podobné (ve smyslu algebraické podobnosti matic) a mají tedy stejné spektrum. K výpočtu spektra matic může být využita nějaká iterační metoda. V tomto pracovním semináři nejprve ukážeme s využitím znalosti spektra jednotlivých grafů, že kompletní graf na 10 vrcholech nemůže být faktorizován třemi Petersenovými grafy. Tento známý výsledek využivá velmi specifické struktury spektra Petersenova grafu a jeho vztahu ke spektru kompletního grafu. Cílem semináře bude pokus o aplikování této nebo obdobné konstrukce i na jiné typy grafů.

Pozvánka v PDF, prezentace v PDF, fotky


18. dubna     Přemysl Holub: Duhově souvislé grafy

Mějme dán hranově obarvený graf G. Řekneme, že G je duhově souvislý, jestliže každé dva vrcholy grafu jsou spojeny duhovou cestou (všechny hrany cesty mají rozdílné barvy). Nejmenší počet barev k potřebný k obarvení hran grafu G tak, aby G byl duhově souvislý, nazveme duhovou souvislostí grafu. Cílem přednášky bude seznámení se s tímto pojmem a některými známými výsledky z této oblasti.

Pozvánka v PDF. Prezentace v PDF.


28. března     Petr Kovář, Martin Kovář: Magická ohodnocení - otevřené problémy

Za posledního čtvrt roku se podařilo dotáhnout do konce důkazy některých výsledků, ale současně vyvstaly nové zajímavé otázky. Na ty nejzajímavější z nich upozorníme.

Pozvánka v PDF.


Abstrakty 2012

10. prosince     Pavel Jahoda: Množiny dokonalých rozdílů

Přednáška bude pojednávati o tom, kterak nalézti množinu dokonalých rozdílů (perfect difference set).

Pozvánka v PDF.


4. prosince     Pavel Jahoda: Co je konečné těleso?

Co je to těleso? Co je konečné těleso? Existují vůbec? Kolik může mít prvků? Jak nějaké zkonstruovat? Proč by měl být polynom použitý při konstrukci konečného tělesa ireducibilní? Dostanu pro různé ireducibilní polynomy při konstrukci konečného tělesa různá konečná tělesa? Kolik různých těles s daným počtem prvků existuje? Trápí Vás alespoň jedna z těchto otázek? Přijďte!

Pozvánka v PDF.


27. listopadu     Petr Kovář: Využití rozkladů grafů na husté podgrafy při paralelní implementaci BEM

spoluautoři: D. Lukáš, T. Kovářová a M. Kravčenko

Naším úkolem bude rozdělit n2 bloků Bij rozsáhlé matice do n skupin tak, aby v každé skupině byly bloky s co nejmenším počtem různých indexů. Ukážeme jaká jsou teoretická omezení pro tento minimální počet indexů při pevně zvoleném počtu n a ukážeme, že pro nekonečně mnoho různých hodnot umíme tohoto optima dosáhnout. Důkaz je konstruktivní, vychází z rozkladů kompletních grafů na husté podgrafy a umožní pro vybrané hodnoty n optimálně implementovat úlohu z minulé přednášky. Na závěr zmíníme několik zobecnění, která umožní dosáhnout počtu různých indexů blízkých optimální hodnotě i pro další hodnoty n, pro které neexistuje optimální řešení.

Pozvánka v PDF.


19. listopadu     Dalibor Lukáš: Paralelní metoda hraničních prvků pomocí cyklické dekompozice grafů

spolu s P. Kovářem, T. Kovářovou, M. Mertou a M. Kravčenkem

Metoda hraničních prvků je numerická metoda pro řešení okrajových úloh některých parciálních diferenciální rovnic. Metoda vede na soustavu lineárních rovnic s plnou maticí, jejíž řádky i sloupce odpovídají prvkům triangulace 3d výpočetní oblasti. Při paralelním sestavení řídké aproximace této matice chceme distribuovat triangulaci tak, aby výpočet spotřeboval minimum času i paměti. Ukazuje se, že pro jisté počty procesorů taková optima dostaneme pomocí cyklické dekompozice úplných grafů.

V přednášce pro ilustraci odvodíme hraniční formulaci Dirichletovy úlohy pro Laplaceovu rovnici v 1 dimenzi. Pro analogickou úlohu ve více dimenzích napíšeme vzorce pro výpočet prvků plné matice a popíšeme její řídkou aproximaci. Konečně formulujeme požadavky na její optimální paralelizaci a ukážeme, že některá optima máme díky cyklické dekompozici grafů.

Pozvánka v PDF.


12. listopadu     Michael Kubesa: T-faktorizace kompletních grafů

Mějme podgrafy G_1,G_2,...,G_s, kompletního grafu, které jsou všechny izomorfní s grafem G. Patří-li každá hrana kompletního grafu do přesně jednoho podgrafu G_i, pak jde o G-dekompozici kompletního grafu. Obsahují-li podgrafy G_i všechny vrcholy kompletního grafu a žádný vrchol není v G_i izolovaný, pak G-dekompozici nazýváme G-faktorizací. My se v přednášce zaměříme na G-faktorizace, kdy G je strom (souvislý graf bez cyklů). Protože G je strom, označíme jej T. V T-faktorizaci kompletního grafu je tedy každý podgraf T_i stromem a obsahuje všechny vrcholy kompletního grafu, Takovým podgrafům budeme říkat kostry kompletního grafu. Snadno lze ukázat, že T-faktorizaci lze provést pouze pro kompletní grafy se sudým počtem vrcholů, a že v T nesmí být žádnývrchol vyššího stupně než-li n, má-li kompletní graf 2n vrcholů. Postačující podmínkou pro T-faktorizaci kompletního grafu K_{2n}, je-li n liché, je smíšené ohodnocení kostry T, které je založeno na existenci rho-ohodnocení a bipartitního rho-ohodnocení, o nichž jsme vyprávěl minule. A právě o smíšeném ohodnoceníbude hovor.

Pozvánka v PDF.


5. listopadu     Michael Kubesa: G-dekompozice kompletních grafů

Mějme podgrafy G_1,G_2,...,G_s, kompletního grafu, které jsou všechny izomorfní s grafem G. Patří-li každá hrana kompletního grafu do přesně jednoho podgrafu G_i, pak jde o G-dekompozici kompletního grafu. Postačující podmínkou pro G-dekompozici kompletního grafu K_{2n+1} jsou alpha-ohodnocení, beta-ohodnocení a rho-ohodnocení grafu G s n hranami. A právě o těchto ohodnoceních a bipartitním rho-ohodnocení bude hovor.

Pozvánka v PDF.


30. října     Petr Kovář: Hledání handicapových labelingů grafů se sudou pravidelností

Prezentovali jsme známé výsledky týkající se nutných podmínek existence handicapových ohodnocení pravidelných grafů. Zmínili jsme otevřené problémy v této oblasti.

Pozvánka v PDF.


22. října     Tereza Kovářová: Konstrukce 3- a 5-pravidelných handicapových grafů

Prezentovali jsme známé výsledky týkající se konstrukcí 3- a 5-pravidelných handicapových grafů. Zformulovali jsme další směr výzkumu.

Pozvánka v PDF.


8. října     Petr Kovář: Nutné podmínky existence handicapových grafů

Prezentovali jsme známé výsledky týkající se nutných podmínek existence handicapových ohodnocení pravidelných grafů. Zmínili jsme otevřené problémy v této oblasti.

Pozvánka v PDF.


1. října     Petr Kovář: Neúplné turnaje a magická ohodnocení pravidelných grafů

V přednášce shrneme přehled témat, kterým se můžeme věnovat v rámci semináře DiMaS.

Pozvánka v PDF.


Abstrakty 2011

21. dubna     Michael Kubesa: Grafová ohodnocení a jejich použití při rozkladech kompletních a bipartitních kompletních grafů

Mějme vzajemně izomorfní pografy G_1,G_2,... ,G_m grafu H (platí tedy G_1 ≅ G_2 ≅ ... ≅ G_m ≅ G). Jestliže každá hrana grafu H je obsažena v přesně jednom podgrafu G_i, i ∈ {1, 2,... , m}, pak hovoříme o G-rozkladu (dekompozici) grafu H. Pokud graf G s n hranami umožňuje tzv. graciózní nebo ρ-ohodnocení, pak existuje G-rozklad kompletního grafu K_{2n+1} a jestliže má G tzv. bipartitní ρ-ohodnocení, pak existuje G-rozklad kompletního bipartitního grafu K_{n,n}.

Pozvánka v PDF.


Abstrakty 2009

16. prosince     Roman Kužel: Nelineární iterační metody pro výpočet kritického čísla a hustoty neutronového toku aktivní zóny jaderných reaktorů typu VVER

Přednáška bude věnována problematice řešení difuzního modelu transportu neutronů pro reaktory s kazetami se šestiúhelníkovým průřezem. Zaměříme se především na rychlé nelineární iterační algoritmy založené na hrubosíťovém výpočtu a metodě příčných integrací.

Pozvánka v PDF.


15. prosince     Roman Čada: Diskrétní matematika v optimalizaci palivových vsázek jaderného reaktoru

Přednáška bude zaměřena po nezbytném fyzikálním úvodu na matematické metody řešení úlohy optimalizace palivových vsázek v jaderných reaktorech. Ačkoli se ve své podstatě jedná o úlohu nelineární kombinatorické optimalizace, používané metody zahrnují kombinaci přístupů založených na spojité a diskrétní nelineární optimalizaci, stochastických metodách a konceptech užívaných v diskrétní matematice.

Pozvánka v PDF.


9. prosince     Martin Knor: Polomerovo Moorovské grafy a digrafy

Graf (digraf) je polomerovo Moorovský ak má pri danom polomere s a maximálnom stupni t maximálny možný počet vrcholov a jeho priemer je nanajvýš s+1. Je známe, že pre každé s a t existuje polomerovo Moorovský digraf daného stupňa a polomeru. Pre grafy je analogický problém otvorený. Polomerovo Moorovské grafy sú známé pre každý stupeň t pri polomeroch 1 a 2 a pre niekolko malých stupňov pri polomere 3.

Pozvánka v PDF.


1. prosince     Petr Kovář: Simpsonovi a matematika

V oblíbeném televizním seriálu najdeme celou řadu momentů, ve kterých se objeví základní i moderní matematické pojmy. V přednášce na několik takových míst upozorníme. Současně naznačíme některé hlubší souvislosti.
Přednáška může být zajímavá nejen pro studenty, ale i pro vyučující (motivace ve výuce).
Kalkulačky s sebou!!!

Pozvánka v PDF.


25. května     S. Arumugam: Min-Max and Max-Min Graph Saturation Parameters

A talk on hereditary property concerning subsets of the vertex set of a graph G. In this talk a brief survey of results on certain parameters for various graph theoretic properties is given.

Pozvánka v PDF.



Od roku 2009 jsou abstrakty připravovány pouze v PDF formátu.

Staší abstrakty najdete pouze v anglické verzi.

Send an email to the organizers kontakty Poslední úpravy: 08.07.2021