Seminar iz diskretne matematike

Vodji seminarja: Boštjan Brešar in Sandi Klavžar
Predavanja potekajo ob ponedeljkih ob 15:15 v seminarski sobi P1 (Gosposvetska cesta 84, v 4. nadstropju).

Bodoča predavanja

Minula predavanja

Klasifikacija 2-prekrižno kritičnih grafov

20. 01. 2014

Predavatelj: Drago Bokal

It is very well-known that there are precisely two minimal non-planar
graphs: K_5 and K_{3,3} (degree 2 vertices being irrelevant in this
context). In the language of crossing numbers, these are the only
1-crossing-critical graphs: they each have crossing number at least one,
and every proper subgraph has crossing number less than one. In 1987,
Kochol exhibited an infi nite family of 3-connected, simple
2-crossing-critical graphs. Recently, a complete characterization of
2-crossing-critical graphs was finalized by Richter, Salazar, Oporowski,
and Bokal. An overview of this characterization will be presented in the
talk. In particular, we will introduce the concepts and some shorter
arguments needed in the proof of the following:

Let G be a 2-crossing-critical graph.
1. Then G has minimum degree at least two and is a subdivision of a
2-crossing-critical graph with minimum degree at least three.
Moreover, suppose G has minimum degree at least three. Then:
2. if G is 3-connected, then either G has a subdivision of V_{10} and a
very particular tile structure or has at most 3 million vertices; or
3. G is not 3-connected and is one of 49 particular examples; or
4. G is 2- but not 3-connected and is obtained from a 3-connected
example by replacing digons with digonal paths.

Symmetry breaking in infinite graphs

02. 12. 2013

Predavatelj: Wilfried Imrich (Montanuniversitaet, Leoben, Avstrija)

A coloring of the vertices of a graph G is called distinguishing if the stabilizer
of the coloring in the automorphism group of G is trivial. Tom Tucker
conjectured that, if every automorphim of a connected, locally finite graph moves
infinitely many vertices, then there exists a distinguishing 2-coloring, that is, a coloring
using only two colors. This is known as the infinite Motion Conjecture.
Despite many
intriguing partial results, it is still open in general.

This conjecture, its generalizations to uncountable graphs, to groups
acting on structures, and to endomorphims of countable and uncountable graphs and structures,
has become an inspiring topic and spawned numerous papers.

In this talk I will present generalizations of the Infinite Motion
Conjecture, to
random colorings on countable graphs, and other generalizations to
uncountable graphs. I will also shortly describe some of the methods used to obtain solutions
for various classes of graphs, this includes the permutation toplogy on countable sets and related topological spaces, in particular Polish spaces.

Grünberg-Kegel graphs and their applications

07. 10. 2013

Predavatelj: Anatolij Kondratjev (Ruska akademija znanosti, Jekaterinburg, Rusija)

Abstract: The prime graph of a group H, also known as the Gruenberg-Kegel graph GK(H), after Karl Gruenberg (1928-2007) and Otto Kegel (1934-), has as its vertex set all the prime divisors of the order |H| and two distinct vertices p, q are adjacent exactly when the group H contains an element of order pq. A survey of the main properties of Gruenberg-Kegel graphs will be given and some their applications to the finite group theory will be presented.

Distance magic graphs

14. 05. 2012

Predavateljica: Sylwia Cichacz

A emph{group distance magic labeling} or a $gr$-distance magic labeling of a graph $G(V,E)$ with $|V | = n$ is an injection $f$ from $V$ to an Abelian group $gr$ of order $n$ such that the weight $w(x)=sum_{yin N_G(x)}f(y)$ of every vertex $x in V$ is equal to the same element $mu in gr$, called the magic constant.
In the talk it will be presented that if $G$ is a graph of order $n=2^{p}(2k+1)$ for some natural numbers $p$, $k$ such that $deg(v)equiv c imod {2^{p+1}}$ for some constant $c$ for any $vin V(G)$, then there exists an $gr$-distance magic labeling for any abelian group $gr$ for the graph $G[C_4]$. Moreover we prove that if $gr$ is an arbitrary abelian group of order $4n$ such that $gr cong zet_2 timeszet_2 times gA$ for some abelian group $gA$ of order $n$, then exists a $gr$-distance magic labeling for any graph $G[C_4]$.

Group-irregular labelings of graphs

14. 05. 2012

Predavatelj: Marcin Anholcer

We investigate the textit{group irregularity strength} ($s_mathcal{G}(G)$) of graphs, i.e. the smallest value of $s$ such that taking any Abelian group $mathcal{G}$ of order $s$, there exists a function $f:E(G)rightarrow mathcal{G}$ such that the sums of edge labels in every vertex are distinct. In particular we prove that for any connected graph $G$ of order at least $3$, $s_mathcal{G} (G)=n$ if $nneq 4k+2$ and $s_mathcal{G} (G)leq n+1$ otherwise, except the case of some infinite family of stars. We investigate also the local version of the problem, this time we prove that $s=chi(G)$ or $s=chi(G)+1$ is enough with few exceptions.

Alliances in graphs with emphasis in Cartesian product

16. 04. 2012

Predavatelj: Ismael González Yero (University of Cádiz, Španija)

A defensive alliance in a graph G is a set A of vertices with the property that every vertex of A has at most one more neighbor outside of A than it has in A. An offensive alliance is a set B of vertices with the property that every vertex in the neighborhood of B has at least one more neighbor in B than it has outside of B. A set D of vertices of G is a dominating set for G if every vertex not in D is adjacent to at least one vertex of D. A defensive (an offensive) alliance is called global if it is also a dominating set. Several results on (defensive, offensive) alliances in graphs are presented in the talk, emphasizing in the case of global offensive alliances in Cartesian product graphs.
Vsi seminarji
Accessibility