### Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 1429-1431 |

Number of pages | 3 |

Journal | Applied Mathematics Letters |

Volume | 22 |

Issue number | 9 |

DOIs | |

State | Published - Sep 2009 |

### Keywords

- Hamiltonian
- Hamiltonian connected
- WK-recursive network

## Fingerprint Dive into the research topics of 'Mutually orthogonal hamiltonian connected graphs'. Together they form a unique fingerprint.

## Cite this

Ho, T-Y., Lin, C-K., Tan, J-M., & Hsu, L-H. (2009). Mutually orthogonal hamiltonian connected graphs.

*Applied Mathematics Letters*,*22*(9), 1429-1431. https://doi.org/10.1016/j.aml.2009.01.058