An Addressing Scheme On Complete Bipartite Graphs

Abstract

For general graphs \(G\), it is known \([6]\) that the minimal length of an addressing scheme, denoted by \(N(G)\), is less than or equal to \(|G| – 1\). In this paper, we prove that for almost all complete bipartite graphs \(K_{m,n}\), \(N(K_{m,n}) = |K_{m,n}| – 2\).