The Sum Number of Complete Bipartite Graphs

For an integer r ≥ 1, consider a graph G_r = (V,E) consisting of a connected undirected component G^t together with r isolated vertices K ¯ r https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780203719916/6ef71bf2-a4fa-438b-9c98-58b1246952d2/content/inequ13_205_1.tif"/> . Let L : V —-> Z ⁺ denote a labelling of the vertices of G_r with distinct positive integers. G_r is said to be a sum graph if there exists a labelling L such that for every vertex pair u and v of V, (u,v) ∈ E if and only if there exists a vertex w ∈ V whose label L(w) = L(u) + L(v). For a given connected component G^r, the sum number σ = σ(G^t) is defined to be the minimum over all integers r for which G_r is a sum graph. It has been shown that for a complete graph on n ≥ 4 vertices, σ(K_n) = 2n-3, and that for a non-trivial tree, σ(T) =1. In this paper we prove that when G^r is a complete bipartite graph K_p,q, q ≥ p ≥ 2, σ(K_p,q) = ⌜(3p+q−3)/2⌝, and we show moreover how to label G_σ correctly, thus solving problems posed by Harary.