A sufficient condition for a graph to contain three disjoint 1-factors

Ore derived a sufficient condition for a graph to contain a Hamiltonian cycle. We obtain a sufficient condition, similar to Ore's condition, for a graph to contain a Hamiltonian cycle and a 1-factor which are edge disjoint.     

The generating graph of some monolithic groups

For a finite group G let Γ(G) denote the graph defined on the non-identity elements of G in such a way that two distinct vertices are connected by an edge if and only if they generate G. We look for conditions on the positive integer m that ensure that Γ(G) contains a Hamiltonian cycle when G=S?Cm is the wreath product of a finite simple group S and a cyclic group of order m.     

On Hamilton cycles in certain planar graphs

Let G be a 2-connected plane graph with outer cycle X_G such that for every minimal vertex cut S of G with |S| ≤ 3, every component of G\S contains a vertex of X_G. A sufficient condition for G to be Hamiltonian is presented. This theorem generalizes both Tutte's theorem that every 4-connected planar graph is Hamiltonian, as well as a recent theorem of Dillencourt about NST-triangulations. A linear algorithm to find a Hamilton cycle can be extracted from the proof. One corollary is that a 4-connected planar graph with the vertices of a triangle deleted is Hamiltonian. © 1996 John Wiley & Sons, Inc.     

On the number of Hamiltonian cycles in triangulations

It is proved that if a planar triangulation different from K₃ and K₄ contains a Hamiltonian cycle, then it contains at least four of them. Together with the result of Hakimi, Schmeichel, and Thomassen [2], this yields that, for n ? 12, the minimum number of Hamiltonian cycles in a Hamiltonian planar triangulation on n vertices is four. We also show that this theorem holds for triangulations of arbitrary surfaces and for 3-connected triangulated graphs.     

Orientations of Hamiltonian cycles in bipartite digraphs

The main result of the paper is the following Theorem. Let D=(X,Y,A) be a bipartite, balanced digraph of order 2n and size at least 2n²–2n+3. Then D contains an almost symmetric Hamiltonian cycle (i.e. a Hamiltonian cycle in which at least 2n–1 arcs are symmetric edges), unless D has a vertex which is not incident to any symmetric edge of D.This theorem implies a number of results on cycles in bipartite, balanced digraphs, including some recent results of N. Chakroun, M. Manoussakis and Y. Manoussakis.     

On a new edge function on complete weighted graphs and its application for locating Hamiltonian cycles of small weight

In this paper, we define a new combinatorial function on the edges of complete weighted graphs. This function assigns to each edge of the graph the sum of the weights of all Hamiltonian cycles that contain the edge. Since this function involves the factorial function, whose exact calculation is intractable due to its superexponential asymptotic rate of increase, we also introduce a normalized version of the function that is efficiently computable. From this version, we derive an upper bound to the weight of the minimum weight Hamiltonian cycle of the graph based on the weights of the graph edges. Then we investigate the possible algorithmic applications of this normalized function using the Nearest Neighbor Heuristic and a smallest edge first heuristic. As evidence for its applicability, we show that the use of this function as a criterion for the selection of the next edge, improves the performance of both heuristics for approximating the minimum weight Hamiltonian cycles in Euclidean plane graphs. Moreover, our experimental results show that the use of the function is more suitable with the structure of the smallest edge first heuristic since it provides a solution closer to the best known solution of known hard TSP instances but in \(O(n^3)\) time.     

Induced subgraphs with large degrees at end-vertices for hamiltonicity of claw-free graphs

A graph is called claw-free if it contains no induced subgraph isomorphic to K1,3. Matthews and Sumner proved that a 2-connected claw-free graph G is Hamiltonian if every vertex of it has degree at least (|V(G)|-2)/3. At the workshop C&C (Novy Smokovec, 1993), Broersma conjectured the degree condition of this result can be restricted only to end-vertices of induced copies of N (the graph obtained from a triangle by adding three disjoint pendant edges). Fujisawa and Yamashita showed that the degree condition of Matthews and Sumner can be restricted only to end-vertices of induced copies of Z₁ (the graph obtained from a triangle by adding one pendant edge). Our main result in this paper is a characterization of all graphs H such that a 2-connected claw-free graph G is Hamiltonian if each end-vertex of every induced copy of H in G has degree at least |V(G)|/3+1. This gives an affirmative solution of the conjecture of Broersma up to an additive constant.     

A Degree Constraint for Uniquely Hamiltonian Graphs

