Results 11 to 20 of about 782 (111)

The Completion Numbers of Hamiltonicity and Pancyclicity in Random Graphs [PDF]

Random Structures &Algorithms, Volume 66, Issue 2, March 2025., 2023
Let μ(G)$$ \mu (G) $$ denote the minimum number of edges whose addition to G$$ G $$ results in a Hamiltonian graph, and let μ^(G)$$ \hat{\mu}(G) $$ denote the minimum number of edges whose addition to G$$ G $$ results in a pancyclic graph.
Yahav Alon, Michael Anastos
semanticscholar   +2 more sources

Chvátal-Erdős condition for pancyclicity [PDF]

Journal of the Association for Mathematical Research, 2023
An $n$-vertex graph is \emph{Hamiltonian} if it contains a cycle that covers all of its vertices and it is \emph{pancyclic} if it contains cycles of all lengths from $3$ up to $n$.
N. Dragani'c, David Munh'a Correia, B. Sudakov   +2 more
semanticscholar   +4 more sources

Pancyclicity of Hamiltonian graphs [PDF]

Journal of the European Mathematical Society, 2022
An n -vertex graph is Hamiltonian if it contains a cycle that covers all of its vertices, and it is pancyclic if it contains cycles of all lengths from 3 up to n .
N. Dragani'c, David Munh'a Correia, B. Sudakov   +2 more
semanticscholar   +3 more sources

Two-Disjoint-Cycle-Cover Pancyclicity of Dragonfly Networks

Mathematics
Interconnection networks (often modeled as graphs) are critical for high-performance computing systems, as they have significant impact on performance metrics like latency and bandwidth.
Zengxian Tian, Guanlin He
doaj   +2 more sources

Rainbow Pancyclicity in Graph Systems [PDF]

The Electronic Journal of Combinatorics, 2019
 Let $G_1,\ldots,G_n$ be graphs on the same vertex set of size $n$, each graph with minimum degree $\delta(G_i)\ge n/2$. A recent conjecture of Aharoni asserts that there exists a rainbow Hamiltonian cycle i.e.
Yangyang Cheng, G. Wang, Zhao Yi
semanticscholar   +5 more sources

Pancyclicity and vertex pancyclicity for some products of graphs

, 2023
Artchariya Muaengwaeng
semanticscholar   +2 more sources

A generalization of Bondy's pancyclicity theorem [PDF]

Combinatorics, probability & computing, 2023
The \emph{bipartite independence number} of a graph $G$, denoted as $\tilde\alpha(G)$, is the minimal number $k$ such that there exist positive integers $a$ and $b$ with $a+b=k+1$ with the property that for any two sets $A,B\subseteq V(G)$ with $A=a$ and
N. Dragani'c, David Munh'a Correia, B. Sudakov   +2 more
semanticscholar   +1 more source

Hamiltonicity of graphs perturbed by a random regular graph

Random Structures &Algorithms, Volume 62, Issue 4, Page 857-886, July 2023., 2023
Abstract We study Hamiltonicity and pancyclicity in the graph obtained as the union of a deterministic n$$ n $$‐vertex graph H$$ H $$ with δ(H)≥αn$$ \delta (H)\ge \alpha n $$ and a random d$$ d $$‐regular graph G$$ G $$, for d∈{1,2}$$ d\in \left\{1,2\right\} $$. When G$$ G $$ is a random 2‐regular graph, we prove that a.a.s.
Alberto Espuny Díaz, António Girão
wiley   +1 more source

Hamiltonicity of graphs perturbed by a random geometric graph

Journal of Graph Theory, Volume 103, Issue 1, Page 12-22, May 2023., 2023
Abstract We study Hamiltonicity in graphs obtained as the union of a deterministic n $n$‐vertex graph H $H$ with linear degrees and a d $d$‐dimensional random geometric graph G d ( n , r ) ${G}^{d}(n,r)$, for any d ≥ 1 $d\ge 1$. We obtain an asymptotically optimal bound on the minimum r $r$ for which a.a.s.
Alberto Espuny Díaz
wiley   +1 more source

Hamilton‐Connected Mycielski Graphs∗

Discrete Dynamics in Nature and Society, Volume 2021, Issue 1, 2021., 2021
Jarnicki, Myrvold, Saltzman, and Wagon conjectured that if G is Hamilton‐connected and not K2, then its Mycielski graph μ(G) is Hamilton‐connected. In this paper, we confirm that the conjecture is true for three families of graphs: the graphs G with δ(G) > |V(G)|/2, generalized Petersen graphs GP(n, 2) and GP(n, 3), and the cubes G3.
Yuanyuan Shen, Xinhui An, Baoyindureng Wu, Zuonong Zhu   +3 more
wiley   +1 more source