Displaying similar documents to “Problems remaining NP-complete for sparse or dense graphs”

Hamiltonian-colored powers of strong digraphs

Garry Johns, Ryan Jones, Kyle Kolasinski, Ping Zhang (2012)

Discussiones Mathematicae Graph Theory

Similarity:

For a strong oriented graph D of order n and diameter d and an integer k with 1 ≤ k ≤ d, the kth power D k of D is that digraph having vertex set V(D) with the property that (u, v) is an arc of D k if the directed distance d D ( u , v ) from u to v in D is at most k. For every strong digraph D of order n ≥ 2 and every integer k ≥ ⌈n/2⌉, the digraph D k is Hamiltonian and the lower bound ⌈n/2⌉ is sharp. The digraph D k is distance-colored if each arc (u, v) of D k is assigned the color i where i = d D ( u , v ) . The digraph...

Potential forbidden triples implying hamiltonicity: for sufficiently large graphs

Ralph J. Faudree, Ronald J. Gould, Michael S. Jacobson (2005)

Discussiones Mathematicae Graph Theory

Similarity:

In [1], Brousek characterizes all triples of connected graphs, G₁,G₂,G₃, with G i = K 1 , 3 for some i = 1,2, or 3, such that all G₁G₂ G₃-free graphs contain a hamiltonian cycle. In [8], Faudree, Gould, Jacobson and Lesniak consider the problem of finding triples of graphs G₁,G₂,G₃, none of which is a K 1 , s , s ≥ 3 such that G₁G₂G₃-free graphs of sufficiently large order contain a hamiltonian cycle. In [6], a characterization was given of all triples G₁,G₂,G₃ with none being K 1 , 3 , such that all G₁G₂G₃-free...

On a family of cubic graphs containing the flower snarks

Jean-Luc Fouquet, Henri Thuillier, Jean-Marie Vanherpe (2010)

Discussiones Mathematicae Graph Theory

Similarity:

