# Ljubljana - Leoben Graph Theory Seminar 2014

3-5 September 2014
UP FAMNIT, Koper, Slovenia
Europe/Ljubljana timezone
Home > Contribution List

## Contribution List

Displaying 21 contributions out of 21
Our aim in this talk is to report on a non-mainstream but interesting edge-colouring line of research we were conducting with our coauthor, friend, and colleague, David Cariolaro, prematurely disappeared this January. For me, the talk is also a tribute to David's memory. Yet, I (and David) would hope this to be a lively talk where the few techniques and results we could gather together get expos ... More
Presented by Prof. Romeo RIZZI
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 vertex-transiti ... More
Presented by Prof. Tomaž PISANSKI
For a finite group G and a subset S of G such that 1 is not in S the Cayley graph Cay(G,S) has vertex set G and arcs in the form (x,sx) where x runs over G and s runs over S. A Cayley graph Cay(G,S) is called a CI-graph if for every subset T with Cay(G,T) being isomorphic to Cay(G,S), T=f(S) for some automorphism f of G. The group G is called a DCI-group if every Cayley graph of G is a CI-graph, a ... More
Presented by Dr. István KOVÁCS
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.
Presented by Prof. Elena KONSTANTINOVA
Given a graph G, the problem of finding the minimum size maximal matching (MMM) is also known as the (independent) edge dominating set (EDS) in the literature. This problem, as well as several closely related problems, have been studied in the literature from several aspects such as computational complexity in special graph classes, approximation, exact solution procedures with experimental result ... More
Presented by Tinaz EKIM
Let rho(G) denote the number of convex cycles of a simple graph G of order n, size m, and girth 3 <= g <= n. It is proved that rho(G) <= (n/g)(m-n+1) and that equality holds if and only if G is an even cycle or a Moore graph. The equality also holds for a possible Moore graph of diameter 2 and degree 57 thus giving a new characterization of Moore graphs.
Presented by Jernej AZARIJA
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$.
Presented by Mr. Riste ŠKREKOVSKI
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 eve ... More
Presented by Marc HELLMUTH
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.
Presented by Prof. Dragan STEVANOVIC
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 distinc ... More
Presented by Dr. Simona BONVICINI
We state the following theorem: a generalized Petersen graph is the 1-skeleton of a regular map if and only if it belongs to the following set: {GP(4,1),GP(5,2),GP(8,3),GP(10,2),GP(10,3),GP(12,5),GP(24,5)}. These graphs are precisely those which are known to be the only arc-transitive generalized Petersen graphs; hence we only have to prove the if" part of our theorem. Five of the correspondin ... More
Presented by Prof. Gábor GÉVAY
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 isomorph ... More
Presented by Prof. Alexander IVANOV
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 to pr ... More
Presented by Dr. Gabriel VERRET
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.
Presented by Dr. Marko OREL
Call a colouring of a graph distinguishing if it is only preserved by the identity automorphism. Tucker conjectured that there is a distinguishing 2-colouring, if every non-trivial automorphism of a graph moves infinitely many vertices. While the general conjecture is still wide open, the statement is known to be true for many special graph classes. It also compares to a result for finite graphs: ... More
Presented by Florian LEHNER
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 work ... More
Presented by Wilfried IMRICH
75 years ago the question was raised for what we nowadays call the distance of vertices $0^n$ and $(p-1)^n$ in {\em Hanoi graph} $H_p^n$, $n,p\in\mathbb{N},\;p\geq 3$. O.~Dunkel pointed out that the two solutions submitted two years later by the proposer B.M.~Stewart and by J.~S.~Frame, depend on an unproved hypothesis, the truth of which having become known as the {\em Frame-Stewart Conjecture}. ... More
Presented by Prof. Andreas HINZ
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.
Presented by Dr. Francesco BELARDO
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 solution ... More
Presented by Mrs. Nina HAUG
The distance between two vertices $u,v \in V(G)$, denoted by $d(u,v)$, is the length of a shortest $u,v$-path in graph $G$. The distance between a vertex $v \in V(G)$ and a subset $P \subseteq V(G)$ is defined as $\min\{d(v,x) \, | \, x \in P \}$, and is denoted by $d(v,P)$. An ordered partition $\{P_1,P_2,\ldots , P_t\}$ of vertices of a graph $G$, is a resolving partition of $G$, if all the ... More
Presented by Marko JAKOVAC
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 \$x,y\in ... More
Presented by Iztok PETERIN