IC-colorings and IC-indices of graphs (Q2568491)

The IC-index of a connected graph \(G\) is defined as the largest integer \(k\) with the following property: It is possible to assign positive integer labels to the vertices of \(G\) so that the labels sum to \(k\) and for any \(i=1,2,\dots,k-1\), there is a connected subgraph of \(G\) whose labels sum to \(i\). The definition is motivated by the postage stamp problem, studied in number theory. The authors determine IC-indices for several classes of graphs, providing the exact values for complete graphs and complete bipartite graphs \(K(m,n)\) in case \(m=1,2\) as well as estimates for paths, cycles, wheels and trees of diameter three.