Results 11 to 20 of about 413 (64)
Decomposing tournaments into paths
Proceedings of the London Mathematical Society, Volume 121, Issue 2, Page 426-461, August 2020., 2020 Abstract We consider a generalisation of Kelly's conjecture which is due to Alspach, Mason, and Pullman from 1976. Kelly's conjecture states that every regular tournament has an edge decomposition into Hamilton cycles, and this was proved by Kühn and Osthus for large tournaments. The conjecture of Alspach, Mason, and Pullman asks for the minimum number
Allan Lo +3 more
wiley +1 more source
Dissecting a square into congruent polygons [PDF]
Discrete Mathematics & Theoretical Computer Science, 2020 We study the dissection of a square into congruent convex polygons. Yuan \emph{et al.} [Dissecting the square into five congruent parts, Discrete Math. \textbf{339} (2016) 288-298] asked whether, if the number of tiles is a prime number $\geq 3$, it is ...
Hui Rao, Lei Ren, Yang Wang
doaj +1 more source
Loose Hamiltonian cycles forced by large $(k-2)$-degree - sharp version [PDF]
, 2018 We prove for all $k\geq 4$ and $1\leq ...
Bastos, Josefran de Oliveira +4 more
core +3 more sources
Hamiltonian paths on Platonic graphs
International Journal of Mathematics and Mathematical Sciences, Volume 2004, Issue 30, Page 1613-1616, 2004., 2004 We develop a combinatorial method to show that the dodecahedron graph has, up to rotation and reflection, a unique Hamiltonian cycle. Platonic graphs with this property are called topologically uniquely Hamiltonian. The same method is used to demonstrate topologically distinct Hamiltonian cycles on the icosahedron graph and to show that a regular graph
Brian Hopkins
wiley +1 more source
Old and new generalizations of line graphs
International Journal of Mathematics and Mathematical Sciences, Volume 2004, Issue 29, Page 1509-1521, 2004., 2004 Line graphs have been studied for over seventy years. In 1932, H. Whitney showed that for connected graphs, edge‐isomorphism implies isomorphism except for K3 and K1,3. The line graph transformation is one of the most widely studied of all graph transformations.
Jay Bagga
wiley +1 more source
Longest cycles in certain bipartite graphs
International Journal of Mathematics and Mathematical Sciences, Volume 21, Issue 1, Page 103-106, 1998., 1995 Let G be a connected bipartite graph with bipartition (X, Y) such that |X| ≥ |Y|(≥2), n = |X| and m = |Y|. Suppose, for all vertices x ∈ X and y ∈ Y, dist(x, y) = 3 implies d(x) + d(y) ≥ n + 1. Then G contains a cycle of length 2m. In particular, if m = n, then G is hamiltomian.
Pak-Ken Wong
wiley +1 more source
Hamiltonicities of Double Domination Critical and Stable Claw-Free Graphs
Discussiones Mathematicae Graph Theory, 2019 A graph G with the double domination number γ×2(G) = k is said to be k- γ×2-critical if γ×2 (G + uv) < k for any uv ∉ E(G). On the other hand, a graph G with γ×2 (G) = k is said to be k-γ×2+$k - \gamma _{ \times 2}^ + $-stable if γ×2 (G + uv) = k for any
Kaemawichanurat Pawaton
doaj +1 more source
Uniquely hamiltonian graphs for many sets of degrees [PDF]
Discrete Mathematics & Theoretical Computer ScienceWe give constructive proofs for the existence of uniquely hamiltonian graphs for various sets of degrees. We give constructions for all sets with minimum 2 (a trivial case added for completeness), all sets with minimum 3 that contain an even number (for ...
Gunnar Brinkmann, Matthias De Pauw
doaj +1 more source
Lower Bound on the Number of Hamiltonian Cycles of Generalized Petersen Graphs
Discussiones Mathematicae Graph Theory, 2020 In this paper, we investigate the number of Hamiltonian cycles of a generalized Petersen graph P (N, k) and prove that Ψ(P(N,3))⩾N⋅αN,\Psi ( {P ( {N,3} )} ) \ge N \cdot {\alpha _N}, where Ψ(P(N, 3)) is the number of Hamiltonian cycles of P(N, 3) and αN ...
Lu Weihua, Yang Chao, Ren Han
doaj +1 more source
Hamiltonian‐connected graphs and their strong closures
International Journal of Mathematics and Mathematical Sciences, Volume 20, Issue 4, Page 745-747, 1997., 1993 Let G be a simple graph of order at least three. We show that G is Hamiltonian‐connected if and only if its strong closure is Hamiltonian‐connected. We also give an efficient algorithm to compute the strong closure of G.
Pak-Ken Wong
wiley +1 more source