Control Systems and Computers

DOI: https://doi.org/10.15407/usim.2017.03.020

Upr. sist. maš., 2017, Issue 3 (269), pp. 20-25.

UDC 519.17

Sherman Zoya O., Post-graduate student at V.M.Glushkov Institute of Cybernetics of National Academy of Sciences of Ukraine, Mikhailovskaya str., 1 apt 4, Кropivnitskij, Ukraine 25015, E-mail: sherman.zoya@gmail.com 

Methods of Constructing Square Difference Labeling

 Introduction.  The urgency of the graceful labeling of graphs, namely, the problem of Kotzig-Ringel Rosa brought a wave of different methods of labeling graphs. In particular, one of the constructive approach of finding graceful trees of large size from the known graceful trees was offered by R. Stanton, C. Zarnke, K. Koh, D. Rogers, T. Tan. K. Koch, D. Rogers and T. Tan have completed the construction of a new graph, adding to the disjunctive union of isomorphic copies of a given graceful graph T an additional vertex connected by its edges to isomorphic images of some fixed vertex of T. This method is used to study gracefulness of the symmetrical trees. The same authors generalized this method by identifying isomorphic images of a fixed vertex of T, with the additional vertex. The construction of a graceful tree is implemented for a given pair of graceful trees and named Δ-constructing. Using it, K. Koh and others proved gracefulness of full m-arch tree.

Methods and results. The methods of construction of square difference trees are applied. A new square difference tree is built from one square difference tree by identifying vertices with the greatest label of the isomorphic copies of the tree and using a new vertex and edges connecting the isomorphic copies of the square difference of a tree with the vertex. A method of Δ-constructing a square difference tree from two square difference trees is used.

Conclusion. The class of square differential trees is expanded. Methods used to build square difference tree can be applied in further theoretical studies.

Download full text (In Russian)!

Keywords: square difference labeling, square difference graph, Δ-construction.

1. Ringel, G., 1963. Problem 25, Theory of Graphs and Its Applications, Proc. Symp., Smolenice, Czech. Acad. Sci. 162 p.
2. Rosa, A., 1967. “ On certain valuations of the vertices of a graph. Theory of Graphs”. Int. Symp., Rome, July. 1966, Gordon and Breach, New York and Dunod Paris, pp. 349–355.
3. Bermond, J., 1979. “Graceful graphs, radio antennae and French windmills”. Graph Theory and Combinatorics, pp. 18–37.
4. Stanton, R., Zarnke, C., 1973. “Labeling of balanced trees”. Proc. 4th Southeast Conf. Combin. Graph Theory, Computing., pp. 479–495.
5. Koh, K.M., Rogers, D.G., Tan, T., 1977. “On graceful trees”. Nanta Mathematics, 10(2), pp. 207–211.
6. Koh, K.M., Rogers, D.G., Tan, T., 1979. “Two theorems on graceful trees”. Discrete Mathematics, 25, pp. 41–148.
   https://doi.org/10.1016/0012-365X(79)90016-5
7. Koh, K.M., Rogers, D.G., Tan, T., 1980. “Products of graceful trees”. Discrete Mathematics, 31, pp. 279–292.
   https://doi.org/10.1016/0012-365X(80)90139-9
8. Ajitha, V.,  Princy, K.L., Lokesha V. et al., 2012. “On square difference Graphs”.  Int. J. of Mathematical Combinatorics, 1 (1), pp. 31–40.
9. Sherman, Z.A., 2016. “Square difference marking of loops and circuits”. Sci.-Tech. conf. “Computer science, mathematics, automation“, Sumy, April, 18–22, pp. 251.

Received 07.03.2017