Solvable trees
College
College of Science
Department/Unit
Mathematics and Statistics Department
Document Type
Conference Proceeding
Source Title
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume
4535 LNCS
First Page
79
Last Page
84
Publication Date
12-1-2008
Abstract
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.
html
Digitial Object Identifier (DOI)
10.1007/978-3-540-89550-3-8
Recommended Citation
Gervacio, S. V., Lim, Y. F., & Ruivivar, L. A. (2008). Solvable trees. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 4535 LNCS, 79-84. https://doi.org/10.1007/978-3-540-89550-3-8
Disciplines
Mathematics
Keywords
Graph theory
Upload File
wf_no
