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

On Jan 2, 6:11 pm, "Radoslaw Hofman" <rad...@xxxxxxxxx> wrote:
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?


Component is a sub graph which is connected.

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?

Here a_i is a arc belong a directed graph. As my definition |a_i fwd
a_j| >0 if and only if a_i fwd a_j with one vertex. So a_i fwd a_i is
always false. since all graph is simple graph( without loop and multi
arc or edge) begin section 2.


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

In my paper, the Cycle includes simple cycle and non simple cycle, in
other words, the Cycle can be disconnected.


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

It also works for directed graph, since fwd operator in my draft is
not commutative.

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

I could not very understand what your question. Digraph also has
strong connected concepts. In other words, given any pair vertices in
a digraph, if they can reachable, then the digraph is strong
connected.


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?


The first sentence of Page 3 is a condition c1 after I review my
draft. What is the draft version of your review? The e_i fwd x_j is
from 6th lines in my draft. Where e_i is an edge and x_j is a vertex
in an undirected graph. Thank your comments, I should define the fwd
operator for undirected graph.


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?

Sorry I confuse by your comments on my paper. Since I can not find
where the sentence "exists such e_i, x_j"... in my draft.


By the way, I checked my draft again which comes from http://arxiv.org/abs/0704.0309v3,
the created time is 2007-7-13 1:40:01.

--------------------------------------------------------------
Guohun Zhu
.

Relevant Pages