Journal of Combinatorics

Volume 8 (2017)

Number 2

Sum-free graphs

Pages: 349 – 370



S. C. Locke (Florida Atlantic University, Florida, U.S.A.)


An $n$-vertex graph is sum-free if the vertices can be labelled with $\{ 1, 2, \dotso , n \}$ such that no vertex gets a label which is the sum of the labels of two of its neighbours. We prove that non-complete graphs with average degree two or less are sum-free. We also prove that graphs with maximum degree three and at least seven vertices are sum-free.


graph labelling

Published 14 February 2017