Menu
Given any positive integer \( k \), a \((p,q)\)-graph \( G = (V, E) \) is strongly \( k \)-indexable if there exists a bijection \( f : V \to \{0,1,2,\ldots,p – 1\} \) such that \( f^+(E(G)) = \{k,k+1,k+2,\ldots,k+q-1\} \) where \( f^+(uv) = f(u) + f(v) \) for any edge \( uv \in E \); in particular, \( G \) is said to be strongly indexable when \( k = 1 \). For any strongly \( k \)-indexable \((p, q)\)-graph \( G \), \( q \leq 2p – 3 \) and if, in particular, \( q = 2p – 3 \) then \( G \) is called a maximal strongly indexable graph. In this paper, necessary conditions for an Eulerian \((p,q)\)-graph \( G \) to be strongly \( k \)-indexable have been obtained. Our main focus is to initiate a study of maximal strongly indexable graphs and, on this front, we strengthen a result of G. Ringel on certain outerplanar graphs.