Article ID Journal Published Year Pages File Type
419953 Discrete Applied Mathematics 2013 9 Pages PDF
Abstract

A finite simple graph GG is called a sum graph (respectively, integral sum graph) if there is a bijection  ff from the vertices of GG to a set of positive integers SS (respectively, a set of integers SS) such that uvuv is an edge of GG if and only if f(u)+f(v)∈Sf(u)+f(v)∈S. For graphs with nn vertices, we show that there exist sum graphs with mm edges if and only if m≤⌊14(n−1)2⌋ and that there exists integral sum graphs with mm edges if and only if m≤⌈38(n−1)2⌉+⌊12(n−1)⌋, except for m=⌈38(n−1)2⌉+⌊12(n−1)⌋−1 when nn is of the form 4k+14k+1. We also characterize sets of positive integers (respectively, integers) which are in bijection with sum graphs (respectively, integral sum graphs) of maximum size for a given order.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,