# Dimacs home page of Robert Samal

My current web-page.
The following is my web-page from 199?.

I study in Prague (capital of Czech Republic), at the
Faculty of Mathematics and Physics
which is part of the Charles University.
I am a participant of this year's REU program. I work together
with Daniel Kral and Pavel Podbrdsky, our advisor
is Endre Szemeredi (and partly Janos Komlos).
We work on several problems in graph theory.

## Hamiltonian cycles

Let consider connected graphs with at least two vertices.
For a graph G denote by h(G) the minimal numer k, such that G^k is
Hamiltonian (we are taking the strong product of graphs
to get the power). It was proved by Bermond, Germa and
Heydemann that h(G) always exists and that G^k is Hamiltonian for any k >= h(G).
Our goal is to prove, that h(G) <= D, where
D is the maximal degree of vertex in G. We have already
proved, that

h(G) <= 13/12 . D + something small
h(G) <= 3 if D = 3 h(G) <= D for G being a star
(D vertices connected to a central one)
h(G) > c D, where c = ln 2 = 0.69...
On July 5 we suceeded to prove the conjecture,
we even got better bound then D. The proof will appear here soon.
## Shannon capacity

Shannon capacity is a interesting parameter of a graph, it is
extremely difficult to compute. (It took several decades to compute
it for pentagon, it is still unknown for cycle on seven vertices.)
There is a conjecture due to Moishe Rosenfeld, that the Shannon
capacity of a certain graph (complement of so-called Clebsch
graph) is 16^(1/3). This would by very interesting, since
this would be the very first example of a graph, for which the
Shannon capacity is the third root of an integer.
## Ramsey type questions for bipartite graph

Suppose you have the edges of complete graph on N vertices by two colors.
Classical Ramsey theorem says, you will alway find a complete subgraph on
n vertices, which has all its edges colored by the same color,
where n is approximately log N. There is also known a construction in which
you cannot find any larger complete graph. Our question is almost the same,
but instead of complete graph we are looking for a complete bipartite
graph with n vertices in each partite. It is known, that we can always
find graph with n approximately log N, there are construction showing
that you cannot do any better, than square root of N. Our goal is to
improve on of the bounds.
## Edge reconstruction

Let G, H be two graphs, let e_1, ..., e_m be edges of G,
f_1, ..., f_m edges of H, and suppose that for any i
graphs G \ e_i and H \ f_i are isomorphic.
Are G and H isomorphic as well?

There are two trivial counterexamples for m = 2 or 3.
So suppose, m >= 4. The Harary conjecture says, that
then G and H are isomorphic. There is a theorem
(due to Lovasz and Muller) that it is true for large m
(m > n log n), but the general case is still open.