A graph, G, is called uniquely Hamiltonian if it contains exactly one Hamilton cycle. We show that if G=(V, E) is uniquely Hamiltonian then Where #(G)=1 if G has even number of vertices and 2 if G has odd number of vertices. It follows that every n-vertex uniquely Hamiltonian graph contains a vertex whose degree is at most c log₂n+2 where c=(log₂3−1)⁻¹≈1.71 thereby improving a bound given by Bondy and Jackson [3].     

Generalized fibonacci cubes are mostly hamiltonian

The Hamiltonian problem is to determine whether a graph contains a spanning (Hamiltonian) path or cycle. Here we study the Hamiltonian problem for the generalized Fibonacci cubes, which are a new family of graphs that have applications in interconnection topologies [J. Liuand W.-J. Hsu, ?Distributed Algorithms for Shortest-Path, Deadlock-Free Routing and Broadcasting in a Class of Interconnection Topologies,”? International Parallel Processing Symposium (1992)]. We show that each member of this family contains a Hamiltonian path. Furthermore, we also characterize the members of this family that contain a Hamiltonian cycle.     

Resonant periodic motions of Hamiltonian systems with one degree of freedom when the Hamiltonian is degenerate

The motions of a non-autonomous Hamiltonian system with one degree of freedom which is periodic in time and where the Hamiltonian contains a small parameter is considered. The origin of coordinates of the phase space is the equilibrium position of the unperturbed or complete system, which is stable in the linear approximation. It is assumed that there is degeneracy in the unperturbed Hamiltonian when account is taken of terms no higher than the fourth degree (the frequency of the small linear oscillations depends on the amplitude) and, in this case, one of the resonances of up to the fourth order inclusive is realized in the system. Model Hamiltonians are constructed for each case of resonance and a qualitative investigation of the motions of the model system is carried out. Using Poincaré's theory of periodic motions and KAM-theory, a rigorous solution is given of the problem of the existence, bifurcations and stability of the periodic motions of the initial system, which are analytic with respect to fractional powers of the small parameter. The resonant periodic motions (in the case of the degeneracy being considered) of a spherical pendulum with an oscillating suspension point are investigated as an application.     

More proofs of menger's theorem

Four ways of proving Menger's Theorem by induction are described. Two of them involve showing that the theorem holds for a finite undirected graph G if it holds for the graphs obtained from G by deleting and contracting the same edge. The other two prove the directed version of Menger's Theorem to be true for a finite digraph D if it is true for a digraph obtained by deleting an edge from D.     

WELFARE MEASUREMENT AND COST-BENEFIT ANALYSIS IN NASH AND STACKELBERG DIFFERENTIAL FISH GAMES

ABSTRACT. This paper develops welfare measures and cost-benefit rules in Nash and Stackelberg differential fish games. The model consists of two fisheries competing on a common fishing ground, but the results are valid in more general settings. Under steady state conditions, the present value of the fisheries' future profit is directly proportional to the current profit plus the value of the net investments in the fish population (the Hamiltonian). Outside the steady state, the rule must, under a Nash game, be modified by adding the present value of the marginal harm done to the fishery by the competitor's future catches to the Hamiltonian. Under a Stackelberg game the present value of the leader's future profit remains proportional to the value of his Hamiltonian.     

On the Facial Thue Choice Index via Entropy Compression

A sequence is nonrepetitive if it contains no identical consecutive subsequences. An edge coloring of a path is nonrepetitive if the sequence of colors of its consecutive edges is nonrepetitive. By the celebrated construction of Thue, it is possible to generate nonrepetitive edge colorings for arbitrarily long paths using only three colors. A recent generalization of this concept implies that we may obtain such colorings even if we are forced to choose edge colors from any sequence of lists of size 4 (while sufficiency of lists of size 3 remains an open problem). As an extension of these basic ideas, Havet, Jendrol', Soták, and ?krabul'áková proved that for each plane graph, eight colors are sufficient to provide an edge coloring so that every facial path is nonrepetitively colored. In this article, we prove that the same is possible from lists, provided that these have size at least 12. We thus improve the previous bound of 291 (proved by means of the Lovász Local Lemma). Our approach is based on the Moser–Tardos entropy‐compression method and its recent extensions by Grytczuk, Kozik, and Micek, and by Dujmovi?, Joret, Kozik, and Wood.     

Matching theory and Barnette's conjecture

