Prof.
Tomaž Pisanski
(University of Primorska and University of Ljubljana)
By shrinking a one-factor F in a cubic graph G an associated quartic graph
X = G/F is obtained. This construction arose recently in at least two unrelated
contexts. On the one hand the search for Hamilton cycles in G is related to the search of
some special sub quartic Eulerian subgraphs W of X. On the other hand
it was shown by Potočnik, Spiga and Verret that certain cubic...
Prof.
Elena Konstantinova
(Sobolev Institute of Mathematics, Novosibirsk, Russia)
In this talk we consider the hamiltonian problem for Cayley graphs having hierarchical structure (such as the hypercubes, the Pancake graphs, the Star graphs). Approaches and algorithms for getting hamiltonian cycles and paths are given. The connections to Gray codes are illustrated. Open problems are also discussed.
Marc Hellmuth
(Bioinformatics, Saarland University)
The ``usual'' Cartesian skeleton, established by Hammack and Imrich,
is a substructure of graphs and provides the essential information
in order to decompose given undirected graphs w.r.t. the direct and
the strong product.
In this talk, we discuss two generalizations of the Cartesian skeleton for undirected hypergraphs and directed graphs. These generalizations enable us to show that...
Prof.
Dragan Stevanovic
(University of Primorska, Koper, Slovenia and Mathematical Institute, SASA, Belgrade, Serbia)
I will present my recent results on characterization of trees with extremal values of Zagreb indices: trees with given maximum vertex degree and extremal value of the second Zagreb index, and trees with given independence number and extremal value of the first Zagreb index.
Mr
Riste Škrekovski
(FIŠ,FMF,FAMNIT,IMFM)
Let $G$ be a graph. The Wiener index of $G$, $W(G)$, is defined as the sum of distances between all pair of vertices of $G$.
Denote by $L^i(G)$ its $i$-iterated line graph. In the talk, we consider the equation $W(L^i(T)) = W(T)$ where $T$ is tree and $i\ge 1$.
Dr
Simona Bonvicini
(University of Modena and Reggio Emilia)
A proper edge-coloring of a graph $G$ is an assignment of colors to
the edges of $G$ such that adjacent edges receive distinct colors. A
proper edge-coloring defines at each vertex the set of colors of its
incident edges. Following the terminology introduced by
Hor\v{n}\'ak, Kalinowski, Meszka and Wo\'zniak, we call such a set
of colors the palette of the vertex. The minimum number of...
Prof.
Alexander Ivanov
(Imperial College London)
Let $\Gamma$ be a finite cubic graph, let $G$ be an edge-transitive automorphism group of $\Gamma$, let $\{x,y\}$ be an edge of $\Gamma$, and let ${\cal A}=\{G(x),G(y)\}$ be the amalgam formed by the corresponding vertex stabilizers. In a groundbreaking paper of 1980 D.M.Goldschmidt proved that $|G(x)|=|G(y)|$ divides $2^7 \cdot 3$ and that there are exactly fifteen possibilities for the...
Dr
Gabriel Verret
(University of Western Australia)
A permutation group is called semiregular if every point-stabiliser is trivial. Together with J. Morris and P. Spiga, we have characterised cubic graphs admitting a vertex-transitive group of automorphisms with an abelian normal subgroup that is not semiregular. While this looks rather technical, this result is surprisingly useful. We illustrate this by explaining how this result can be used...
Dr
Marko Orel
(University of Primorska; IMFM)
In the talk I will present several examples of cores, i.e., graphs possessing the property that all their endomorphisms are automorphisms. The examples will be mostly formed by some matrix structures.
Wilfried Imrich
(Montanuniversitaet Leoben)
We extend the definition of the Cartesian product to graphs with loops and show that the Sabidussi-Vizing unique prime factorization theorem for connected finite simple graphs still holds in this context for all connected finite graphs with at least one unlooped vertex.
We also prove that the prime factorization can be computed in O(m) time, where m is the size of the given graph.
Joint...
Dr
Francesco Belardo
(University of Messina)
In this talk we discuss some recent results on the Laplacian Spectral Theory of Signed graphs which extend and unify the more studied spectral theories of the Laplacian and the signless Laplacian of simple graphs.
Mrs
Nina Haug
(Alpen-Adria-Universität Klagenfurt / TU Graz)
We consider the following question: Among all trees that have the same (given) degree sequence, find a tree with the minimal number of subtrees.
While it is already known that the unique solution of the analogous maximisation problem is the "greedy tree", the solution of the minimisation problem is more com- plex. In the talk, we develop a polynomial time algorithm for finding an optimal...
Iztok Peterin
(FEECS, University of Maribor, Slovenia and IMFM, Ljubljana, Slovenia)
A walk $W$ between two non-adjacent vertices in a graph $G$ is
called tolled if the first vertex of $W$ is among vertices from $W$
adjacent only to the second vertex of $W$, and the last vertex of
$W$ is among vertices from $W$ adjacent only to the second-last
vertex of $W$. In the resulting interval convexity, a set $S\subset
V(G)$ is toll convex if for any two non-adjacent vertices...
