# The sum number of the cocktail party graph

Miller, M., Ryan, J.F. and Smyth, W.F.
(1998)
*The sum number of the cocktail party graph.*
Bulletin of the Institute of Combinatorics and its Applications, 22
.
pp. 79-90.

## Abstract

A graph G is called a sum graph if there exists a labelling of the vertices of G by distinct positive integers such that the vertices labelled u and v are adjacent if and only if there exists a vertex labelled u + v. If G is not a sum graph, adding a finite number of isolated vertices to it will always yield a sum graph, and the sum number oe(G) of G is the smallest number of isolated vertices that will achieve this result. A labelling that realizes G + K oe(G) as a sum graph is said to be optimal. In this paper we consider G = H m;n , the complete n-partite graph on n 2 sets of m 2 nonadjacent vertices. We give an optimal labelling to show that oe(H 2;n ) = 4n \Gamma 5, and in the general case we give constructive proofs that oe(H m;n ) 2 \Omega\Gamma mn) and oe(H m;n ) 2 O(mn 2 ). We conjecture that oe(H m;n ) is asymptotically greater than mn, the cardinality of the vertex set; if so, then H m;n is the first known graph with this property. We also provide for the first time an optimal labelling of the complete bipatite graph Kmn whose smallest label is 1.

Publication Type: | Journal Article |
---|---|

Publisher: | The Institute of Combinatorics and its Applications |

Publishers Website: | http://bkocay.cs.umanitoba.ca/ICA/ |

URI: | http://researchrepository.murdoch.edu.au/id/eprint/27559 |

Item Control Page |

### Downloads

Downloads per month over past year