We consider cubic graphs formed with k ≥ 2 disjoint claws C i K 1 , 3 (0 ≤ i ≤ k-1) such that for every integer i modulo k the three vertices of degree 1 of C i are joined to the three vertices of degree 1 of C i - 1 and joined to the three vertices of degree 1 of C i + 1 . Denote by t i the vertex of degree 3 of C i and by T the set t , t , . . . , t k - 1 . In such a way we construct three distinct graphs, namely FS(1,k), FS(2,k) and FS(3,k). The graph FS(j,k) (j ∈ 1,2,3) is the graph where the set of vertices i = 0 i = k - 1 V ( C i ) T induce j cycles (note...

The cubic Szegő equation

Patrick Gérard, Sandrine Grellier (2010)

Annales scientifiques de l'École Normale Supérieure

Similarity:

We consider the following Hamiltonian equation on the L 2 Hardy space on the circle, i t u = Π ( | u | 2 u ) , where Π is the Szegő projector. This equation can be seen as a toy model for totally non dispersive evolution equations. We display a Lax pair structure for this equation. We prove that it admits an infinite sequence of conservation laws in involution, and that it can be approximated by a sequence of finite dimensional completely integrable Hamiltonian systems. We establish several...

Forbidden triples implying Hamiltonicity: for all graphs

Ralph J. Faudree, Ronald J. Gould, Michael S. Jacobson (2004)

Discussiones Mathematicae Graph Theory

Similarity:

In [2], Brousek characterizes all triples of graphs, G₁, G₂, G₃, with G i = K 1 , 3 for some i = 1, 2, or 3, such that all G₁G₂G₃-free graphs contain a hamiltonian cycle. In [6], Faudree, Gould, Jacobson and Lesniak consider the problem of finding triples of graphs G₁, G₂, G₃, none of which is a K 1 , s , s ≥ 3 such that G₁, G₂, G₃-free graphs of sufficiently large order contain a hamiltonian cycle. In this paper, a characterization will be given of all triples G₁, G₂, G₃ with none being K 1 , 3 , such that all...

A note on a new condition implying pancyclism

Evelyne Flandrin, Hao Li, Antoni Marczyk, Mariusz Woźniak (2001)

Discussiones Mathematicae Graph Theory

Similarity:

We first show that if a 2-connected graph G of order n is such that for each two vertices u and v such that δ = d(u) and d(v) < n/2 the edge uv belongs to E(G), then G is hamiltonian. Next, by using this result, we prove that a graph G satysfying the above condition is either pancyclic or isomorphic to K n / 2 , n / 2 .

Hofer’s metrics and boundary depth

Michael Usher (2013)

Annales scientifiques de l'École Normale Supérieure

Similarity:

We show that if ( M , ω ) is a closed symplectic manifold which admits a nontrivial Hamiltonian vector field all of whose contractible closed orbits are constant, then Hofer’s metric on the group of Hamiltonian diffeomorphisms of  ( M , ω ) has infinite diameter, and indeed admits infinite-dimensional quasi-isometrically embedded normed vector spaces. A similar conclusion applies to Hofer’s metric on various spaces of Lagrangian submanifolds, including those Hamiltonian-isotopic to the diagonal in  M × M ...

Extension of several sufficient conditions for Hamiltonian graphs

Ahmed Ainouche (2006)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a 2-connected graph of order n. Suppose that for all 3-independent sets X in G, there exists a vertex u in X such that |N(X∖u)|+d(u) ≥ n-1. Using the concept of dual closure, we prove that 1. G is hamiltonian if and only if its 0-dual closure is either complete or the cycle C₇ 2. G is nonhamiltonian if and only if its 0-dual closure is either the graph ( K r K K ) K , 1 ≤ r ≤ s ≤ t or the graph ( ( n + 1 ) / 2 ) K K ( n - 1 ) / 2 . It follows that it takes a polynomial time to check the hamiltonicity or the nonhamiltonicity...

Perturbation results for a class of singular Hamiltonian systems

Antonio Ambrosetti, Ivar Ekeland (1989)

Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti

Similarity:

The existence of solutions with prescribed period T for a class of Hamiltonian systems with a Keplerian singularity is discussed.

Derivation of Hartree’s theory for mean-field Bose gases

Mathieu Lewin (2013)

Journées Équations aux dérivées partielles

Similarity:

This article is a review of recent results with Phan Thành Nam, Nicolas Rougerie, Sylvia Serfaty and Jan Philip Solovej. We consider a system of N bosons with an interaction of intensity 1 / N (mean-field regime). In the limit N , we prove that the first order in the expansion of the eigenvalues of the many-particle Hamiltonian is given by the nonlinear Hartree theory, whereas the next order is predicted by the Bogoliubov Hamiltonian. We also discuss the occurrence of Bose-Einstein condensation...

Spectral radius and Hamiltonicity of graphs with large minimum degree

Vladimir Nikiforov (2016)

Czechoslovak Mathematical Journal

Similarity:

Let G be a graph of order n and λ ( G ) the spectral radius of its adjacency matrix. We extend some recent results on sufficient conditions for Hamiltonian paths and cycles in G . One of the main results of the paper is the following theorem: Let k 2 , n k 3 + k + 4 , and let G be a graph of order n , with minimum degree δ ( G ) k . If λ ( G ) n - k - 1 , then G has a Hamiltonian cycle, unless G = K 1 ( K n - k - 1 + K k ) or G = K k ( K n - 2 k + K ¯ k ) .

Variations on a sufficient condition for Hamiltonian graphs

Ahmed Ainouche, Serge Lapiquonne (2007)

Discussiones Mathematicae Graph Theory

Similarity:

Given a 2-connected graph G on n vertices, let G* be its partially square graph, obtained by adding edges uv whenever the vertices u,v have a common neighbor x satisfying the condition N G ( x ) N G [ u ] N G [ v ] , where N G [ x ] = N G ( x ) x . In particular, this condition is satisfied if x does not center a claw (an induced K 1 , 3 ). Clearly G ⊆ G* ⊆ G², where G² is the square of G. For any independent triple X = x,y,z we define σ̅(X) = d(x) + d(y) + d(z) - |N(x) ∩ N(y) ∩ N(z)|. Flandrin et al. proved that a 2-connected graph G is hamiltonian...

Cycle-pancyclism in bipartite tournaments II

Hortensia Galeana-Sánchez (2004)

Discussiones Mathematicae Graph Theory

Similarity:

Let T be a hamiltonian bipartite tournament with n vertices, γ a hamiltonian directed cycle of T, and k an even number. In this paper the following question is studied: What is the maximum intersection with γ of a directed cycle of length k contained in T[V(γ)]? It is proved that for an even k in the range (n+6)/2 ≤ k ≤ n-2, there exists a directed cycle C h ( k ) of length h(k), h(k) ∈ k,k-2 with | A ( C h ( k ) ) A ( γ ) | h ( k ) - 4 and the result is best possible. In a previous paper a similar result for 4 ≤ k ≤ (n+4)/2 was...

Hamiltonicity of cubic Cayley graphs

Henry Glover, Dragan Marušič (2007)

Journal of the European Mathematical Society

Similarity:

Following a problem posed by Lovász in 1969, it is believed that every finite connected vertex-transitive graph has a Hamilton path. This is shown here to be true for cubic Cayley graphs arising from finite groups having a ( 2 , s , 3 ) -presentation, that is, for groups G = a , b a 2 = 1 , b s = 1 , ( a b ) 3 = 1 , generated by an involution a and an element b of order s 3 such that their product a b has order 3 . More precisely, it is shown that the Cayley graph X = Cay ( G , { a , b , b - 1 } ) has a Hamilton cycle when | G | (and thus s ) is congruent to 2 modulo 4, and has a...

Growth of Sobolev norms in the cubic defocusing nonlinear Schrödinger equation

Marcel Guardia, Vadim Kaloshin (2015)

Journal of the European Mathematical Society

Similarity:

We consider the cubic defocusing nonlinear Schrödinger equation in the two dimensional torus. Fix s > 1 . Recently Colliander, Keel, Staffilani, Tao and Takaoka proved the existence of solutions with s -Sobolev norm growing in time. We establish the existence of solutions with polynomial time estimates. More exactly, there is c > 0 such that for any 𝒦 1 we find a solution u and a time T such that u ( T ) H s 𝒦 u ( 0 ) H s . Moreover, the time T satisfies the polynomial bound 0 < T < 𝒦 C .

Analytic invariants for the 1 : - 1 resonance

José Pedro Gaivão (2013)

Annales de l’institut Fourier

Similarity:

Associated to analytic Hamiltonian vector fields in 4 having an equilibrium point satisfying a non semisimple 1 : - 1 resonance, we construct two constants that are invariant with respect to local analytic symplectic changes of coordinates. These invariants vanish when the Hamiltonian is integrable. We also prove that one of these invariants does not vanish on an open and dense set.

Overview of the differential Galois integrability conditions for non-homogeneous potentials

Andrzej J. Maciejewski, Maria Przybylska (2011)

Banach Center Publications

Similarity:

We report our recent results concerning integrability of Hamiltonian systems governed by Hamilton’s function of the form H = 1 / 2 i = 1 n p ² i + V ( q ) , where the potential V is a finite sum of homogeneous components. In this paper we show how to find, in the differential Galois framework, computable necessary conditions for the integrability of such systems. Our main result concerns potentials of the form V = V k + V K , where V k and V K are homogeneous functions of integer degrees k and K > k, respectively. We present examples...

Invariants, conservation laws and time decay for a nonlinear system of Klein-Gordon equations with Hamiltonian structure

Changxing Miao, Youbin Zhu (2006)

Applicationes Mathematicae

Similarity:

We discuss invariants and conservation laws for a nonlinear system of Klein-Gordon equations with Hamiltonian structure ⎧ u t t - Δ u + m ² u = - F ( | u | ² , | v | ² ) u , ⎨ ⎩ v t t - Δ v + m ² v = - F ( | u | ² , | v | ² ) v for which there exists a function F(λ,μ) such that ∂F(λ,μ)/∂λ = F₁(λ,μ), ∂F(λ,μ)/∂μ = F₂(λ,μ). Based on Morawetz-type identity, we prove that solutions to the above system decay to zero in local L²-norm, and local energy also decays to zero if the initial energy satisfies E ( u , v , , 0 ) = 1 / 2 ( | u ( 0 ) | ² + | u t ( 0 ) | ² + m ² | u ( 0 ) | ² + | v ( 0 ) | ² + | v t ( 0 ) | ² + m ² | v ( 0 ) | ² + F ( | u ( 0 ) | ² , | v ( 0 ) | ² ) ) d x < , and F₁(|u|²,|v|²)|u|² + F₂(|u|²,|v|²)|v|² - F(|u|²,|v|²) ≥ aF(|u|²,|v|²) ≥ 0, a >...