Results 11 to 20 of about 384 (59)
Sparse Kneser graphs are Hamiltonian
Journal of the London Mathematical Society, Volume 103, Issue 4, Page 1253-1275, June 2021., 2021 Abstract For integers k⩾1 and n⩾2k+1, the Kneser graph K(n,k) is the graph whose vertices are the k‐element subsets of {1,…,n} and whose edges connect pairs of subsets that are disjoint. The Kneser graphs of the form K(2k+1,k) are also known as the odd graphs.
Torsten Mütze +2 more
wiley +1 more source
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
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
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
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
Vertices with the Second Neighborhood Property in Eulerian Digraphs
, 2014 The Second Neighborhood Conjecture states that every simple digraph has a vertex whose second out-neighborhood is at least as large as its first out-neighborhood, i.e. a vertex with the Second Neighborhood Property.
Dong-Lan Luo (608306) +8 more
core +4 more sources
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