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$.