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\).

05C45 Eulerian and Hamiltonian graphs
05C38 Paths and cycles
05C85 Graph algorithms (graph-theoretic aspects)
05C90 Applications of graph theory
Full Text: DOI
[1] Leighton, F.T., Introduction to parallel algorithms and architectures: arrays, trees, hypercubes, (1992), Morgan Kaufmann Publishers San Mateo, CA · Zbl 0743.68007
[2] 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)
[3] 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)
[4] Carle, J.; Myoupo, J.-F.; Seme, D., All-to-all broadcasting algorithms on honeycomb networks and applications, Parallel processing letters, 9, 539-550, (1999)
[5] Stojmenovic, I., Honeycomb networks: topological properties and communication algorithms, IEEE transactions on parallel and distributed systems, 8, 1036-1042, (1997)
[6] Megson, G.M.; Yang, X.; Liu, X., Honeycomb tori are Hamiltonian, Information processing letters, 72, 99-103, (1999) · Zbl 0999.68010
[7] Harary, F., Graph theory, (1972), Addison-Wesley Reading, MA · Zbl 0797.05064
[8] 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
[9] 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
[10] 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.