Hamiltonian cycles in I–graphs
Electronic Notes in Discrete Mathematics, 2013 Abstract The I–graphs generalize the family of generalized Petersen graphs. We show that a connected I–graph which is not a generalized Petersen graph is Hamiltonian.
BONVICINI, Simona, Pisanski, Tomaž
openaire +3 more sources
Hamiltonian path and Hamiltonian cycle are solvable in polynomial time in graphs of bounded independence number [PDF]
A Hamiltonian path (a Hamiltonian cycle) in a graph is a path (a cycle, respectively) that traverses all of its vertices. The problems of deciding their existence in an input graph are well-known to be NP-complete, in fact, they belong to the first ...
Jedličková, Nikola, Kratochvíl, Jan
core
Detecting alien limit cycles near a Hamiltonian 2-saddle cycle [PDF]
, 2009 This paper aims at providing an example of a cubic Hamiltonian 2-saddle cycle that after bifurcation can give rise to an alien limit cycle; this is a limit cycle that is not controlled by a zero of the related Abelian integral. To guarantee the existence
Luca, Stijn +4 more
core +1 more source
Energy Conditions for Hamiltonicity of Graphs
Discrete Dynamics in Nature and Society, 2014 Let G be an undirected simple graph of order n. Let A(G) be the adjacency matrix of G, and let μ1(G)≤μ2(G)≤⋯≤μn(G) be its eigenvalues. The energy of G is defined as ℰ(G)=∑i=1n|μi(G)|. Denote by GBPT a bipartite graph.
Guidong Yu +3 more
doaj +1 more source
Numerical evidence for phase transitions of NP-complete problems for instances drawn from Lévy-stable distributions [PDF]
, 2011 Random NP-Complete problems have come under study as an important tool used in the analysis of optimization algorithms and help in our understanding of how to properly address issues of computational intractability.
Connelly, Abram, Abram Connelly
core +1 more source
The Hamiltonian and Hypohamiltonian of Generalized Petersen Graph (GP_(n,9))
Jambura Journal of MathematicsThe study of Hamiltonian and Hypohamiltonian properties in the generalized Petersen graph GP_{n,k} is interesting due to the unique structure and characteristics of these graphs. The method employed in this study involves searching for Hamiltonian cycles
Susilawati Susilawati +3 more
doaj +1 more source
Gauss diagrams as cubic graphs: The choice of the Hamiltonian cycle matters [PDF]
We explore to what extent the properties of a Gauss diagram are affected by the choice of its Hamiltonian cycle. We present an example of a realizable Gauss diagram and an unrealizable Gauss diagram that differ only by a choice of the Hamiltonian cycle ...
Vernitski, Alexei
core +1 more source
Note on Petrie and Hamiltonian cycles in cubic polyhedral graphs [PDF]
, 1994 summary:In this note we show that deciding the existence of a Hamiltonian cycle in a cubic plane graph is equivalent to the problem of the existence of an associated cubic plane multi-3-gonal graph with a Hamiltonian cycle which takes alternately left ...
Ivančo, J., Jendroľ, S., Tkáč, M.
core
On edge-graceful labeling and deficiency for regular graphs
AKCE International Journal of Graphs and Combinatorics, 2018 An edge-graceful labeling of a finite simple graph with vertices and edges is a bijection from the set of edges to the set of integers such that the vertex sums are pairwise distinct modulo , where the vertex sum at a vertex is the sum of labels of all ...
Tao-Ming Wang, Guang-Hui Zhang
doaj +1 more source
On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs
, 1999 It is a simple fact that cubic Hamiltonian graphs have at least two Hamiltonian cycles. Finding such a cycle is NP-hard in general, and no polynomialtime algorithm is known for the problem of finding a second Hamiltonian cycle when one such cycle is ...
Miklos Santha +2 more
core