Bounds for the gamma-number of graphs
Abstract
The gamma-number 7 (G) of a graph G is the smallest positive integer n for which there exists an injective function : V{G) {0,lM..,n} such that each uv € E(G) is labeled 1F (u) M -F(v)| and the resulting edge labels are distinct. The strong gamma-number 7∗ (G) of a graph G is defined to be the smallest positive integer n such that 7 (G) = n with the additional property that there exists an integer so that min { F (u), F (v)} << max{ F (u), F (v)} for each uv 6 E(G). The strong gammarnumber is defined to be +00, otherwise. In this paper, we prove that if G is a bipartite graph, then 7 (mG) < nry (G) + m - 1 for any positive integer m. We also show that ya (G) < +00 and 7, (G) < 27 (G) + 1 for any bipartite graph G. Moreover, we provide a sharp upper bound for 7 (G U H) in terms of 7 (G) and 7∗ (H) when G and H are graphs such that H is bipartite, and give formulas for the gamma-number of certain forests. In addition to these, we present strong gamma-number analogues of the gamma-number results. Finally, we determine the exact values of the gamma-number and strong gamma-number for all cycles. © 2018 Utilitas Mathematica Publishing Incorporated. All rights reserved.
