Journal of Combinatorics

Volume 8 (2017)

Number 2

Sum-free graphs

Pages: 349 – 370

DOI: https://dx.doi.org/10.4310/JOC.2017.v8.n2.a7

Author

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

Abstract

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.

Keywords

graph labelling

Published 14 February 2017