Spider web networks: a family of optimal, fault tolerant, Hamiltonian bipartite graphs (Q1765415)

Let \(P(2r)\), \(r\geq2\), be a \(2r\)-gonal prisma with two \(2r\)-gonal faces \([a_1,a_2,\dots,a_{2r}]\), \([b_1,b_2,\dots,b_{2r}]\), and edges \(a_ia_{i+1},b_ib_{i+1}\) and \(a_ib_i\), \(i=1,2,\dots,2r\) (indices modulo \(2r\)). A {spider web network} SW\((m,n)\), \(m=2r\), \(n=2s\), \(r\geq2\), \(s\geq1\), is a graph obtained from \(P(m)=P(2r)\) by placing \(n\) vertices (in order) \(c^{(1)}_i,c^{(2)}_i,\dots,c^{(2s)}_i\) into the edge \(a_ib_i\) and inserting edges \(c^{(2k-1)}_{2i+1} c^{(2k-1)}_{2i+2}\) and \(c^{(2k)}_{2i} c^{(2k)}_{2i+1}\) for every \(i=1,2,\dots,r\) (indices modulo \(2r\)) and every \(k\), \(k=1,2,\dots,s\). Clearly SW\((m,n)\) is a bipartite planar Hamiltonian graph. Let \(C\) and \(D\) be a bipartition of the vertex set of SW\((m,n)\). In this paper it is proved that SW\((m,n)-e\) is Hamiltonian for every edge of SW\((m,n)\) and SW\((m,n)-\{c,d\}\) remains Hamiltonian for any \(c\in C\) and \(d\in D\).