2021/03/01 by Gao, Zhen-Bin, Lau, Gee-Choon, Shiu, Wai-Chee · 1 citation
#05C69 #05C78 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2103.00724
For any graph G of order p, a bijection f: V(G)→ [1,p] is called a numbering of the graph G of order p. The strength strf(G) of a numbering f: V(G)→ [1,p] of G is defined by strf(G) = max\f(u)+f(v) | uv∈ E(G)\, and the strength str(G) of a graph G itself is str(G) = min\strf(G) | f is a numbering of G\. A numbering f is called a strength labeling of G if strf(G)=str(G). In this paper, we obtained a sufficient condition for a graph to have str(G)=|V(G)|+\d(G). Consequently, many questions raised in [Bounds for the strength of graphs, \it Aust. J. Combin. \bf72(3), (2018) 492--508] and [On the strength of some trees, \it AKCE Int. J. Graphs Comb. (Online 2019) doi.org/10.1016/j.akcej.2019.06.002] are solved. Moreover, we showed that every graph G either has str(G)=|V(G)|+\d(G) or is a proper subgraph of a graph H that has str(H) = |V(H)| + \d(H) with \d(H)=\d(G). Further, new good lower bounds of str(G) are also obtained. Using these, we determined the strength of 2-regular graphs and obtained new lower bounds of str(Qn) for various n, where Qn is the n-regular hypercube.