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.
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
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 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.
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.