By Theorem 1, the graph may also be solved with the initial hole in or 2. Alternately, an even path is formed by, ,, with a hole in. An even path is formed by, , with a hole in. įor, suppose the initial hole is in vertex. Solve the even path formed by the remaining pegs with a hole in. A similar argument holds for the case when the initial hole is in, , or. A similar argument holds when the initial hole is in, ,or. Solve the even cycle formed by the remaining pegs with a hole in. A similar argument holds if the initial hole is in, 3, or. By Theorem 1, the graph may also be solved with the initial hole in or. This subgraph is solvable with the final peg in by. An even path subgraph is formed by, , with a hole in. Note that the vertices and are symmetric.įor, suppose the initial hole is in vertex jump. The graph is solvable with the initial hole in vertex, ,, ,, or. The graph is solvable with the initial hole in vertex, ,, ,, ,, ,, ,, ,, , or. If is odd, then is distance 2-solvable with the initial hole in and the final two pegs in and. In, it was shown that is solvable with the initial hole in vertex and the final peg in, where. However, these graphs may be solvable from additional vertices as well. In the following result, we show that is solvable with the initial hole in several vertices. An exhaustive computer search was used to determine solvability. The list of trees comes from the appendix to Harary. In Figure 3, we list all nonisomorphic freely solvable trees with ten vertices or less. (ii) If is a -solvable spanning subgraph of, then is (at worst) -solvable.īecause of this observation, it is of particular interest to determine which trees are freely solvable. Hence, if there are holes in and and pegs elsewhere, then can be -solved from this configuration.
(i) If can be -solved with the initial hole in vertex and a jump is possible, then there is a first jump say. The following observation is also useful. It follows that is a starting state of with associated terminal state. Let and be the duals of and, respectively. Suppose that is a starting state of with associated terminal state. The following theorem allows the completion of the game in reverse by exchanging the roles of pegs and holes. Known examples of freely solvable graphs include the Petersen graph, the platonic solids, the Archimedean solids, the complete graph, and the complete -partite graph. We are motivated by the above comments to give examples of freely solvable graphs in this paper. Also shows that, if is freely solvable and is obtained by appending a pendent vertex to any vertex of, then is (at worst) solvable. However, determining whether a specific graph is freely solvable is NP-hard. In, it is shown that, of the nonisomorphic connected graphs on seven vertices or less, only are not freely solvable. The right graph in this figure is freely solvable.Īn example of an unsolvable, a solvable, and a freely solvable graph.
The middle graph in Figure 2 is solvable but not freely solvable. In Figure 2, the left graph is not solvable. A graph is distance 2-solvable if there exists some vertex so that, starting with a hole in, there exists an associated terminal state consisting of two pegs that are distance 2 apart. A graph is freely solvable if this is true for all vertices. Ī graph is solvable if there exists some vertex so that, starting with a hole in, there exists an associated terminal state consisting of a single peg. If there are pegs in vertices and and a hole in, then we allow the peg in to jump over the peg in into the hole in provided that.
For all undefined graph theory terminology, refer to West. Because of the restrictions of peg solitaire, we will assume that all graphs are finite, undirected, and connected graphs with no loops or multiple edges. A graph,, is a set of vertices,, and a set of edges. In, this notion is generalized to graphs.
0 kommentar(er)
