Maximal Strongly Indexable Graphs

Abstract

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,\dots ,p–1\}$ such that $f^{+}(E(G))=\{k,k+1,k+2,\dots ,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\le 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.