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