Re: Hamiltonian cycle problem in 2-connected bipartite cubic graph is Polynomial

Hi,



I have started to study your paper and I have some requests for
clarifications as I am not familiar with notation and vocabulary you are
using:



1. Theorem 1, c3 - what "components" do you mean?



2. Page 2 "It is obvious that |a_i fwd a_i| = 0" - why? As you are
considering also directed graphs you should make assumption about this?



3. Page 2 in - what does c1 state? Cycle is set of arcs such that for every
arc you can either reach "some other arc (a_j)" or from this other arc reach
another one? Such condition does not even assure about connectivity of this
set of arcs, because forward relation is limited to pair of arcs. Maybe you
should make some more assumptions about this graph (before this definition
there is no word about partitions).



4. Page 2 c2 - it works only for undirected graph.



5. Page 3 - c2 what dou you need "is a strong connected digraph" for? This
condition works only for undirected graph.



6. Page 3 - first sentence - I thought that forward relation was defined for
arcs. How then should I understand forward relation from arc to vertex e_i
fwd x_j?



7. Page 3 - first sentence - anyway this condition is very week because it
begins with "exists such e_i, x_j"... maybe it exists, but does it change
anything? I can imagine having any graph, add some edge and two vertexes
such that condition (whatever it is supposed to mean :-) ) will be
preserved - will it make graph bipartied?



To read further I need some answers for above.



Best regards,



Radek Hofman




.

Relevant Pages