# zbMATH — the first resource for mathematics

Spider web networks: a family of optimal, fault tolerant, Hamiltonian bipartite graphs. (English) Zbl 1057.05052
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$$.

##### MSC:
 05C45 Eulerian and Hamiltonian graphs 05C38 Paths and cycles 05C85 Graph algorithms (graph-theoretic aspects) 05C90 Applications of graph theory
##### Keywords:
bipartite; $$1$$-edge Hamiltonian; $$1_p$$-Hamiltonian; optimal
Full Text:
##### References:
  Leighton, F.T., Introduction to parallel algorithms and architectures: arrays, trees, hypercubes, (1992), Morgan Kaufmann Publishers San Mateo, CA · Zbl 0743.68007  Chen, M.S.; Shin, K.G.; Kandlur, D.D., Addressing, routing, and broadcasting in hexagonal mesh multiprocessors, IEEE transactions on computers, 39, 10-18, (1990)  Youn, H.Y.; Lee, J.Y., An efficient dictionary machine using hexagonal processor arrays, IEEE transactions on parallel and distributed systems, 7, 166-273, (1996)  Carle, J.; Myoupo, J.-F.; Seme, D., All-to-all broadcasting algorithms on honeycomb networks and applications, Parallel processing letters, 9, 539-550, (1999)  Stojmenovic, I., Honeycomb networks: topological properties and communication algorithms, IEEE transactions on parallel and distributed systems, 8, 1036-1042, (1997)  Megson, G.M.; Yang, X.; Liu, X., Honeycomb tori are Hamiltonian, Information processing letters, 72, 99-103, (1999) · Zbl 0999.68010  Harary, F., Graph theory, (1972), Addison-Wesley Reading, MA · Zbl 0797.05064  Hung, C.N.; Hsu, L.H.; Sung, T.Y., Christmas tree: A versatile 1-fault tolerant design for token rings, Information processing letters, 72, 55-63, (1999) · Zbl 1338.68219  Mukhopadhyaya, K.; Sinha, B.P., Hamiltonian graphs with minimum number of edges for fault-tolerant topologies, Information processing letters, 44, 95-99, (1992) · Zbl 0768.68002  Wang, J.J.; Hung, C.N.; Hsu, L.H., Optimal 1-Hamiltonian graphs, Information processing letters, 65, 157-161, (1998) · Zbl 1338.68223
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.