A construction method of mininal graceful graph based on least scale number on ruler
[Objective]For any positive integern≥2,it is possible to measure all lengths from 1 to n by carving at least a few scales on an ungraduated ruler of length n.This is the problem of the ruler with the least number of scales.Given a positive integer n,there exists a set of m integers {ai},which satisfies 0=a1＜a2＜…＜am=n,so that any integer s(0≤s≤n)can be expressed as the difference aj-ai between the two elements in the set.Therefore,{ai } is called the restricted difference basis on n.The ruler with the least number of divisions,restricted difference basis,and representation of graceful graphs are three unresolved mathematical problems.[Methods]According to the definitions of minimal graceful graphs and restricted difference basis,the construction of"ruler with the least number of divisions","minimal graceful graph",and"restricted difference basis"is the same mathematical problem.[Results]The conclusion is that Kn is not a graceful graph when n≥5,and K4+Kn is a graceful graph when n≥1.The upper and lower bounds on the number of vertices of minimal graceful graphs with edges ranging from 6 to 82 are obtained;The graceful labels of graphs K3∨K1,3,n-3e,K3,n ∨ K3-e and K2,3,n ∨ K3-7e are given using construction methods,thus proving that these three types of graphs are all graceful graphs.Moreover,when0≤n≤9,K3 ∨ K1,3,n-3e and K2,3,n ∨ K3-7e are all extremely graceful graphs.When 0≤n≤8,K3,n ∨ K3-eare all extremely graceful graphs,and 29 sets of scale values for the most economical rulers are given.[Conclusions]As the length n of the ruler increases,a set of scale values for this ruler needs to be calculated.Minimum scale value will become very difficult.At present,there is no literature on using the method of constructing graceful graphs to obtain the most economical scale value design.This article proposes a new approach to solve the problems of the most economical scale and restricted difference basis by using the method of constructing minimal graceful graphs.
least scale number on rulergraceful graphjoin graphsminimal graceful graphgraceful labeling
万方数据
维普
