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 n2 feasible values of the spectra of Kn,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 K4k+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 K4k+2, where the Fronček's necessary condition is:

If a [t1,t2,t3,t4]-caterpillar on 2n vertices with t4 ≥ 3 and n ≥ 4 factorizes K2n into n isomorphic copies, then either t1=n and t2+t3+t4=n+2 or t1+t4=t2+t3=n+1.

We will examine these caterpillars with a vertex of degree 2k+1.

Pictures from the seminar.

March 7th, 2005     T. Kovářová: "On spanning tree factorizations of complete graphs"

Let T be a tree such that there is a T-factorization of a complete graph K2n into n isomorphic copies of T, then the degree sequence of the tree T must satisfy certain necessary conditions. Michal Kubesa conjectured that always the vertex set V(T) can be split into two subsets V1, V2 of the same size n, such that the sum of degrees of all the vertices in V1 is the same as the one in V2. We will present the necessary background for the topic of a spanning tree factorizations of complete graphs, and introduce some basic observations, related to the conjecture. An open discussion on the problem is expected to follow.

Pictures from the seminar.

March 18th, 2005     Discussion: "New results on faktorizations of K4k+2 into caterpillars and on Kubesa's conjecture"

We have opened several problems during the first seminars. Now came the time to summarize the open problems, present new results and to post, if necessary, new questions on "old" topics.

Pictures from the seminar.

March 25th, 2005     Discussion: "On Dalibor Fronček's observations"

Discussion on "The Observations" by Dalibor Fronček on inductive constructions on factorizations of K4k+2 into caterpillars with diameter 5.

Pictures from the seminar.

April 11th, 2005     Discussion: "New results on factorizations of K4k+2 into caterpillars of diameter 5 without a maximal vertex"

This time we focused on factorizations of K4k+2 into caterpillars of diameter 5 without a maximal vertex. Michael Kubesa will present results on factorizations of K4k+2 into caterpillars of diameter 5 - case AB. Tereza Kovářová will present results on factorizations of K4k+2 into caterpillars of diameter 5 - case Ab and Petr Kovář will present results on factorizations of K4k+2 into caterpillars of diameter 5 - case Aa.

Pictures from the seminar.

April 14th, 2005     Discussion: "Completing the results on factorizations of K4k+2 into caterpillars of diameter 5"

Factorizations of K4k+2 into caterpillars of diameter 5. Are there any missing cases?

April 18th, 2005     Discussion: "Completing the results on factorizations of K4k+2 into caterpillars of diameter 5 - case AB and ab"

The problem of factorizations of K4k+2 into caterpillars of diameter 5 is mostly solved. It remains to find certain labelings for graphs for n=6 and n=8.

April 21th, 2005     Discussion: "Summary of results on factorizations of K4k+2 into caterpillars of diameter 5"

What remains to be done on the problem of factorizations of K4k+2 into caterpillars of diameter 5?

May 6th, 2005     P. Kovář: "Introduction to magic labelings of graphs I"

Magic type labeling are an analogue to magic squares well known from recreational mathematics. First we introduce various magic type graph labelings:

  • a vertex magic total (VMT) labeling of a graph G(V,E),
  • an (s,d)-vertex antimagic total (VAMT) labeling,
  • a supermagic (SPM) labeling (also known as vertex magic edge labeling).
This talk should be a brief introduction to the topic of "magic graph labelings". We give definitions, examples and a summary of known results.

J. MacDougall conjectured that any regular graph with the exception of K2 and 2K3 has a VMT labeling.

In the talk we present recent results on VMT and VAMT labelings of certain regular graphs and post some research problems.

May 19th, 2005     Discussion: "On the article on factorizations of K4k+2 into caterpillars of diameter 5"

Putting all parts of the paper on the problem of factorizations of K4k+2 into caterpillars of diameter 5 into one coherent article.

May 20th, 2005     P. Kovář: "Introduction to magic labelings of graphs II"

Magic type labeling are an analogue to magic squares well known from recreational mathematics. First we introduce various magic type graph labelings:

  • a vertex magic total (VMT) labeling of a graph G(V,E),
  • an (s,d)-vertex antimagic total (VAMT) labeling,
  • a supermagic (SPM) labeling (also known as vertex magic edge labeling).
In the beginning we review the definitions and some examples. This talk should introduce the notion of magic rectangles and especially Kotzig arrays. These arrays are used to construct magic type labelings of regular graphs, copies of regular graphs or products of regular graphs.

In the talk we present recent results post some research problems realted to the MacDougall's conjecture that any regular graph with the exception of K2 and 2K3 has a VMT labeling.

Pictures from the seminar.


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