Problems remaining NP-complete for sparse or dense graphs

Ingo Schiermeyer

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

An upper bound of a generalized upper Hamiltonian number of a graph

Martin Dzúrik (2021)

Archivum Mathematicum

Similarity:

In this article we study graphs with ordering of vertices, we define a generalization called a pseudoordering, and for a graph $H$ we define the $H$ -Hamiltonian number of a graph $G$ . We will show that this concept is a generalization of both the Hamiltonian number and the traceable number. We will prove equivalent characteristics of an isomorphism of graphs $G$ and $H$ using $H$ -Hamiltonian number of $G$ . Furthermore, we will show that for a fixed number of vertices, each path has a maximal upper...

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 $^{\to} 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 =^{\to} d_{D} (u, v)$ . The digraph...

Factors and circuits in $K_{1, 3}$ -free graphs

Zdeněk Ryjáček (1989)

Banach Center Publications

Similarity:

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 \partial_{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 \times 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} \cup K ₛ \cup K ₜ) \lor K ₂$ , 1 ≤ r ≤ s ≤ t or the graph $((n + 1) / 2) K ₁ \lor 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 \to \infty$ , 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 \geq 2,$ $n \geq k^{3} + k + 4,$ and let $G$ be a graph of order $n$ , with minimum degree $δ (G) \geq k .$ If $λ (G) \geq n - k - 1,$ then $G$ has a Hamiltonian cycle, unless $G = K_{1} \lor (K_{n - k - 1} + K_{k})$ or $G = K_{k} \lor (K_{n - 2 k} + {\bar{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) \subseteq N_{G} [u] \cup N_{G} [v]$ , where $N_{G} [x] = N_{G} (x) \cup 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)}) \cap A (γ) | \geq 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, \dots 〉$ generated by an involution $a$ and an element $b$ of order $s \geq 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}} \geq 𝒦 {∥ u (0) ∥}_{H^{s}}$ . Moreover, the time $T$ satisfies the polynomial bound $0 < T < 𝒦^{C}$ .