Shiue, Chin-Lin; Fu, Hung-Lin

The IC-indices of complete bipartite graphs

Electron. J. Comb. 15(1), Research Paper R43, 13 p. (2008)


Summary: Let G be a connected graph, and let f be a function mapping V (G) into N. We define f (H) = v$\in V$ (H) f (v) for each subgraph H of G. The function f is called an IC-coloring of G if for each integer k in the set ${1, 2, \cdot \cdot \cdot , f (G)}$ there exists an (induced) connected subgraph H of G such that f (H) = k, and the IC-index of G, M (G), is the maximum value of f (G) where f is an IC-coloring of G. In this paper, we show that M (Km,n) = $3 \cdot $2m+n - 2 - 2m - 2 + 2 for each complete bipartite graph Km,n, $2 \leq m \leq n$.

Mathematics Subject Classification