0
$\begingroup$

(It's wrong there is a separation even for for a graph with a basic Hamiltonian path.)

Let G(V,E) be a connected (no separation) directed graph, such that, $S_x$=V∖{x}, ∀x∈V is a subset of vertices of G. Then the induced subgraph G[$S_x$] is the graph whose vertex set is $S_x$ and whose edges set consists of all of the edges in E that have both endpoints in $S_x$.

Then a necessary condition (not sufficient see link Graph minus a point has at most 2 connected components for a counterexample) for a graph G(V,E) to have a Hamiltonian path (not necesarily a cycle) is that the induced subgraphs ∀x∈V, G[$S_x$] have at most 2 connected components.

Now, let G[$S_x$] have 2 disjoint nontrivial connected components, let's say that $S_x$ = $A_x \cup B_x$, then we say that:

$E_{-}$={$(a,b) \in E: \forall a \in A_x \forall b \in B_x \ | \ (a,x) \in E, (x,b) \in E$}

$E_{+}$={$(b,a) \in E: \forall a \in A_x, \forall b \in B_x \ | \ (b,x) \in E, (x,a) \in E$}

$E_x$={$(y,z) \in E: \forall y,z \in V, y \neq x, z \neq x$}

Then I want to either proof or find a counterexample of the following statement, if $\forall x \in V$ none of the graphs,

G(V\ {x}, $E_x \cup E_{+}$)

G(V\ {x}, $E_x \cup E_{-}$)

have a separation then G(V,E) has a Hamiltonian cycle.

(A separation of V are 2 disjoint nontrivial sets C and D, such that C $\cup$ D = V. I define a separation between two points in a graph G(V,E) $x, y \in V$ when I can't find a direct/undirect path from x to y in E) i.e.

$\begin{bmatrix} 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{bmatrix}$

Can't find a path from cities (1 and 2) to cities (3 and 4)

$\begin{bmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{bmatrix}$

Can't find a path from city 1 to cities (2, 3 and 4)

notice that the power of those matrices M^2, M^3 preserve the zeroes, so it should be easy to find a separation (hopefully in Polynomial time).

$\endgroup$
8
  • $\begingroup$ Start with an undirected graph G(V,E) (so that if it has a Hamiltonian path then the graph is connected sideways thus there can't be a separation of 2 cities) $\endgroup$
    – yugikaiba
    Jan 1, 2021 at 15:04
  • $\begingroup$ Your two subgraphs of the form $(V \setminus \{x\}, ...)$ are ill-defined because you cannot have edges incident to $x$ when $x$ is not present in your graph. I suppose what you propose could be described as: Take some graph $G_0$ and pick some order $v_0, ..., v_{n}$ and define $G_i$ as the graph $G_0[\{v_i, ...., v_n\}]$. Then $G_0$, the initial graph, has a HP if $G_i$ has at most $i + 1$ components? $\endgroup$ Jan 1, 2021 at 15:40
  • $\begingroup$ Also, your definition of "separation" doesn't make much sense to me as it stands, and I don't see how it relates to "separation between two points". $\endgroup$ Jan 1, 2021 at 15:57
  • 1
    $\begingroup$ If you want to edit to make it more comprehensible go ahead. $\endgroup$
    – yugikaiba
    Jan 1, 2021 at 16:01
  • $\begingroup$ I can't because I don't know what you mean to say in the first place. $\endgroup$ Jan 1, 2021 at 16:02

1 Answer 1

2
$\begingroup$

I'm assuming that you aim to find a polynomial time algorithm for deciding whether a graph has a Hamiltonian path.

Consider the undirected graph obtained from a cycle graph $C_n$ (with $n \geq 3$) and modifying it by taking two distinct vertices of the cycle and attaching (to each one) a new vertex. The resulting graph has no HP but is strongly connected and the removal of any vertex still leaves us with a strongly connected graph and thus has no "separation", leading to your algorithm falsely outputting that the original graph has a HP.

$\endgroup$
1
  • $\begingroup$ You have made a valiant effort to make sense of the OP, but since the OP puts the onus on us to "make it more comprehensible", I don't believe anyone can succeed in responding. $\endgroup$
    – hardmath
    Jan 4, 2021 at 18:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .