2024/10/21 by Dheer Noal Desai, Runze Wang, Desai, Dheer Noal +1
Computer Science · Mathematics · #05C78 (Primary) 05C35 #11B13 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2410.16494
openalex publication_date 2024/10/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In a graph, we assign distinct integers to the vertices, and take the sum of two integers if they are on two adjacent vertices. The minimum possible number of different sums is the sum index of this graph. In this paper, we present some new developments on graph sum index. First, we explain the connections between graph sum index and results in additive combinatorics. Then, we determine the sum indices of the complete multipartite graphs, hypercubes, and some cluster graphs. Also, we study the maximum number of edges in a graph with a fixed sum index, which is related to the forbidden subgraph problem.