On the spanning \(w\)-wide diameter of the star graph. (English) Zbl 1107.05055
Summary: Let \(u\) and \(v\) be any two distinct nodes of an undirected graph \(G\), which is \(k\)-connected. A container \(C(u,v)\) between \(u\) and \(v\) is a set of internally disjoint paths \(P_1,P_2,\dots,P_w\) between \(u\) and \(v\) where \(1\leq w\leq k\). The width of \(C(u,v)\) is \(w\) and the length of \(C(u,v)\) (written as \(I[C(u,v)])\) is \(\max\{I (P_i)\mid 1\leq i\leq w\}\). A \(w\)-container \(C(u,v)\) is a container with width \(w\). The \(w\)-wide distance between \(u\) and \(v\), \(d_w(u,v)\), is \(\min\{I(C(u,v))\mid C(u,v)\) is a \(w\)-container}. A \(w\)-container \(C(u,v)\) of the graph \(G\) is a \(w^*\)-container if every node of \(G\) is incident with a path in \(C(u,v)\). That means that the \(w\)-container \(C(u,v)\) spans the whole graph. Let \(S_n\) be the \(n\)-dimensional star graph with \(n\geq 5\). It is known that \(S_n\) is bipartite. In this article, we show that, for any pair of distinct nodes \(u\) and \(v\) in different partite sets of \(S_n\), there exists an \((n-1)^*\)-container \(C(u,v)\) and the \((n-1)\)-wide distance \(d_{(n-1)}(u,v)\) is less than or equal to \(\frac{n!}{n-2}+1\). In addition, we show the existence of a \(2^*\)-container \(C(u,v)\) and the 2-wide distance \(d_2(u,v)\) is bounded above by \(\frac {n!}{2}+1\).
MSC:
| 05C45 | Eulerian and Hamiltonian graphs |
References:
| [1] | Akers, IEEE Trans Comput 38 pp 555– (1989) |
| [2] | Albert, Aust J Combin 24 pp 193– (2001) |
| [3] | Bagherzadeh, IEEE Trans Comput 45 pp 475– (1996) |
| [4] | , Graph theory with applications, North Holland, New York, 1980. |
| [5] | Bouabdallah, Theory Comput Syst 31 pp 279– (1998) |
| [6] | Chang, Inform Process Lett 92 pp 15– (2004) |
| [7] | Fragopoulou, J Parallel Distrib Comput 24 pp 55– (1995) |
| [8] | Fragopoulou, IEEE Trans Comput 45 pp 174– (1996) |
| [9] | Gu, Inform Process Lett 56 pp 29– (1995) |
| [10] | Hsieh, Theor Comput Sci 337 pp 370– (2005) |
| [11] | Hsieh, Networks 36 pp 225– (2000) |
| [12] | Hsieh, Theor Comput Sci 262 pp 215– (2001) |
| [13] | Hsieh, IEEE Trans Comput 50 pp 960– (2001) |
| [14] | Hsu, IEICE Trans Fundam E77-A pp 668– (1994) |
| [15] | Jwo, J Circuits Syst Comput 1 pp 43– (1991) |
| [16] | Latifi, Inform Process Lett 46 pp 143– (1993) |
| [17] | Introduction to parallel algorithms and architectures: Arrays \.c trees \.c hypercubes, Morgan Kaufmann, San Mateo, CA, 1992. |
| [18] | Li, Inform Sci 165 pp 59– (2004) |
| [19] | Lin, Theor Comput Sci 339 pp 257– (2005) |
| [20] | , , , The spanning diameter of the star graphs, 2004 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN’04), IEEE Computer Society Press, 2004, pp. 551–556. |
| [21] | Menger, Fundam Math 10 pp 95– (1927) |
| [22] | Miller, IEEE Trans Comput 43 pp 13– (1994) |
| [23] | Park, J Parallel Distrib Comput 64 pp 1286– (2004) |
| [24] | Rouskov, J Parallel Distrib Comput 33 pp 91– (1996) |
| [25] | Almost all n-dimensional rectangular lattices are Hamilton-laceable, Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing, 1978, pp. 649–661. |
| [26] | Tsai, Inform Process Lett 91 pp 293– (2004) |
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.
