Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419953 | Discrete Applied Mathematics | 2013 | 9 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Apurv Tiwari, Amitabha Tripathi,