Home
Scholarly Works
The sum number of complete bipartite graphs
Chapter

The sum number of complete bipartite graphs

Abstract

For an integer r ≥ 1, consider a graph G r = (V, E) consisting of a connected undirected component G’ together with r isolated vertices K r 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 r 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’, the sum number σ= σ(G’) is defined to be the ainimua 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’ is a complete bipartite graph K p, q ≥ p ≥ 2, σ(K p, q ) = (3p+q-3)/2, and we show moreover p, q p, q how to label G σ correctly, thus solving problems posed by Harary.

Authors

Hartsfield N; Smyth WF

Book title

Graphs Matrices and Designs

Pagination

pp. 205-211

Publication Date

January 1, 2017

DOI

10.1201/9780203719916
View published work (Non-McMaster Users)

Contact the Experts team