Uniquely colorable graphs with minimum number of edges
Abstract
In this paper a uniquely K-colorable graph with minimum possible number of edges is being constructed. It is shown that the graph can be transformed into the set of all possible graphs of that kind (for any specified number of vertices) using only two kinds of transformations. It has been proven that all such graphs are (K – 1)-connected. An expression for the number of edges in such graphs is derived as well as some equations that have practical applications, in particular, in solving various optimization problems.
Published
2007-08-20
How to Cite
Velikohatiko, Y., & Mironov, A. (2007). Uniquely colorable graphs with minimum number of edges. Information and Control Systems, (4), 13-16. Retrieved from http://proceedings.spiiras.nw.ru/index.php/ius/article/view/14681
Issue
Section
Information processing and control