Counterexamples to the edge reconstruction conjecture for infinite graphs

For every infinite cardinal α, there exists a graph with α edges which is not uniquely reconstructible from its family of edge-deleted subgraphs.     

Some applications of the nash-williams lemma to the edge-reconstruction conjecture

It is shown that a graph whose vertices have one of four possible degrees is edgereconstructible if either 8 ord 2log ₂ 68, where andd are the minimum and the average degree of a graph respectively.     

Family of counterexamples to King's conjecture

In this short Note we present an infinite family of arbitrary high dimensional counterexamples to the King's conjecture.     

Some counterexamples to a generalized Saari's conjecture

For the Newtonian -body problem, Saari's conjecture states that the only solutions with a constant moment of inertia are relative equilibria, solutions rigidly rotating about their center of mass. We consider the same conjecture applied to Hamiltonian systems with power-law potential functions. A family of counterexamples is given in the five-body problem (including the Newtonian case) where one of the masses is taken to be negative. The conjecture is also shown to be false in the case of the inverse square potential and two kinds of counterexamples are presented. One type includes solutions with collisions, derived analytically, while the other consists of periodic solutions shown to exist using standard variational methods.

     

An analogue of the Descartes-Euler formula for infinite graphs and Higuchi's conjecture

Let be a connected 2-manifold without boundary obtained from a (possibly infinite) collection of polygons by identifying them along edges of equal length. Let be the set of vertices, and for every , let denote the (Gaussian) curvature of : minus the sum of incident polygon angles. Descartes showed that whenever may be realized as the surface of a convex polytope in . More generally, if is made of finitely many polygons, Euler's formula is equivalent to the equation where is the Euler characteristic of . Our main theorem shows that whenever converges and there is a positive lower bound on the distance between any pair of vertices in , there exists a compact closed 2-manifold and an integer so that is homeomorphic to minus points, and further .

In the special case when every polygon is regular of side length one and for every vertex , we apply our main theorem to deduce that is made of finitely many polygons and is homeomorphic to either the 2-sphere or to the projective plane. Further, we show that unless is a prism, antiprism, or the projective planar analogue of one of these that . This resolves a recent conjecture of Higuchi.

     

On possible counterexamples to Negami's planar cover conjecture

A simple graph H is a cover of a graph G if there exists a mapping φ from H onto G such that φ maps the neighbors of every vertex υ in H bijectively to the neighbors of φ (υ) in G . Negami conjectured in 1986 that a connected graph has a finite planar cover if and only if it embeds in the projective plane. The conjecture is still open. It follows from the results of Archdeacon, Fellows, Negami, and the first author that the conjecture holds as long as the graph K _1,2,2,2 has no finite planar cover. However, those results seem to say little about counterexamples if the conjecture was not true. We show that there are, up to obvious constructions, at most 16 possible counterexamples to Negami's conjecture. Moreover, we exhibit a finite list of sets of graphs such that the set of excluded minors for the property of having finite planar cover is one of the sets in our list. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 183–206, 2004     

Very degenerate polynomial submersions and counterexamples to the real Jacobian conjecture

Until recently, the only known examples of non-injective polynomial local diffeomorphisms of the plane were the Pinchuk maps discovered in 1994. These maps have the form $(p,q)$, where p is a fixed polynomial of degree 10, and q satisfies certain relation. The lowest possible degree of q in a Pinchuk map is 25. In 2021, with the same p of a Pinchuk map, another example was given with q of degree 15. Aiming to find different examples, with the first components having lower degrees, we look for polynomials of degree less than or equal to 9 sharing some properties with the polynomial p of a Pinchuk map. We find precisely one polynomial of degree 7 and some ones of degree 9. By using one of the polynomials of degree 9 in the first component we construct a non-injective polynomial local diffeomorphism of the plane, with degree 15.     

A class of counterexamples to the Gel´fand-Kirillov conjecture

