The super spanning connectivity and super spanning laceability of tori with faulty elements. (English) Zbl 1310.68026
Summary: A \(k\)-container of a graph \(G\) is a set of \(k\) internally disjoint paths between two distinct vertices. A \(k\)-container of \(G\) is a \(k^*\)-container if it contains all vertices of \(G\). A graph \(G\) is \(k^*\)-connected if there exists a \(k^*\)-container between any two distinct vertices, and a bipartite graph \(G\) is \(k^*\)-laceable if there exists a \(k^*\)-container between any two vertices from different partite sets of \(G\). A \(k\)-connected graph (respectively, bipartite graph) \(G\) is super spanning connected (respectively, laceable) if \(G\) is \(r^*\)-connected (\(r^*\)-laceable) for any \(r\) with \(1 \leq r \leq k\). This paper shows that the two-dimensional torus \(\mathrm{Torus}(m, n)\), \(m, n \geq 3\), is super spanning connected if at least one of \(m\) and \(n\) is odd and super spanning laceable if both \(m\) and \(n\) are even. Furthermore, the super spanning connectivity and spanning laceability of tori with faulty elements have been discussed.
MSC:
| 68M10 | Network design and communication in computer systems |
| 05C38 | Paths and cycles |
| 05C40 | Connectivity |
| 68M15 | Reliability, testing and fault tolerance of networks and computer systems |
| 68R10 | Graph theory (including graph drawing) in computer science |
Keywords:
interconnection networks; tori; spanning connectivity; spanning laceability; container; fault-toleranceReferences:
| [1] | Albert M., Australasian Journal of Combinatorics 24 pp 193– (2001) |
| [2] | DOI: 10.1016/j.ipl.2004.06.006 · Zbl 1173.68599 · doi:10.1016/j.ipl.2004.06.006 |
| [3] | DOI: 10.1016/j.ipl.2011.10.010 · Zbl 1233.68028 · doi:10.1016/j.ipl.2011.10.010 |
| [4] | DOI: 10.1016/j.dam.2012.03.014 · Zbl 1244.05175 · doi:10.1016/j.dam.2012.03.014 |
| [5] | DOI: 10.1142/S0219265910002738 · doi:10.1142/S0219265910002738 |
| [6] | DOI: 10.1016/j.cor.2008.04.002 · Zbl 1177.90071 · doi:10.1016/j.cor.2008.04.002 |
| [7] | DOI: 10.1142/S0129054106003905 · Zbl 1103.68097 · doi:10.1142/S0129054106003905 |
| [8] | DOI: 10.1016/j.tcs.2011.04.045 · Zbl 1223.68083 · doi:10.1016/j.tcs.2011.04.045 |
| [9] | DOI: 10.1016/S0167-8191(99)00069-1 · doi:10.1016/S0167-8191(99)00069-1 |
| [10] | DOI: 10.1016/j.ins.2011.01.027 · Zbl 1216.68057 · doi:10.1016/j.ins.2011.01.027 |
| [11] | DOI: 10.1016/j.dam.2011.09.006 · Zbl 1238.68029 · doi:10.1016/j.dam.2011.09.006 |
| [12] | DOI: 10.1142/S0129054111008532 · Zbl 1222.68044 · doi:10.1142/S0129054111008532 |
| [13] | DOI: 10.1016/j.disc.2008.04.063 · Zbl 1221.05119 · doi:10.1016/j.disc.2008.04.063 |
| [14] | DOI: 10.1016/j.tcs.2005.02.007 · Zbl 1074.05054 · doi:10.1016/j.tcs.2005.02.007 |
| [15] | DOI: 10.1016/j.tcs.2007.05.002 · Zbl 1206.05060 · doi:10.1016/j.tcs.2007.05.002 |
| [16] | DOI: 10.1016/j.comcom.2007.05.028 · doi:10.1016/j.comcom.2007.05.028 |
| [17] | DOI: 10.1016/j.ins.2010.05.015 · Zbl 1205.68046 · doi:10.1016/j.ins.2010.05.015 |
| [18] | DOI: 10.1016/j.tcs.2011.04.035 · Zbl 1223.68086 · doi:10.1016/j.tcs.2011.04.035 |
| [19] | DOI: 10.1016/j.ipl.2004.05.013 · Zbl 1177.68031 · doi:10.1016/j.ipl.2004.05.013 |
| [20] | Xiang Y.H., Parallel and Distributed Computing and Systems 2 pp 77– (2009) |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
