Spider web networks: a family of optimal, fault tolerant, Hamiltonian bipartite graphs
type: Item
instance of: scholarly article
title: Spider web networks: a family of optimal, fault tolerant, Hamiltonian bipartite graphs
zbMATH Open document ID: 1057.05052
author: Shin-Shin Kao
author: Lih-Hsing Hsu
published in: Applied Mathematics and Computation
publication date: 2005-02-23T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C90
zbMATH DE Number: 2137410
zbMATH Keywords: bipartite
zbMATH Keywords: \(1\)-edge Hamiltonian
zbMATH Keywords: \(1_p\)-Hamiltonian
zbMATH Keywords: optimal
reviewed by: Stanislav Jendroľ
MaRDI profile type: Publication
full work available at URL: j.amc.2003.06.005
OpenAlex ID: W2133063816
cites work: Q4002466
cites work: Honeycomb tori are Hamiltonian
cites work: Parallel concepts in graph theory
cites work: Christmas tree: a versatile 1-fault-tolerant design for token rings
cites work: Hamiltonian graphs with minimum number of edges for fault-tolerant topologies
cites work: Optimal 1-Hamiltonian graphs
DOI: 10.1016/J.AMC.2003.06.005
description: scientific article; zbMATH DE number 2137410