Abstracts 2009

June 25th     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.

Since 2009 are the abstracts maintained only on PDF.

Abstracts 2008

January 8th     A. Semaničová: From magic squares to antimagic wheels

Joint work with Martin Bača and Petr Kovář

We focus on (a,d)-antimagic labelings of wheels and similar graphs. Besides presenting a solution to some problems we also post a few open problems.

January 8th     A. Semaničová: Number of edges and vertices in a supermagic graph

Joint work with Jaroslav Ivančo and Petr Kovář

We examine the relation between the number of edges and the number of vertices in a supermagic graph. We show that for every order n there exists a constant εso that every graph on n vertices with ε edges is not supermagic.

In the second part we examine supermagic labelings of regular graphs.

September 24th     M. Knor: Graph centers

In this short lecture we present the notion of graph radii, diameters, centers, periphery and rim. Also we mention the most recent generalizations of graph centers which are based on sets of vertices (and not only on a single vertex). We give a summary of known results for generalized radii.

Abstracts 2007

January 18th, 2007     D. Fronček: Incomplete and non-compact round robin tournaments

Joint work with Mariusz Meszka, Petr Kovář, and Tereza Kovářová

Most hockey fans (at least all Czech ones) would probably agree that the current format of the World Championship is not good. Therefore, we can imagine a situation when the International Ice Hockey Federation tries yet another model of the championship. As they want to preserve the current number of teams and games, they decide to play two qualifying groups with 8 teams in each of them. However, because a complete tournament would take too long, they decide that each team plays just 5 games rather than 7. One group consists of Slovakia, Czech Republic, Sweden, Russia, France, Denmark, Japan, and Ukraine. The games that are not to be played include Slovakia-France, Slovakia-Japan, Russia-Sweden and Russia-Czech Republic. We can see that this schedule is not fair, because Russia plays just one tough game against Slovakia while Slovakia plays all the strongest teams. We will show how to avoid such a situation and make an incomplete tournament as fair as possible. The solution is actually a nice application of certain type of graph labeling, namely vertex-magic vertex labeling.

On the other hand, we can consider complete round robin tournaments that are scheduled in a bit unusual way. Many sports competitions are played as 2-leg round robin tournaments with 2n teams. These tournaments are typically scheduled in such a way that a schedule for a 1-leg tournament is repeated twice. By a round we mean a collection of games in which each team plays at most one game. A team that does not play a game in a particular round is said to have a bye in that round.

The home and away games of every team should interchange as regularly as possible provided that each team meets every opponent once at its own field and once at the opponent's field. The best home-away pattern (HAP) is indeed one with no two consecutive home or away games (called a break in the schedule). Obviously, we can never find a compact schedule for 2n teams with no breaks - in this case the teams that start the season with a home game would never meet. Therefore, looking at HAPs, the best schedule is one with the minimum number of breaks. This number in a 1-leg round robin tournaments is 2n-2, as proved by de Werra.

We will show that if each team has exactly one bye, then we can construct schedules with no breaks, and that these schedules are unique.

Abstracts 2006

April 25th, 2006     M. Kubesa: Progress on the Cheesecake problem - Summary of open problems

The summary of problem to solve is:

• Decompose K_{m,m,m,m,m} into C_m
• Decompose K_{m,4m,4m,4m,4m} into C_m
• Decompose K_{2,2,2,2} into C_3

Pictures from the seminar.

October 4th, 2006     P. Kovář: On spectra of VMT labelings of complete bipartite graphs

Let λ be an injective mapping from the set of both vertices and edges (V ∪ E) of a graph to the set of the first |V|+|E| natural numbers. The weight w_λ(v) of a vertex v in V is the sum of its label and the labels of all adjacent edges. We say λ is a vertex magic total (VMT) labeling if the weight of each vertex is equal to the same constant h called the magic constant. The spectra of a given graph G is the set of all magic constants which can be realized by a VMT labelings of G. It was conjectured by W. Wallis et al. that all n² feasible values of the spectra of K_n,n can be realized by some VMT labeling. So far only two different magic constants were known. We present constructions for a large set of magic constants.

October 25th, 2006     T. Kupka: The spectral properties of the Laplacian matrix of the Cartesian product

The presentation is concerned with a problem of the recognition of the Cartesian product graph. First we introduce the Laplacian matrix as the representation of a graph. Then we focuse on the spectral properties of the Laplacien matrix and show how to use them for a recognition of the Cartesian and approximate Cartesian product graphs. We conclude this talk by a summary of approache problems and design algorithm that solves many of them.

Abstracts 2005

February 28th, 2005     M. Kubesa: "Faktorizations of K_4k+2 into caterpillars of diameter 5 without a vertex of degree 2"

Kubesa conjectures: All such caterpillars, that satisfy Fronček's necessary condition, faktorize K_4k+2, where the Fronček's necessary condition is:

If a [t₁,t₂,t₃,t₄]-caterpillar on 2n vertices with t₄ ≥ 3 and n ≥ 4 factorizes K_2n into n isomorphic copies, then either t₁=n and t₂+t₃+t₄=n+2 or t₁+t₄=t₂+t₃=n+1.