On \(\gamma\)-labelings of graphs (Q2811809)

This paper provides an answer to the question which graphs have a \(\gamma\)-max labeling consisting of one set of consecutive numbers. For complete bipartite graphs and complete graphs, \(\gamma\)-min and \(\gamma\)-max labelings are also characterized.NEWLINENEWLINEA \(\gamma\)-labeling of a graph \(G\) is a bijection \(f:V(G)\to\{0,1,2,\dots,m\}\) that induces a labeling \(f^\prime((u,v))=|f(u)-f(v)|\) of the edges of \(G\). Its value is defined as NEWLINE\[NEWLINE\mathrm{val}(f)=\sum\limits_{(u,v)\in E(G)}f^\prime((u,v)).NEWLINE\]NEWLINE The maximum value of a \(\gamma\)-labeling of \(G\) is defined as NEWLINE\[NEWLINE\mathrm{val}_{\max}(G) \max\mathrm{val}(f)|f\text{ is a }\gamma\text{-labeling of }G\}.NEWLINE\]NEWLINE A \(\gamma\)-labeling of \(G\) whose value is \(\mathrm{val}_{\max}(G)\) is called a \(\gamma\)-max labeling of \(G\). An analogous definitions are obtained for \(\min\) case.NEWLINENEWLINEThe authors also provide an alternative and improved proof for the well-known formula \(\mathrm{val}_{\max} (K_{r,s})=rs\left(rs-\frac12(r+s)+1\right)\).