Weak-Vertex-Pancyclicity of (n, k)-Star Graphs
| Autor: | Ying-You Chen, 陳映攸 |
|---|---|
| Rok vydání: | 2008 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 96 The (n, k)-star graph (Sn,k for short) is an attractive alternative to the hypercube and also a generalized version of the n-star (Sn for short). It is isomorphic to the n-star (n-complete, Kn for short) graph if k = n?{1 (k = 1). Jwo et al. have already demonstrated in 1991 that an n-star contains a cycle of every even length from 6 to n!. Obviously, every edge in a Kn contained in cycles of length ranged from 3 to n. This work shows that every vertex in an Sn,k lies on a cycle of length l for every 3 = 6. For max{n–3, 2} = 4, each vertex in an Sn,k is contained in a cycle of length ranged from 6 to n!/(n–k)!. Moreover, each constructed cycle of an available length in an Sn,k can contain a desired 1-edge. Li has shown in 2005 that an Sn contains a cycle of every even length from 6 to n! when the number of faulty edges in the Sn does not exceed n–3. Xu et al. improved this result by showing that for any edge subset F of an Sn with |F| = 3. An Sn,k with one faulty edge is also investigated as follows. Every edge in an Sn,1 (Kn) lies on a cycle of length l for every 3 = 5 and every vertex in an S4,1 (K4) lies on a cycle of length 3 or 4. When 4 = 7, every vertex in an Sn,k contained in a cycle of length ranged from 3 to n!/(n–k)!. Additionally, when max{n–3, 3} = 5, each vertex in an Sn,k contained in a cycle of length ranged from 6 to n!/(n–k)!. Moreover, each constructed cycle of an available length in an Sn,k can contain a desired 1-edge. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|