On $(1,2)$-Strongly Indexable Spiders

Abstract

For any integers $k,d\ge 1$, a $(p,q)$-graph $G$ with vertex set $V(G)$ and edge set $E(G)$, where $p=|V(G)|$ and $q=|E(G)|$, is said to be $(k,d)$-strongly indexable (in short $(\mathbf{\text{k, d}})$-\textbf{SI}) if there exists a pair of functions $(f,f^{+})$ that assigns integer labels to the vertices and edges, i.e., $f:V(G)\to \{0,1,\dots ,p-1\}$ and $f^{+}:E(G)\to \{k,k+d,k+2d,\dots ,k+(q-1)d\}$, such that $f^{+}(u,v)=f(u)+f(v)$ for any $(u,v)\in E(G)$. We determine here classes of spiders that are $(1,2)$-SI graphs. We show that every given $(1,2)$-SI spider can be extended to an $(1,2)$-SI spider with arbitrarily many legs.