一圖形(graph) G由一有限且非空點集合(vertex set)與一邊集合(edge set)所組成。一條連接u和v兩點的路徑之中最短的，我們稱之為u-v最短路徑(u-v geodesic)。在一圖形G中uv兩點之間的最短距離代表u-v最短路徑上的邊數，表示成dG(u,v)。一個有n個點的圖形G，假如每一個邊都包含於一個長度從3到n的迴圈(cycle)之中，則G被稱為邊泛圈(edge-pancyclic)圖。在一個圖形G中，假如對任兩點而言，都存在各種長度從dG(u,v)到n-1的路徑連接這兩點，則G被稱為泛連通(panconnected)圖。明顯地，所有泛連通圖都是邊泛圈圖。源自邊泛圈圖的特性，我們提出最短路徑泛圈圖。在一個有n個點的圖形G中，對任兩點u和v而言，假如每一條u-v最短路徑都包含於各種長度從max{2dG(u,v),3}到n之間的迴圈上，則稱G為最短路徑泛圈(geodesic-pancyclic)圖。因為雙分圖(bipartite graph)沒有長度為奇數的迴圈，所以我們提出最短路徑泛偶圈(geodesic-bipancyclicity)的性質。在一個有n個點的雙分圖G中，對任兩點u和v而言，假如每一條u-v最短路徑都包含於各種偶數長度從max{2dG(u,v),4}到n之間的迴圈上，則稱G為最短路徑泛偶圈圖。

在這篇論文之中，我們首先分析這些已知的漢米爾頓相關(Hamiltonian-like)性質之間的關係，尤其是針對泛連通特性與最短路徑泛圈特性。我們證明出若泛連通圖的類別沒有包含最短路徑泛圈圖的類別，就是兩者沒無互相的直接包含關係。接著，我們對於兩種立方體相似(cube-like)的圖形，討論其最短路徑泛圈特性。我們證明維度k的超立方體(hypercube, Qk)是最短路徑泛偶圈圖形，以及維度k的擴增立方體(augmented cube, AQk)是最短路徑泛圈圖形，其中k>=2。我們也討論擴增立方體的容錯(fault-tolerant) 泛連通特性。我們證明出AQk−f仍是泛連通圖，其中f為一壞點或壞邊且k>=3。此外，我們致力研究判斷是否為最短路徑泛圈圖的充分條件。因為判斷一圖形是否是漢米爾頓的問題仍是NP-complete，所以探索出許多漢米爾頓圖的充分條件。這些充分條件也都推廣在後來的許多漢米爾頓相關圖形，其中也包括泛連通圖。我們證明出大部分已知用在泛連通圖的充份條件，都正好能適用在最短路徑泛圈圖上。

A graph G is a finite nonempty vertex set V(G), together with an (possible empty) edge set E(G) of 2-element subset of V (G). A shortest path connecting two vertices u and v is called a u-v geodesic. The distance between u and v in a graph G, denoted by dG(u,v), is the number of edges in a u-v geodesic. A graph G with n vertices is edge-pancyclic if every edge of G belongs to an l-cycle for every 3<=l<=n. G is called panconnected if, for each pair of vertices u,v in V(G) and for each integer l with dG(u,v)<=l<=n−1, there is a path of length l in G that connects u and v. Clearly, all panconnected graphs are indeed edge-pancyclic. We introduce geodesic-pancyclicity inspired with the property of edge-pancyclicity in graphs. A graph G is geodesic-pancyclic if, for each pair of vertices u,v in V(G), every u-v geodesic lies on every cycle of length l satisfying max{2dG(u,v),3}<=l<=n. Since there is no cycle with odd length in bipartite graphs, we discuss the geodesic-bipancyclicity of bipartite graphs. A bipartite graph G with n vertices is geodesic-bipancyclic if, for each pair of vertices u,v in V(G), every u-v geodesic lies on every even cycle of length l satisfying max{2dG(u,v),4}<=l<=n.

In this dissertation, we first analyze the relationship between these Hamiltonianlike properties, especially for panconnectivity and geodesic-pancyclicity. Then, we discuss geodesic-pancyclicity on two cube-like graphs. We prove that hypercube Qk is geodesic-bipancyclic with dimension k<=2, and augmented cube AQk is geodesic-pancyclic with dimension k<=2. We also discuss fault-tolerant panconnectivity of AQk. We show that AQk−f is panconnected if f is a vertex or an edge of AQk with dimension k>=3. Furthermore, we study sufficient conditions of geodesic-pancyclic graphs. In particular, we show that most of the known sufficient conditions of panconnected graphs also hold true on geodesic-pancyclic graphs.

