Simpler counterexamples to the edge-reconstruction conjecture for infinite graphs

A nonisomorphic, edge-hypomorphic pair of countable forests is constructed, hereby providing a counterexample to the edge-reconstruction conjecture for infinite graphs that is simpler than the counterexamples previously given by C. Thomassen. In addition, to answer the questions posed by C. Thomassen in a previous paper, it is shown that there is a countable forest that is vertex-reconstructible but not edge-reconstructible, and that there is a countable, connected graph with these properties.     

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.     

An analogue of nakai's conjecture

Let R be an associative ring with 1 and let T be a hereditary torsion theory in the category of left R-modules. In defining the localizatio n of R respect to x, the concept of T-injective module arises (see [5] , [11]) . We can consider the family E _T of all short exact sequences of left R-modules respect to which every T-injective left R-module is injective . E _T proper class in the sense defined in [ 9] . In this paper we characterize proper classe s which are of the form E _T for some hereditary torsion theory x. On the other hand, we give some conditions on x, which imply that E _T has enough projectives , and we show an example where E _T does not have enough projectives.     

A product formula for orthogonal polynomials associated with infinite distance-transitive graphs

The infinite, locally finite distance-transitive graphs form an extension of homogeneous trees and are described by two discrete parameters. The associated orthogonal polynomials may be regarded as spherical functions of certain Gelfand pairs or as characters of some polynomial hypergroups; they are certain Bernstein polynomials and admit a discrete nonnegative product formula. In this paper we use the graph-theoretic origin of these polynomials to derive the existence of positive dual continuous product and transfer formulas. The dual product formulas will be computed explicitly.     

An analogue of the rauch variational formula for prym differentials

In [5], H. E. Rauch discovered a formula for the first variation of an abelian differential on a Riemann surface and its periods with respect to the change of complex structure induced by a Beltrami differential. R. S. Hamilton, in [3], and discussed by C. Earle in [1], found an elegant proof of the formula using only first principles and not requiring uniformization theory. His proof uses a small amount of Hodge theory, the Riemann bilinear period relations, and a simple operator construction. In this article, we find an analogue of Rauch’s formula for the Prym differentials using some of Hamilton’s techniques, the Hodge theorem for vector bundles, and the “Prym version” of the Riemann bilinear relations. We discover a complicated set of formulas for the variation of the Prym differentials, with different specific solutions depending to the make-up of the Prym character. We conclude that the variation of the Prym periods with a given character depends on the differentials for the character and the differentials for its inverse. This explains the simplicity of the classical case, where the character is its inverse.     

An analogue of Berry's conjecture for the phase in fractal obstacle scattering

In this paper, the authors consider the high-frequency asymptoticsof the phase s() of acoustic waves scattered by an obstacleRⁿ with fractal boundary. Under certain conditions, it is provedthat if is –Minkowski measurable with –Minkowskimeasure µ then there exists a positive constant C_n, dependingonlyon n and such that where     

An infinite color analogue of Rado's theorem

Let R be a subring of the complex numbers and a be a cardinal. A system L of linear homogeneous equations with coefficients in R is called a-regular over R if, for every a-coloring of the nonzero elements of R, there is a monochromatic solution to L in distinct variables. In 1943, Rado classified those finite systems of linear homogeneous equations that are a-regular over R for all positive integers a. For every infinite cardinal a, we classify those finite systems of linear homogeneous equations that are a-regular over R. As a corollary, for every positive integer s, we have ℵ₀²>ℵs if and only if the equation x₀+sx₁=x₂+?+xs+2 is ℵ₀-regular over R. This generalizes the case s=1 due to Erd?s.     

An infinite family of biprimitive semisymmetric graphs

A regular and edge-transitive graph that is not vertex-transitive is said to be semisymmetric. Every semisymmetric graph is necessarily bipartite, with the two parts having equal size and the automorphism group acting transitively on each of these two parts. A semisymmetric graph is called biprimitive, if its automorphism group acts primitively on each part. In this article, a classification of biprimitive semisymmetric graphs arising from the action of the group PSL(2, p), p ≡ ±1 (mod 8) a prime, acting on cosets of S₄ is given, resulting in several new infinite families of biprimitive semisymmetric graphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 217–228, 1999     

An infinite family of tetravalent half-arc-transitive graphs

A graph is half-arc-transitive if its automorphism group acts transitively on vertices and edges, but not on arcs. In this paper, a new infinite family of tetravalent half-arc-transitive graphs with girth 4 is constructed, each of which has order 16m such that m>1 is a divisor of 2t²+2t+1 for a positive integer t and is tightly attached with attachment number 4m. The smallest graph in the family has order 80.     

An analogue of group divisible designs for Moore graphs

We study graphs whose adjacency matrix S of order n satisfies the equation S + S² = J ? K + kI, where J is a matrix of order n of all 1's, K is the direct sum on $\text{n}\text{l}$ matrices of order l of all 1's, and I is the identity matrix. Moore graphs are the only solutions to the equation in the case l = 1 for which K = I. In the case k = l we can obtain Moore graphs from a solution S by a bordering process analogous to obtaining (ν, κ, λ)-designs from some group divisible designs. Other parameters are rare. We are able to find one new interesting graph with parameters k = 6, l = 4 on n = 40 vertices. We show that it has a transitive automorphism group isomorphic to C₄ × S₅.     

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.     

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     

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.     

An analogue of the Harer-Zagier formula for unicellular maps on general surfaces

A unicellular map is the embedding of a connected graph in a surface in such a way that the complement of the graph is simply connected. In a famous article, Harer and Zagier established a formula for the generating function of unicellular maps counted according to the number of vertices and edges. The keystone of their approach is a counting formula for unicellular maps on orientable surfaces with n edges, and with vertices colored using every color in [q] (adjacent vertices are authorized to have the same color). We give an analogue of this formula for general (locally orientable) surfaces.Our approach is bijective and is inspired by Lass?s proof of the Harer-Zagier formula. We first revisit Lass?s proof and twist it into a bijection between unicellular maps on orientable surfaces with vertices colored using every color in [q], and maps with vertex set [q] on orientable surfaces with a marked spanning tree. The bijection immediately implies Harer-Zagier?s formula and a formula by Jackson concerning bipartite unicellular maps. It also shed a new light on constructions by Goulden and Nica, Schaeffer and Vassilieva, and Morales and Vassilieva. We then extend the bijection to general surfaces and obtain a correspondence between unicellular maps on general surfaces with vertices colored using every color in [q], and maps on orientable surfaces with vertex set [q]with a marked planar submap. This correspondence gives an analogue of the Harer-Zagier formula for general surfaces. We also show that this formula implies a recursion formula due to Ledoux for the numbers of unicellular maps with given numbers of vertices and edges.     

Behzad-Vizing conjecture and Cartesian-product graphs

We prove the following theorem: if the Behzad-Vizing conjecture is true for graphs G and H, then is it true for the Cartesian product G□H.