Results 31 to 40 of about 406 (81)
A conjecture on the prevalence of cubic bridge graphs [PDF]
, 2010 Almost all d-regular graphs are Hamiltonian, for d ≥ 3. In this note we conjecture that in a similar, yet somewhat different, sense almost all cubic non-Hamiltonian graphs are bridge graphs, and present supporting empirical results for this prevalence of
Filar, Jerzy A +2 more
core +1 more source
A Fan-Type Heavy Pair Of Subgraphs For Pancyclicity Of 2-Connected Graphs
Discussiones Mathematicae Graph Theory, 2016 Let G be a graph on n vertices and let H be a given graph. We say that G is pancyclic, if it contains cycles of all lengths from 3 up to n, and that it is H-f1-heavy, if for every induced subgraph K of G isomorphic to H and every two vertices u, v ∈ V (K)
Wideł Wojciech
doaj +1 more source
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
Notes on a conjecture of Manoussakis concerning Hamilton cycles in digraphs
, 2014 In 1992, Manoussakis conjectured that a strongly 2-connected digraph $D$ on $n$ vertices is hamiltonian if for every two distinct pairs of independent vertices $x,y$ and $w,z$ we have $d(x)+d(y)+d(w)+d(z)\geq 4n-3$.
Ning, Bo
core +1 more source
Hamiltonian Normal Cayley Graphs
Discussiones Mathematicae Graph Theory, 2019 A variant of the Lovász Conjecture on hamiltonian paths states that every finite connected Cayley graph contains a hamiltonian cycle. Given a finite group G and a connection set S, the Cayley graph Cay(G, S) will be called normal if for every g ∈ G we ...
Montellano-Ballesteros Juan José +1 more
doaj +1 more source
2-Spanning Cyclability Problems of Some Generalized Petersen Graphs
Discussiones Mathematicae Graph Theory, 2020 A graph G is called r-spanning cyclable if for every r distinct vertices v1, v2, . . . , vr of G, there exists r cycles C1, C2, . . . , Cr in G such that vi is on Ci for every i, and every vertex of G is on exactly one cycle Ci.
Yang Meng-Chien +3 more
doaj +1 more source
Alternating Hamiltonian cycles in $2$-edge-colored multigraphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2019 A path (cycle) in a $2$-edge-colored multigraph is alternating if no two consecutive edges have the same color. The problem of determining the existence of alternating Hamiltonian paths and cycles in $2$-edge-colored multigraphs is an $\mathcal{NP ...
Alejandro Contreras-Balbuena +2 more
doaj +1 more source
Edge-Connectivity and Edges of Even Factors of Graphs
Discussiones Mathematicae Graph Theory, 2019 An even factor of a graph is a spanning subgraph in which each vertex has a positive even degree. Jackson and Yoshimoto showed that if G is a 3-edge-connected graph with |G| ≥ 5 and v is a vertex with degree 3, then G has an even factor F containing two ...
Haghparast Nastaran, Kiani Dariush
doaj +1 more source
Matchings of quadratic size extend to long cycles in hypercubes [PDF]
Discrete Mathematics & Theoretical Computer Science, 2016 Ruskey and Savage in 1993 asked whether every matching in a hypercube can be extended to a Hamiltonian cycle. A positive answer is known for perfect matchings, but the general case has been resolved only for matchings of linear size.
Tomáš Dvořák
doaj +1 more source
Spectral radius and traceability of connected claw-free graphs
, 2015 Let $G$ be a connected claw-free graph on $n$ vertices and $\overline{G}$ be its complement graph. Let $\mu(G)$ be the spectral radius of $G$. Denote by $N_{n-3,3}$ the graph consisting of $K_{n-3}$ and three disjoint pendent edges. In this note we prove
Li, Binlong, Ning, Bo
core +1 more source