Results 1 to 10 of about 635 (107)
Pancyclicity when each Cycle Must Pass Exactly k Hamilton Cycle Chords
Discussiones Mathematicae Graph Theory, 2015 It is known that Θ(log n) chords must be added to an n-cycle to produce a pancyclic graph; for vertex pancyclicity, where every vertex belongs to a cycle of every length, Θ(n) chords are required.
Affif Chaouche Fatima +2 more
doaj +2 more sources
Rainbow vertex pair-pancyclicity of strongly edge-colored graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2023 An edge-colored graph is \emph{rainbow }if no two edges of the graph have the same color. An edge-colored graph $G^c$ is called \emph{properly colored} if every two adjacent edges of $G^c$ receive distinct colors in $G^c$.
Peixue Zhao, Fei Huang
doaj +1 more source
Fan's condition on induced subgraphs for circumference and pancyclicity [PDF]
Opuscula Mathematica, 2017 Let \(\mathcal{H}\) be a family of simple graphs and \(k\) be a positive integer. We say that a graph \(G\) of order \(n\geq k\) satisfies Fan's condition with respect to \(\mathcal{H}\) with constant \(k\), if for every induced subgraph \(H\) of \(G ...
Wojciech Wideł
doaj +1 more source
Edge condition for hamiltonicity in balanced tripartite graphs [PDF]
Opuscula Mathematica, 2009 A well-known theorem of Entringer and Schmeichel asserts that a balanced bipartite graph of order \(2n\) obtained from the complete balanced bipartite \(K_{n,n}\) by removing at most \(n-2\) edges, is bipancyclic.
Janusz Adamus
doaj +1 more source
Heavy subgraphs, stability and hamiltonicity [PDF]
, 2016 Let $G$ be a graph. Adopting the terminology of Broersma et al. and \v{C}ada, respectively, we say that $G$ is 2-heavy if every induced claw ($K_{1,3}$) of $G$ contains two end-vertices each one has degree at least $|V(G)|/2$; and $G$ is o-heavy if every
Li, Binlong, Ning, Bo
core +4 more sources
On regular subgraphs of augmented cubes
AKCE International Journal of Graphs and Combinatorics, 2020 The n-dimensional augmented cube AQn is a variation of the hypercube It is a -regular and -connected graph on vertices. One of the fundamental properties of AQn is that it is pancyclic, that is, it contains a cycle of every length from 3 to In this paper,
Amruta Shinde, Y. M. Borse
doaj +1 more source
A result on Hamiltonian line graphs involving restrictions on induced subgraphs [PDF]
, 1988 It is shown that the existence of a Hamilton cycle in the line graph of a graph G can be ensured by imposing certain restrictions on certain induced subgraphs of G.
Benhocine +11 more
core +7 more sources
Tight Hamilton Cycles in Random Uniform Hypergraphs [PDF]
, 2010 In this paper we show that $e/n$ is the sharp threshold for the existence of tight Hamilton cycles in random $k$-uniform hypergraphs, for all $k\ge 4$. When $k=3$ we show that $1/n$ is an asymptotic threshold.
Dudek, Andrzej, Frieze, Alan
core +11 more sources
Generating random graphs in biased Maker-Breaker games [PDF]
, 2015 We present a general approach connecting biased Maker-Breaker games and problems about local resilience in random graphs. We utilize this approach to prove new results and also to derive some known results about biased Maker-Breaker games. In particular,
Ferber, Asaf +2 more
core +2 more sources
A Note on Cycles in Locally Hamiltonian and Locally Hamilton-Connected Graphs
Discussiones Mathematicae Graph Theory, 2020 Let 𝒫 be a property of a graph. A graph G is said to be locally 𝒫, if the subgraph induced by the open neighbourhood of every vertex in G has property 𝒫. Ryjáček conjectures that every connected, locally connected graph is weakly pancyclic.
Tang Long, Vumar Elkin
doaj +1 more source