On two problems regarding the Hamiltonian cycle game.

Hefetz, Dan; Stich, Sebastian

Displaying similar documents to “On two problems regarding the Hamiltonian cycle game.”

How long can a graph be kept planar?

Anuradha, V., Jain, Chinmay, Snoeyink, Jack, Szabó, Tibor (2008)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

Breaking symmetry on complete bipartite graphs of odd size.

Pikhurko, Oleg (2003)

Integers

Similarity:

Paths through fixed vertices in edge-colored graphs

W. S. Chou, Y. Manoussakis, O. Megalakaki, M. Spyratos, Zs. Tuza (1994)

Mathématiques et Sciences Humaines

Similarity:

We study the problem of finding an alternating path having given endpoints and passing through a given set of vertices in edge-colored graphs (a path is alternating if any two consecutive edges are in different colors). In particular, we show that this problem in NP-complete for 2-edge-colored graphs. Then we give a polynomial characterization when we restrict ourselves to 2-edge-colored complete graphs. We also investigate on (s,t)-paths through fixed vertices, i.e. paths of length...