Results 1 to 10 of about 322 (111)
Graphs which have pancyclic complements [PDF]
International Journal of Mathematics and Mathematical Sciences, 1978 Let p and q denote the number of vertices and edges of a graph G, respectively. Let Δ(G) denote the maximum degree of G, and G¯ the complement of G. A graph G of order p is said to be pancyclic if G contains a cycle of each length n, 3≤n≤p.
H. Joseph Straight
doaj +3 more sources
Spectral Sufficient Conditions on Pancyclic Graphs [PDF]
Complexity, 2021 A pancyclic graph of order n is a graph with cycles of all possible lengths from 3 to n. In fact, it is NP-complete that deciding whether a graph is pancyclic.
Guidong Yu +3 more
doaj +4 more sources
Hamilton-Connected Mycielski Graphs∗
Discrete Dynamics in Nature and Society, 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>VG ...
Yuanyuan Shen +2 more
doaj +2 more sources
New Sufficient Conditions for Hamiltonian Paths [PDF]
The Scientific World Journal, Volume 2014, Issue 1, 2014., 2014 A Hamiltonian path in a graph is a path involving all the vertices of the graph. In this paper, we revisit the famous Hamiltonian path problem and present new sufficient conditions for the existence of a Hamiltonian path in a graph.
M. Sohel Rahman +3 more
wiley +2 more sources
Journal of Combinatorial Theory, Series B, 1999 AbstractA graph is called weakly pancyclic if it contains cycles of all lengths between its girth and circumference. A substantial result of Häggkvist, Faudree, and Schelp (1981) states that a Hamiltonian non-bipartite graph of order n and size at least ⌊(n−1)2/4⌋+2 contains cycles of every length l, 3⩽l⩽n.
Béla Bollobás, Andrew Thomason
openalex +3 more sources
Eulerian and pancyclic zero-divisor graphs of ordered sets [PDF]
AKCE International Journal of Graphs and CombinatoricsIn this paper, we determine when the zero-divisor graph of a special class of a finite pseudocomplemented poset is Eulerian. Also, we deal with Hamiltonian, vertex pancyclic, and edge pancyclic properties of the complement of a zero-divisor graph of ...
Nilesh Khandekar, Vinayak Joshi
doaj +2 more sources
Rainbow Pancyclicity in Graph Systems [PDF]
The Electronic Journal of Combinatorics, 2021 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. a cycle with edge set $\{e_1,\ldots,e_n\}$ such that $e_i\in E(G_i)$ for $1\leq i \leq n$.
Yangyang Cheng, Guanghui Wang, Yi Zhao
openalex +3 more sources
Pancyclicity of claw-free hamiltonian graphs [PDF]
Discrete Mathematics, 1999 AbstractA graph G on n vertices is called subpancyclic if it contains cycles of every length k with 3 ⩽ k ⩽ c(G), where c(G) denotes the length of a longest cycle in G; if moreover c(G) = n, then G is called pancyclic. By a result of Flandrin et al. a claw-free graph (on at least 35 vertices) with minimum degree at least 13(n − 2) is pancyclic.
H. Trommel
openalex +5 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 +3 more sources
A theorem on pancyclic-oriented graphs
Journal of Combinatorial Theory, Series B, 1977 AbstractWe prove the theorem: Let G = (X, U) be an oriented strongly connected graph with n(≥2) vertices. For each two nonadjacent vertices x, y(x ≠ y) we have d(x) + d(y) ≥ 2n + 1. Then G is pancyclic or G is a tournament.
Maria Overbeck-Larisch
openalex +3 more sources