×

The spanning connectivity of the \((n,k)\)-star graphs. (English) Zbl 1103.68097

Summary: A \(k\)-container \(C(u, v)\) of a graph \(G\) is a set of \(k\)-disjoint paths joining \(u\) to \(v\). A \(k\)-container \(C(u, v)\) is a \(k^*\)-container if every vertex of \(G\) is incident with a path in \(C(u, v)\). A graph \(G\) is \(k^*\)-connected if there exists a \(k^*\)-container between any two distinct vertices \(u\) and \(v\). A \(k\)-regular graph \(G \) is super spanning connected if \(G\) is \(i^*\)-connected for all \(1\leq i\leq k\). In this paper, we prove that the \((n, k)\)-star graph \(S_{n,k}\) is super spanning connected if \(n\geq 3\) and \((n-k) \geq 2\).

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C40 Connectivity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Akers S. B., IEEE Trans. Comput. 38 pp 555– · Zbl 0678.94026 · doi:10.1109/12.21148
[2] Albert M., Australasian Journal of Combinatorics 24 pp 193–
[3] Bondy J. A., Graph Theory with Applications (1980)
[4] Chiang W. K., Information Processing Letters 56 pp 259–
[5] DOI: 10.1142/S0129054198000167 · Zbl 1319.68016 · doi:10.1142/S0129054198000167
[6] Hsu D. F., IEICE Trans, Fundamentals 77 pp 668–
[7] Hsu H. C., Networks 42 pp 189– · Zbl 1031.05079 · doi:10.1002/net.10096
[8] DOI: 10.1016/j.tcs.2005.02.007 · Zbl 1074.05054 · doi:10.1016/j.tcs.2005.02.007
[9] Menger K., Fund. Math. 10 pp 95–
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.