標題: Mutually orthogonal hamiltonian connected graphs
作者: Ho, Tung-Yang
Lin, Cheng-Kuan
Tan, Jimmy J. M.
Hsu, Lih-Hsing
資訊工程學系
Department of Computer Science
關鍵字: Hamiltonian;Hamiltonian connected;Interconnection networks
公開日期: 1-九月-2009
摘要: in this work, we concentrate on those n-vertex graphs G with n >= 4 and (e) over bar <= n - 4. Let P(1) = < u(1), u(2),..., u(n)) and P(2) = (v(1), v(2),..., v(n)) be any two hamiltonian paths of G. We say that P(1) and P(2) are orthogonal if u(1) = v(1), u(n) = v(n), and u(q) not equal v(q) for q is an element of {2, n - 1}. We say that a set of hamiltonian paths {P(1), P(2),..., P(s)} of G are mutually orthogonal if any two distinct paths in the set are orthogonal. We will prove that there are at least two orthogonal hamiltonian paths of G between any two different vertices. Furthermore, we classify the cases such that there are exactly two orthogonal hamiltonian paths of G between any two different vertices. Aside from these special cases, there are at least three mutually orthogonal hamiltonian paths of G between any two different vertices. (C) 2009 Elsevier Ltd. All rights reserved.
URI: http://dx.doi.org/10.1016/j.aml.2009.01.058
http://hdl.handle.net/11536/6773
ISSN: 0893-9659
DOI: 10.1016/j.aml.2009.01.058
期刊: APPLIED MATHEMATICS LETTERS
Volume: 22
Issue: 9
起始頁: 1429
結束頁: 1431
顯示於類別:期刊論文


文件中的檔案:

  1. 000267964200023.pdf

若為 zip 檔案,請下載檔案解壓縮後,用瀏覽器開啟資料夾中的 index.html 瀏覽全文。