Search Results

1 - 10 of 20 items :

  • "Hamiltonian cycle" x
Clear All
Matchings Extend to Hamiltonian Cycles in 5-Cube

R eferences [1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North-Holland, New York-Amsterdam-Oxford, 1982). [2] R. Caha and V. Koubek, Spanning multi-paths in hypercubes , Discrete Math. 307 (2007) 2053–2066. doi:10.1016/j.disc.2005.12.050 [3] D. Dimitrov, T. Dvořák, P. Gregor and R. Škrekovski, Gray codes avoiding matchings , Discrete Math. Theoret. Comput. Sci. 11 (2009) 123–148. [4] T. Dvořák, Hamiltonian cycles with prescribed edges in hypercubes , SIAM J. Discrete Math. 19 (2005) 135–144. doi:10.1137/S

Open access
Arc-Disjoint Hamiltonian Cycles in Round Decomposable Locally Semicomplete Digraphs

.2307/2315334 [8] J. Huang, On the structure of local tournaments , J. Combin. Theory Ser. B 63 (1995) 200–221. doi:10.1006/jctb.1995.1016 [9] S. Li, W. Meng, Y. Guo and G. Xu, A local tournament contains a vertex whose out-arc are pseudo-girth-pancyclic , J. Graph Theory 62 (2009) 346–361. doi:10.1002/jgt.20404 [10] D. Meierling, Local tournaments with the minimum number of Hamiltonian cycles or cycles of length three , Discrete Math. 310 (2010) 1940–1948. doi:10.1016/j.disc.2010.03.003 [11] C. Thomassen, Edge-disjoint Hamiltonian paths and cycles in

Open access
Hamiltonian Normal Cayley Graphs

. 104 (2012) 1171–1197. doi:10.1112/plms/pdr042 [8] H.H. Glover, K. Kutnar and D. Marušič, Hamiltonian cycles in cubic Cayley graphs: the < 2, 4 k, 3 > case , J. Algebraic Combin. 30 (2009) 447–475. doi:10.1007/s10801-009-0172-5 [9] H.H. Glover and D. Marušič, Hamiltonicity of cubic Cayley graph , J. Eur. Math. Soc. 9 (2007) 775–787. [10] H.H. Glover and T.Y. Yang, A Hamilton cycle in the Cayley graph of the (2, p, 3) - presentation of PSL 2( p ), Discrete Math. 160 (1996) 149–163. doi:10.1016/0012-365X(95)00155-P [11] K

Open access
On Uniquely Hamiltonian Claw-Free and Triangle-Free Graphs

cubic graphs, J. Com- bin. Theory (B) 29 (1980) 303-309. doi:10.1016/0095-8956(80)90087-8 [5] H. Fleischner, Uniquely Hamiltonian graphs of minimum degree 4, J. Graph Theory 75 (2014) 167-177. doi:10.1002/jgt.2172 [6] P. Haxell, B. Seamone and J. Verstraete, Independent dominating sets and Hamiltonian cycles, J. Graph Theory 54 (2007) 233-244. doi:10.1002/jgt.20205 [7] J. Petersen, Die theorie der regul¨aren graphs, Acta Math. 15 (1891) 193-220. doi:10.1007/BF02392606 [8] J. Sheehan, The multiplicity of

Open access
A Limit Conjecture on the Number of Hamiltonian Cycles on Thin Triangular Grid Cylinder Graphs

R eferences [1] O. Bodroža-Pantić, B. Pantić, I. Pantić and M. Bodroža-Solarov, Enumeration of Hamiltonian cycles in some grid graphs , MATCH Commun. Math. Comput. Chem. 70 (2013) 181–204. [2] O. Bodroža-Pantić, H. Kwong and M. Pantić, Some new characterizations of Hamiltonian cycles in triangular grid graphs , Discrete Appl. Math. 201 (2016) 1–13. doi:10.1016/j.dam.2015.07.028 [3] O. Bodroža-Pantić, H. Kwong and M. Pantić, A conjecture on the number of Hamiltonian cycles on thin grid cylinder graphs , Discrete Math. Theoret. Comput. Sci

Open access
On the Hamiltonian Number of a Plane Graph

Abstract

The Hamiltonian number of a connected graph is the minimum of the lengths of the closed spanning walks in the graph. In 1968, Grinberg published a necessary condition for the existence of a Hamiltonian cycle in a plane graph, formulated in terms of the degrees of its faces. We show how Grinberg’s theorem can be adapted to provide a lower bound on the Hamiltonian number of a plane graph.

Open access
On Vertices Enforcing a Hamiltonian Cycle

Abstract

A nonempty vertex set X ⊆ V (G) of a hamiltonian graph G is called an H-force set of G if every X-cycle of G (i.e. a cycle of G containing all vertices of X) is hamiltonian. The H-force number h(G) of a graph G is defined to be the smallest cardinality of an H-force set of G. In the paper the study of this parameter is introduced and its value or a lower bound for outerplanar graphs, planar graphs, k-connected graphs and prisms over graphs is determined.

Open access
Families of triples with high minimum degree are hamiltonian

References [1] R. Aharoni, A. Georgakopoulos and P. Sprüssel, Perfect matchings in r-partite r- graphs, European J. Combin. 30 (2009) 39-42. doi:10.1016/j.ejc.2008.02.011 [2] E. Buss, H. H`an and M. Schacht, Minimum vertex degree conditions for loose Hamil- ton cycles in 3-uniform hypergraphs, J. Combin. Theory (B), to appear. [3] R. Glebov, Y. Person andW.Weps, On extremal hypergraphs for hamiltonian cycles, European J. Combin. 33 (2012) 544-555 (An extended abstract has appeared in the Proceedings of EuroComb

Open access
Torus–Connected Cycles: A Simple and Scalable Topology for Interconnection Networks

.-K., Chuang, H.-C., Kao, S.-S. and Tan, J.J. (2010). Mutually independent Hamiltonian cycles in dual-cubes, Journal of Supercomputing 54 (2): 239–251. Singh, A., Dally, W., Gupta, A. and Towles, B. (2003). Goal: A load-balanced adaptive routing algorithm for torus networks, SIGARCH Computer Architecture News 31 (2): 194–205. TOP500 (2013). China’s Tianhe-2 supercomputer takes no. 1 ranking on 41st TOP500 list, http://top500.org/blog/lists/2013/06/press-release/ , (last accessed in August 2013). Wu, J. and Sun, X.-H. (1994). Optimal cube

Open access
Symmetric Hamilton Cycle Decompositions of Complete Multigraphs

.20257 [5] M. Buratti, S. Capparelli and A. Del Fra, Cyclic Hamiltonian cycle systems of the -fold complete and cocktail party graph, European J. Combin. 31 (2010) 1484-1496. doi:10.1016/j.ejc.2010.01.004 [6] M. Buratti and A. Del Fra, Cyclic Hamiltonian cycle systems of the complete graph, Discrete Math. 279 (2004) 107-119. doi:10.1016/S0012-365X(03)00267-X [7] M. Buratti and F. Merola, Dihedral Hamiltonian cycle system of the cocktail party graph, J. Combin. Des. 21 (2013) 1-23. doi:10.1002/jcd.21311 [8

Open access