Solvable trees
A state of a simple graph G is an assignment of either a 0 or 1 to each of its vertices. For each vertex i of G, we define the move [i] to be the switching of the state of vertex i, and each neighbor of i, from 0 to 1, or from 1 to 0. The given initial state of G is said to be solvable if a sequence...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | text |
| Published: |
Animo Repository
2008
|
| Subjects: | |
| Online Access: | https://animorepository.dlsu.edu.ph/faculty_research/468 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | De La Salle University |
| Summary: | A state of a simple graph G is an assignment of either a 0 or 1 to each of its vertices. For each vertex i of G, we define the move [i] to be the switching of the state of vertex i, and each neighbor of i, from 0 to 1, or from 1 to 0. The given initial state of G is said to be solvable if a sequence of moves exists such that this state is transformed into the 0-state (all vertices have state 0.) If every initial state of G is solvable, we call G a solvable graph. We shall characterize here the solvable trees. © 2008 Springer Berlin Heidelberg. |
|---|