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.