On computing sets of integers with maximum number of pairs summing to powers of 2

arXiv2303.02872MaRDI QIDQ6428485FDOQ6428485

Authors: Max A. Alekseyev 

Publication date: 5 March 2023

Abstract: We address the problem of finding sets of integers of a given size with maximum number of pairs summing to powers of $2$. By fixing particular pairs this problem reduces to finding a labeling of the vertices of a given graph with pairwise distinct integers such that the endpoint labels for each edge sum to a power of $2$. We propose an efficient algorithm for this problem, which we use to determine the maximum size of graphs of order $n$ that admit such a labeling for all $nleq18$. We also identify the minimal forbidden subgraphs of order $leq11$, whose presence prevents graphs from having such a labeling.

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Other designs, configurations (05B30) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computer solution of Diophantine equations (11Y50)

This page was built for publication: On computing sets of integers with maximum number of pairs summing to powers of 2

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6428485)