Barnette's Conjecture claims that all cubic, 3-connected, planar, bipartite graphs are Hamiltonian. We give a translation of this conjecture into the matching-theoretic setting. This allows us to relax the requirement of planarity to give the equivalent conjecture that all cubic, 3-connected, Pfaffian, bipartite graphs are Hamiltonian.A graph, other than the path of length three, is a brace if it is bipartite and any two disjoint edges are part of a perfect matching. Our perspective allows us to observe that Barnette's Conjecture can be reduced to cubic, planar braces. We show a similar reduction to braces for cubic, 3-connected, bipartite graphs regarding four stronger versions of Hamiltonicity. Note that in these cases we do not need planarity.As a practical application of these results, we provide some supplements to a generation procedure for cubic, 3-connected, planar, bipartite graphs discovered by Holton et al. (1985) [14]. These allow us to check whether a graph we generated is a brace.     

The multiplicative Weyl functional calculus

The Weyl calculus discussed in the author's previous papers starts with a fixed set of n noncommuting self-adjoint operators and associates an operator to a real function of n variables. The calculus is not multiplicative with respect to point-wise multiplication of functions. However, if the n self-adjoint operators generate a unitary Lie group representation, a “skew product” of functions can be defined which yields multiplicativity. This skew product depends only on the Lie group, not on the particular representation. In the case of the Heisenberg group, this skew product makes it possible to write the Schrödinger equation as an integro-differential equation on the phase plane. Strong convergence of the dynamical group, as Planck's constant goes to zero, to the classical Hamiltonian flow is proved under various conditions on the Hamiltonian.     

Matroidal families of finite connected nonhomeomorphic graphs exist

A matroidal family is a nonempty set ? of connected finite graphs such that for every arbitrary finite graph G the edge sets of the subgraphs of G which are isomorphic to an element of ? form a matroid on the edge set of G. In the present paper the question whether there are any matroidal families besides the four previously described by Simões-Pereira is answered affirmatively. It is shown that for every natural number n ? 2 there is a matroidal family that contains the complete graph with n vertices. For n = 4 this settles Simões-Pereira's conjecture that there is a matroidal family containing all wheels.     

Hamiltonicity of edge chromatic critical graphs

Vizing conjectured that every edge chromatic critical graph contains a 2-factor. Believing that stronger properties hold for this class of graphs, Luo and Zhao (2013) showed that every edge chromatic critical graph of order $n$ with maximum degree at least $\frac{6n}{7}$ is Hamiltonian. Furthermore, Luo et al. (2016) proved that every edge chromatic critical graph of order $n$ with maximum degree at least $\frac{4n}{5}$ is Hamiltonian. In this paper, we prove that every edge chromatic critical graph of order $n$ with maximum degree at least $\frac{3n}{4}$ is Hamiltonian. Our approach is inspired by the recent development of Kierstead path and Tashkinov tree techniques for multigraphs.     

Kolmogorov condition near hyperbolic singularities of integrable Hamiltonian systems

In this paper we show that, if an integrable Hamiltonian system admits a nondegenerate hyperbolic singularity then it will satisfy the Kolmogorov condegeneracy condition near that singularity (under a mild additional condition, which is trivial if the singularity contains a fixed point).      

On Hamiltonian-connected regular graphs

In this paper it is shown that any m-regular graph of order 2m (m ≧ 3), not isomorphic to K_m,m, or of order 2m + 1 (m even, m ≧ 4), is Hamiltonian connected, which extends a previous result of Nash-Williams. As a corollary, it is derived that any such graph contains atleast m Hamiltonian cycles for odd m and atleast 1/2m Hamiltonian cycles for even m.     

Polynomial time recognition and testing of isomorphism of cyclic tournaments

By a tournament is meant an oriented graph any pair of whose vertices is joined by precisely one directed edge; a tournament is cyclic if its automorphism group contains a permutation whose cyclic decomposition consists of a unique cycle containing all vertices. In the present paper we describe an algorithm for recognizing the isomorphism of cyclic tournaments. This algorithm has an arbitrary tournament as input. For this tournament, in polynomial time in the number of its vertices it determines its cyclicity, and when it is cyclic it constructs a canonical form for the tournament and generators of its automorphism group. A procedure which constructs the set of all nonconjugate Hamiltonian permutations for a given permutation group of odd order in polynomial time is of independent interest. The technique of construction of the basic algorithm uses both classical results of the theory of computational complexity with permutation groups and Schur's method of S-rings.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklovaa AN SSSR, Vol. 192, pp. 74–111, 1991.