[1] Y. Alavi and J. E. Williamson, Panconnected graphs, Studia Scientiarum Mathematicarum Hungarica 10 (1975) 19–22.
[2] T. Araki and Y. Shibata, Pancyclicity of recursive circulant graphs, Information Processing Letters 81 (2002) 187–190. Erratum, 84 (2002) 173.
[3] T. Araki, Edge-pancyclicity of recursive circulants, Information Processing Letters 88 (2003) 287–292.
[4] Y. A. Ashir and I. A. Stewart, On embedding cycles in k-ary n-cubes, Parallel Processing Letters 7 (1997) 49–55.
[5] Y. A. Ashir and I. A. Stewart, On embedding cycles in k-ary n-cubes, Parallel Processing Letters 7 (1997) 49–55.
[6] Y. A. Ashir and I. A. Stewart, Fault-tolerant embeddings of Hamiltonian circuits in k-ary n-cubes, SIAM Journal on Discrete Mathematics 15 (2002) 317–
328.
[7] A. S. Asratian, R. H¨aggkvist, and G. V. Sarkisian, A characterization of panconnected graphs satisfying a local Ore-type condition, Journal of Graph Theory 22 (1996) 95–103.
[8] A. S. Asratian and N.K. Khachatrian, Some localization theorems on Hamiltonian circuits, Journal of Combinatorial Theory Series B 49 (1990) 287–294.
[9] J.-C. Bermond and P. Rosenstiehl, Le carr´e du graphe repr´esentatif des arˆetes de tout multigraphe est pancyclique, Pro. Colloque sur la Th´eorie des Graphe 26-27 Avril 1973 Cahiers du C.E.R.O., Bruxelles 15 (1973) 285–286.
[10] J. A. Bondy, Pancyclic graphs I, Journal of Combinatorial Theory Series B 11 (1971) 80–84.
[11] J. A. Bondy, Pancyclic graphs, Proceedings of Second Louisiana Conference on Combinatorics, Graph theory, and Computing (Louisiana State University, Baton Rouge), 1971, 167–172.
[12] J. A. Bondy, Variations on the Hamiltonian theme, Canadian Mathematical Bulletin 15 (1972) 57–62.
[13] J. A. Bondy and V. Chv´atal, A method in graph theory, Discrete Mathematics 15 (1976) 111–136.
[14] J. A. Bondy and A. W. Ingleton, Pancyclic graphs II, Journal of Combinatorial Theory Series B 20 (1976) 41–46.
[15] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, North Holland, New York, 1980.
[16] H.-C. Chan, J.-M. Chang, Y.-L. Wang, and S.-J. Horng, Geodesic-pancyclic graphs, Discrete Applied Mathematics to appear.
[17] J.-M. Chang, J.-S. Yang, Y.-L. Wang, and Y. Cheng, Panconnectivity, fault-tolerant hamiltonicity and Hamiltonian-connectivity in alternating group graphs, Networks 44 (2004) 302–310.
[18] G. Chartrand and S. F. Kapoor, The cube of every connected graph is 1-Hamiltonian, Journal of research of the National Bureau of Standards 73B (1969) 47–48.
[19] G. Chartrand and O. R. Oellermann, Applied and Algorithmic Graph Theory McGraw-Hill, Singapore, 1993.
[20] Y.-C. Chen, C.-H. Tsai, L.-H. Hsu, and Jimmy J.-M. Tan, On some super fault-tolerant Hamiltonian graphs, Applied Mathematics and Computation 148 (2004) 729–741.
[21] S. A. Choudum and V. Sunitha, Augmented cubes, Networks 40 (2002) 71–84.
[22] K. Day and A. Tripathi, Embedding of cycles in arrangement graphs, IEEE Transactions on Computers 42 (1993) 1002–1006.
[23] G. A. Dirac, Some theorems on abstract graphs, Proceedings of the London Mathematical Society 3 (1952) 69–81.
[24] J. Fan, Hamilton-connectivity and cycle-embedding of M¨obius cubes, Information Processing Letters 82 (2002) 113–117.
[25] J. Fan, X. Jia, and X. Lin, Complete path embeddings in crossed cubes, Information Sciences 176 (2006) 3332–3346.
[26] J. Fan, X. Jia, and X. Lin, Optimal embeddings of paths with various lengths in twisted cubes, IEEE Transactions on Parallel and Distributed Systems 18
(2007) 511–521.
[27] J. Fan, X. Lin, and X. Jia, Node-pancyclicity and edge-pancyclicity of crossed cubes, Information Processing Letters 93 (2005) 133–138.
[28] J. Fan, X. Lin, and X. Jia, Optimal path embedding in crossed cubes, IEEE Transactions on Parallel and Distributed Systems 16 (2005) 1190–1200.
[29] J. Fan, X. Lin, and X. Jia, Optimal fault-tolerant embedding of paths in twisted cubes, Journal of Parallel and Distributed Computing 67 (2007) 205–214.
[30] R. J. Faudree and R. H. Schelp, Path connected graphs, Acta Mathematica Academiae Scientiarum Hungaricae 25 (1974) 313–319.
[31] R. J. Faudree and R. H. Schelp, The square of a block is strongly path connected, Journal of Combinatorial Theory Series B 20 (1976) 47–61.
[32] M. R. Garey and D. S. Johnson, Computers and Intractibility: A Guide to the Theory of NP-Completeness. Freeman, New York (1979).
[33] R. J. Gould, Advances on the Hamiltonian problem — a survey, Graphs and Combinatorics 19 (2003) 7–52.
[34] F. Harary and I. C. Ross, The square of a tree, The Bell System Technical Journal 39 (1960) 641–647.
[35] G. R. T. Hendry, Extending cycles in graphs, Discrete Mathematics 85 (1990) 59–72.
[36] A. M. Hobbs, The square of a block is vertex pancyclic, Journal of Combinatorial Theory Series B 20 (1976) 1–4.
[37] S.-Y. Hsieh and N.-W. Chang, Hamiltonian path embedding and pancyclicity on the M¨obius cube with faulty nodes and faulty edges, IEEE Transactions on Computers 55 (2006) 854–863.
[38] S.-Y. Hsieh and C.-H. Chen, Pancyclicity on M¨obius cubes with maximal edge faults, Parallel Computing 30 (2004) 407–421.
[39] S.-Y. Hsieh, G.-H. Chen, and C.-W. Ho, Fault-free Hamiltonian cycles in faulty arrangement graphs, IEEE Transactions on Parallel and Distributed Systems 10 (1999) 223–237.
[40] S.-Y. Hsieh and J.-Y. Shiu, Cycle embedding of augmented cubes, Applied Mathematics and Computation to appear.
[41] H.-C. Hsu, L.-C. Chiang, Jimmy J.-M. Tan, and L.-H. Hsu, Fault hamiltonicity of augmented cubes, Parallel Computing 31 (2005) 131–145.
[42] H.-C. Hsu, P.-L. Lai, and C.-H. Tsai, Geodesic pancyclicity and balanced pancyclicity of augmented cubes, Information Processing Letters 101 (2007) 227–232.
[43] K.-S. Hu, S.-S. Yeoh, C. Chen, and L.-H. Hsu, Node-pancyclicity and edgepancyclicity of hypercube variants, Information Processing Letters 102 (2007) 1–7.
[44] W.-T. Huang, Jimmy J.-M. Tan, C.-N. Hung, and L.-H. Hsu, Fault-tolerant hamiltonicity of twisted cubes, Journal of Parallel and Distributed Computing 62 (2002) 591–604.
[45] J. Jwo, S. Lakshmivarahan, and S. K. Dhall, Embedding of cycles and grids in star graphs, Journal of Circuits, Systems, and Computers 1 (1991) 43–74.
[46] D, K˝onig, Theorie der endlichen und unendlichen Graphen Leipzig (1936). Reprinted by Chelsea, New York (1950).
[47] L. Lesniak, n-distant Hamiltonian graphs, Utilitas Mathematica 9 (1976) 161–175.
[48] T.-K. Li, C.-H. Tsai, Jimmy J.-M. Tan, and L.-H. Hsu, Bipanconnectivity and edge-fault-tolerant bipancyclicity of hypercubes, Information Processing Letters 87 (2003) 107–110.
[49] M.-J. Ma, G. Liu, and X.-F. Pan, Path embedding in faulty hypercubes, Applied Mathematics and Computation to appear.
[50] M.-J. Ma, G. Liu, and J.-M. Xu, Panconnectivity and edge-fault-tolerant pancyclicity of augmented cubes, Parallel Computing 33 (2007) 36–42.
[51] M.-J. Ma and J.-M. Xu, Panconnectivity of locally twisted cubes, Applied Mathematics Letters 19 (2006) 673–677.
[52] B. Monien, H. Sudborough, Embedding one Interconnection Network in Another, Computing Supplementum 7 (1990) 257–282.
[53] J. W. Moon, On a problem of Ore, The Mathematical Gazette 49 (1965) 40–41.
[54] L. Nebesk´y, On the line graph of the square and the square of the line graph of a connected graph, ˇCasopis pro Pˇestovani Matematiky 98 (1973) 285–287.
[55] O. Ore, Note on Hamilton circuits, American Mathematical Monthly 67 (1960) 55.
[56] O. Ore, Arc coverings of graphs, Annali di Matematica Pura ed Applicata 55 (1961) 315–321.
[57] O. Ore, Theory of Graphs American Mathematical Society Colloquium Publications, 38 Providence (1962).
[58] O. Ore, Hamilton connected graphs, Journal de math´ematiques pures et appliqu´ees 42 (1963) 21–27.
[59] J.-H. Park, H.-S. Lim, and H.-C. Kim, Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements, Theoretical Computer Science 377 (2007) 170–180.
[60] B. Randerath, I. Schiermeyer, M. Tewes, and L. Nolkmann, Vertex pancyclic graphs, Discrete Applied Mathematics 120 (2002) 219–237.
[61] R. A. Rowley and B. Rose, Fault-tolerant ring embedding in de Bruijn networks, IEEE Transactions on Computers 42 (1993) 1480–1486.
[62] Y. Saad and M. H. Schultz, Topological properties of hypercubes, IEEE Transactions on Computers 37(7) (1988) 867–872.
[63] M. Sekanina, On an ordering of the set of vertices of a connected graph, Publications of the Faculty of Sciences of the University of Brno 412(7) (1960) 137–142.
[64] C.-H. Tsai, Cycles embedding in hypercubes with node failures, Information Processing Letters 102 (2007) 242–246.
[65] C.-H. Tsai and S.-Y. Jiang, Path bipancyclicity of hypercubes, Information Processing Letters 101 (2007) 93–97.
[66] C.-H. Tsai, Jimmy J.-M. Tan, T. Liang, and L.-H. Hsu, Fault-tolerant hamiltonian laceability of hypercubes, Information Processing Letters 83 (2002) 301–306.
[67] Y.-C. Tseng, S.-H. Chang, and J.-P. Sheu, Fault-free ring embedding in a star graph with both link and node failure, IEEE Transactions on Parallel and Distributed Systems 8 (1997) 1185–1195.
[68] D. Wang, Embedding Hamiltonian cycles into folded hypercubes with faulty links, Journal of Parallel and Distributed Computing 61 (2001) 545–564.
[69] W.-W. Wang, M.-J. Ma, and J.-M. Xu, Fault-tolerant pancyclicity of augmented cubes, Information Processing Letters 103 (2007) 52–56.
[70] J. E. Williamson, Panconnected graphs II, Periodica Mathematica Hungarica 8 (1977) 371–375.
[71] S. A. Wong, Hamilton cycles and paths in butterfly graphs, Networks 26 (1995) 145–150.
[72] J.-M. Xu, Z.-Z. Du, and M. Xu, Edge-fault-tolerant edge-bipancyclicity of hypercubes, Information Processing Letters 96 (2005) 146–150.
[73] J.-M. Xu and M.-J. Ma, Cycles in folded hypercubes, Applied Mathematics Letters 19 (2006) 140–145.
[74] J.-M. Xu, M.-J. Ma, and Z.-Z. Du, Edge-fault-tolerant properties of hypercubes and folded hypercubes, Australasian Journal Combinatorics 35 (2006) 7–16.
[75] J.-M. Xu, M.-J. Ma, and M. L¨u, Paths in M¨obius cubes and crossed cubes, Information Processing Letters 97 (2006) 94–97.
[76] M. Xu and J.-M. Xu, Edge-pancyclicity of M¨obius cubes, Information Processing Letters 96 (2005) 136–140.
[77] M.-C. Yang, T.-K. Li, Jimmy J.-M. Tan, and L.-H. Hsu, Fault-tolerant cycleembedding of crossed cubes, Information Processing Letters 88 (2003) 149–154.
[78] M.-C. Yang, T.-K. Li, Jimmy J.-M. Tan, and L.-H. Hsu, Fault-tolerant pancyclicity of the M¨obius cubes, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E88-A (2005) 346–352.
[79] M.-C. Yang, T.-K. Li, Jimmy J.-M. Tan, and L.-H. Hsu, On embedding cycles into faulty twisted cubes, Information Sciences 176 (2006) 676–690.
[80] M.-C. Yang, Jimmy J.-M. Tan, and L.-H. Hsu, Hamiltonian circuit and linear array embeddings in faulty k-ary n-cubes, Journal of Parallel and Distributed Computing 67 (2007) 362–368.
[81] M.-C. Yang, Jimmy J.-M. Tan, and L.-H. Hsu, Highly fault-tolerant cycle embeddings of hypercubes, Journal of Systems Architecture 53 (2007) 227–232.
[82] X. Yang, G. M. Megson, D. J. Evans, Locally twisted cubes are 4-pancyclic, Applied Mathematics Letters 17 (2004) 919–925.
[83] X. Yang, G. M. Megson, D. J. Evans, Pancyclicity of M¨obius cubes with faulty nodes, Microprocessors and Microsystems 30 (2006) 165–172.