![](https://csdnimg.cn/release/download_crawler_static/11580815/bg3.jpg)
2. The steps to determine whether an arbitrary undirected planar graph
except the one of knight’s tour is a Hamiltonian
It is very difficult to find a best large spanning subgraph which is a maximal
planar graph from a non-planar graph G
0
since there are many spanning subgraphs
of G
0
which are maximal planar graphs. One does not know it is in the class P or in
the class NP, so one begins his determination starting from an arbitrary undirected
planar graph.
The deciding whether an arbitrary undirected planar graph is a Hamiltonian, or
not, is very complex. There are some steps for this work. Those are as follows:
(a) Determining whether an arbitrary undirected graph G is a connected graph
or not, namely, determining ω(G) = 1 or ω(G) > 1, here ω(G) is the number of the
connected component in G. If there is ω(G) > 1, one should decide the graph isn’t
the Hamiltonian.
(b) If G is a sole block of planar graph, one should determine whether there is
a vertex cut or edge cut in G, or not. If there is, one should determine G is sole
connected, not 2-connected, then one should decide G isn’t a Hamiltonian; if there
isn’t any cut set, then go on.
(c) Determine whether all vertices are on the periphery cycle of G. If those are,
then decide the G is a trivial Hamiltonian and stop the procedure; if those aren’t,
then go on.
(d) Determine whether there exists at least a cut-off-able edge, and or even it is
openable, on the periphery cycle of G. And if there is not so, then decide G is a
non-Hamiltonian; if so, then cut it and go to next.
(e) Elect in order all distinct combinations of cut-off-able edges to cut them off,
respectively, and determine whether there is a spanning subgraph which still is 2-
connected and in which there
a cycle through every vertices exactly once in those spanning subgraphs of G.
If there is, then decide G is a Hamiltonian; if there isn’t, then decide G is a non-
Hamiltonian.
3. The maximal number of the edges allowed to be really cut off for a
Hamiltonian
Although there are many cut-off-able edges in a graph G, a few of those edges can
really be cut off for a Hamiltonian. Since the number of edges is equivalent to that
of vertices in a Hamiltonian cycle, after cut some cut-off-able edges the number of
rest edges needs to be that of all vertices in G, otherwise, there must not exist any
Hamiltonian cycle.
There is a graph G such that the order is n and the size is m. And one lets m
c
be the number of cut-off-able edges of which the degrees of two end vertices are ≥ 3,
individually, and lets m
c,r
be the maximal number of the edges allowed to be really
cut off. Hence, in a Hamiltonian there is
(1) m
c,r
= m − n.
3
http://www.paper.edu.cn