The IC-indices of complete multipartite graphs. (English) Zbl 1387.05097

Summary: Given a connected graph \(G\), a function \(f\) mapping the vertex set of \(G\) into the set of all integers is a coloring of \(G\). For any subgraph \(H\) of \(G\), we denote as \(f(H)\) the sum of the values of \(f\) on the vertices of \(H\). If for any integer \(k \in \{1,2,\ldots,f(G)\}\), there exists an induced connected subgraph \(H\) of \(G\) such that \(f(H) = k\), then the coloring \(f\) is called an IC-coloring of \(G\). The IC-index of \(G\), written \(M(G)\), is defined to be the maximum value of \(f(G)\) over all possible IC-colorings \(f\) of \(G\). In this paper, we give a lower bound on the IC-index of any complete \(\ell\)-partite graph for all \(\ell \geq 3\) and then show that, when \(\ell = 3\), our lower bound also serves as an upper bound. As a consequence, the exact value of the IC-index of any tripartite graph is determined.


05C15 Coloring of graphs and hypergraphs
05C40 Connectivity
Full Text: DOI Euclid


[1] R. Alter and J. A. Barnett, A postage stamp problem, Amer. Math. Monthly 87 (1980), no. 3, 206-210. https://doi.org/10.2307/2321610 · Zbl 0432.10032
[2] R. K. Guy, Unsolved Problems in Number Theory, Second edition, Problem Books in Mathematics, Unsolved Problems in Intuitive Mathematics I, Springer-Verlag, New York, 1994. https://doi.org/10.1007/978-1-4899-3585-4 · Zbl 0805.11001
[3] R. L. Heimer and H. Langenbach, The stamp problem, J. Recreational Math. 7 (1974), no. 3, 235-250.
[4] C. T. Long and N. Woo, On bases for the set of integers, Duke Math. J. 38 (1971), 583-590. https://doi.org/10.1215/s0012-7094-71-03872-5 · Zbl 0219.10066
[5] W. F. Lunnon, A postage stamp problem, Comput. J. 12 (1969), no. 4, 377-380. https://doi.org/10.1093/comjnl/12.4.377
[6] S. Mossige, The postage stamp problem: an algorithm to determine the \(h\)-range on the \(h\)-range formula on the extremal basis problem for \(k = 4\), Math. Comp. 69 (2000), no. 229, 325-337. https://doi.org/10.1090/s0025-5718-99-01204-1 · Zbl 0935.11005
[7] S. G. Penrice, Some new graph labeling problems: a preliminary report, DIMACS Tech. Rep. 95-26 (1995), 1-9.
[8] E. Salehi, S.-M. Lee and M. Khatirinejad, IC-colorings and IC-indices of graphs, Discrete Math. 299 (2005), no. 1-3, 297-310. https://doi.org/10.1016/j.disc.2004.02.026 · Zbl 1082.05041
[9] E. S. Selmer, On the postage stamp problem with the three stamp denominations, Math. Scand. 47 (1980), no. 1, 29-71. https://doi.org/10.7146/math.scand.a-11874 · Zbl 0436.10027
[10] C.-L. Shiue and H.-L. Fu, The IC-indices of complete bipartite graphs, Electron. J. Combin. 15 (2008), no. 1, Research paper 43, 13 pp. · Zbl 1181.05077
[11] C.-L. Shiue and H.-C Lu, The IC-indices of some complete multipartite graphs. arXiv:1610.00238 · Zbl 1387.05097
[12] R. G. Stanton, J. A. Bate and R. C. Mullin, Some tables for the postage stamp problem, Proceedings of the Fourth Manitoba Conference on Numerical Mathematics (Winnipeg, Man., 1974), 351-356, Utilitas Math., Winnipeg, Man., 1975. · Zbl 0361.05014
[13] A. Stöhr, Gelöste und ungelöste Fragen über Basen der natürlichen Zahlenreihe I, II, J. Reine Angew. Math. 194 (1955), 40-65, 111-140. https://doi.org/10.1515/crll.1955.194.40 https://doi.org/10.1515/crll.1955.194.111
[14] D. B. West, Introduction to Graph Theory, Prentice-Hall, Upper Saddle River, NJ, 1996. · Zbl 0845.05001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.