Weak-vertex-pancyclicity of (n, k)-star graphs
| Autor: | Jung-Sheng Fu, Dyi-Rong Duh, Tai-Ling Ye, Ying-You Chen |
|---|---|
| Jazyk: | angličtina |
| Předmět: |
Discrete mathematics
Vertex (graph theory) General Computer Science Complete graph n-star graph Star (graph theory) Interconnection networks Graph Theoretical Computer Science Combinatorics (n k)-star graph Cycle embedding Embedding Weak-vertex-pancyclicity Hypercube Computer Science(all) Mathematics |
| Zdroj: | Theoretical Computer Science. (1-3):191-199 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2008.01.035 |
| Popis: | The (n,k)-star graph (S"n","k for short) is an attractive alternative to the hypercube and also a generalized version of the n-star. It is isomorphic to the n-star (n-complete) 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!. This work shows that every vertex in an S"n","k lies on a cycle of length l for every [email protected][email protected]?n!/(n-k)! when [email protected][email protected]?n-4 and n>=6. Additionally, for [email protected][email protected]?n-2, each vertex in an S"n","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 S"n","k can contain a desired 1-edge. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|