Let be a connected non-special semisimple algebraic group and let be a finite dimensional -representation such that has trivial generic stabilizer. Let . Then the semi-direct product is a counter-example to the Gel´fand-Kirillov conjecture.

     

Domination graphs: examples and counterexamples

We give a counterexample to a conjecture of Dahlhaus et al. [3] claiming that the Special Quadratic Consensus Method yields a polynomial-time recognition for domination graphs, and discuss several new properties of domination graphs.     

A restriction on the combinatorial structure of counterexamples to the Jacobian conjecture at infinity

A constraint on the combinatorial structure of a meromorphic immersion of a (+1)-pair (v, l) in the space ?² with one dicritical component is found.     

The gallai-younger conjecture for planar graphs

Younger conjectured that for everyk there is ag(k) such that any digraphG withoutk vertex disjoint cycles contains a setX of at mostg(k) vertices such thatG–X has no directed cycles. Gallai had previously conjectured this result fork=1. We prove this conjecture for planar digraphs. Specifically, we show that ifG is a planar digraph withoutk vertex disjoint directed cycles, thenG contains a set of at mostO(klog(k)log(log(k))) vertices whose removal leaves an acyclic digraph. The work also suggests a conjecture concerning an extension of Vizing's Theorem for planar graphs.     

Meyniel's conjecture holds for random graphs

In the game of cops and robber, the cops try to capture a robber moving on the vertices of the graph. The minimum number of cops required to win on a given graph G is called the cop number of G. The biggest open conjecture in this area is the one of Meyniel, which asserts that for some absolute constant C, the cop number of every connected graph G is at most . In this paper, we show that Meyniel's conjecture holds asymptotically almost surely for the binomial random graph , which improves upon existing results showing that asymptotically almost surely the cop number of is provided that for some . We do this by first showing that the conjecture holds for a general class of graphs with some specific expansion‐type properties. This will also be used in a separate paper on random d‐regular graphs, where we show that the conjecture holds asymptotically almost surely when . © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 396–421, 2016     

Proof of the Seymour conjecture for large graphs

Paul Seymour conjectured that any graphG of ordern and minimum degree of at leastk/k+1n contains thekth power of a Hamiltonian cycle. Here, we prove this conjecture for sufficiently largen.     

Vizing’s conjecture for chordal graphs

Vizing conjectured that γ(G□H)≥γ(G)γ(H) for every pair G,H of graphs, where “□” is the Cartesian product, and γ(G) is the domination number of the graph G. Denote by γⁱ(G) the maximum, over all independent sets I in G, of the minimal number of vertices needed to dominate I. We prove that γ(G□H)≥γⁱ(G)γ(H). Since for chordal graphs γⁱ=γ, this proves Vizing’s conjecture when G is chordal.     

The reconstruction conjecture for finite simple graphs and associated directed graphs

In this paper, we study the Reconstruction Conjecture for finite simple graphs. Let Γ and ${\mathrm{\Gamma }}^{\prime }$ be finite simple graphs with at least three vertices such that there exists a bijective map $f:V(\mathrm{\Gamma })\to V({\mathrm{\Gamma }}^{\prime })$ and for any $v\in V(\mathrm{\Gamma })$, there exists an isomorphism ${?}_v:\mathrm{\Gamma }?v\to {\mathrm{\Gamma }}^{\prime }?f(v)$. Then we define the associated directed graph $\stackrel{?}{\mathrm{\Gamma }}=\stackrel{?}{\mathrm{\Gamma }}(\mathrm{\Gamma },{\mathrm{\Gamma }}^{\prime },f,{\{{?}_v\}}_{v\in V(\mathrm{\Gamma })})$ with two kinds of arrows from the graphs Γ and ${\mathrm{\Gamma }}^{\prime }$, the bijective map f and the isomorphisms ${\{{?}_v\}}_{v\in V(\mathrm{\Gamma })}$. By investigating the associated directed graph $\stackrel{?}{\mathrm{\Gamma }}$, we study when are the two graphs Γ and ${\mathrm{\Gamma }}^{\prime }$ isomorphic.