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

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.

Naproti kombinatorični karakterizaciji ekvistabilnih grafov – delni rezultati o Orlinovi domnevi

02. 04. 2012

Predavatelj: Martin Milanič

Ekvistabilni grafi so grafi, za katere obstaja linearen funkcional, ki karakterizira maksimalne neodvisne množice grafa. (Neodvisna množica v grafu je množica paroma nepovezanih točk.) Leta 2009 je Jim Orlin postavil domnevo, da je vsak ekvistabilni graf splošni particijski graf, tj., presečni graf take družine D podmnožic končne množice S, da maksimalne neodvisne množice grafa ustrezajo natanko particijam množice S z elementi iz družine D.
Znano je, da je Orlinova domneva pravilna za razred tetivnih grafov in za grafe brez asteroidalnih trojic. Če domneva drži tudi v splošnem, podaja kombinatorično karakterizacijo ekvistabilnih grafov. Na predavanju bomo razložili znane relacije med splošnimi particijskimi grafi, ekvistabilnimi grafi in t.i. trikotniškimi grafi ter obravnavali nekaj delnih rezultatov o Orlinovi domnevi. Med drugim bomo predstavili popolno karakterizacijo ekvistabilnih grafov, ki so netrivialni kartezični ali tenzorski produkti.

Skupno delo s Štefkom Miklavičem.

Greedy trees, caterpillars, and Wiener-type graph invariants

16. 01. 2012

Predavateljica: Nina Schmuck (TU Graz, Avstrija)

The extremal questions of maximising or minimising various distance-based graph invariants among trees with a given degree sequence have been vigorously studied. In many cases, the so-called greedy tree and some caterpillars are found to be extremal. Therefore, the following question naturally arises: What do the distance-based graph invariants look like when the optimal solution of the minimisation problem is the greedy tree and, analogously, when the optimal solution of the maximisation problem is a caterpillar.

We obtain that the greedy tree is optimal for all graph invariants of the form [W_f(T) = sum_{{u,v} subseteq V(T)} f(d(u,v))], for any nonnegative, nondecreasing function $f$. Furthermore, if $f$ is any increasing, convex function, we find that $W_f(T)$ is maximised by a caterpillar. From this result, we also achieve a partial characterisation of the structure of the extremal caterpillars.

Additionally, our solutions of both the minimisation and the maximisation problems include not only the classical Wiener index ($f(x)=x$), but also the hyper-Wiener index ($f(x)=frac{x(x+1)}{2}$) and the generalised Wiener index ($f(x)=x^{alpha}$ with $alpha > 1$).

 
Joint work with Stephan Wagner and Hua Wang.
Vsi seminarji
Accessibility