On the impossibility of Directed Moore Graphs

This note introduces the notion (d, k) Directed Moore Graphs (DMG in short), and investigates the question of their existence. A (d, k) DMG is a regular directed graph of degree d and diameter k containing the maximum number of nodes according to a certain definition. It is shown that unless d = 1 or k = 1 there are no (d, k) DMG's.     

A new method of proving structural properties for certain class of stochastic dynamic control problems

This paper introduces the multimodularity concept to study structural properties for certain class of stochastic dynamic control problems through a new efficient approach. We demonstrate that this approach can substantially simplify the proofs of the main results of one recent article and provide an alternative method for two other models in the literature.     

Radial Moore graphs of radius three

The maximum number of vertices in a graph of specified degree and diameter cannot exceed the Moore bound. Graphs achieving this bound are called Moore graphs. Because Moore graphs are so rare, researchers have considered various relaxations of the Moore graph constraints. Since the diameter of a Moore graph is equal to its radius, one can consider graphs in which the condition on the diameter is relaxed, by one, while the condition on the radius is maintained. Such graphs are called radial Moore graphs. It has previously been shown that radial Moore graphs exist for all degrees when the radius is two. In this paper, we extend this result to radius three. We also construct examples that settle the existence question for a few new cases, and summarize the state of knowledge on the problem.     

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₅.     

On a method of K. Uhlenbeck for proving partial regularity for solutions of certain nonlinear elliptic systems

We extend a method of K. Uhlenbeck for proving the partial regularity of solutions of nonlinear elliptic systems. We do not employ reverse Hölder type inequalities.     

A method for proving polynomial enumeration formulas

We present an elementary method for proving enumeration formulas which are polynomials in certain parameters if others are fixed and factorize into distinct linear factors over Z. Roughly speaking the idea is to prove such formulas by “explaining” their zeros using an appropriate combinatorial extension of the objects under consideration to negative integer parameters. We apply this method to prove a new refinement of the Bender-Knuth (ex-)Conjecture, which easily implies the Bender-Knuth (ex-)Conjecture itself. This is probably the most elementary way to prove this result currently known. Furthermore we adapt our method to q-polynomials, which allows us to derive generating function results as well. Finally we use this method to give another proof for the enumeration of semistandard tableaux of a fixed shape which differs from our proof of the Bender-Knuth (ex-)Conjecture in that it is a multivariate application of our method.     

The reconstruction problem for certain infinite graphs

We are concerned with the notion of the degree-type (D _G ⁱ )_i∈ω of a graphG, whereD _G ⁱ is defined to be the number of vertices inG with degreei. In the first section the following results are proven:

1. IfG is a connected, locally finite, countably infinite graph such that there exists ani so thatD _G ⁱ andD _G ⁱ⁺¹ are both finite and different from 0, thenG is reconstructible.
2. Locally finite, countably infinite graphsG, for which infinitely manyD _G ⁱ are different from 0 but only finitely manyD _G ⁱ are infinite, are reconstructible.

In the second section we give some results about the reconstructibility of certain locally finite countably infinite interval graphs and show that a reconstruction of a planar, infinite graph has to be planar too.     

Multicomponent proof-theoretic method for proving interpolation properties

Proof-theoretic method has been successfully used almost from the inception of interpolation properties to provide efficient constructive proofs thereof. Until recently, the method was limited to sequent calculi (and their notational variants), despite the richness of generalizations of sequent structures developed in structural proof theory in the meantime. In this paper, we provide a systematic and uniform account of the recent extension of this proof-theoretic method to hypersequents, nested sequents, and labelled sequents for normal modal logic. The method is presented in terms and notation easily adaptable to other similar formalisms, and interpolant transformations are stated for typical rule types rather than for individual rules.     

One sufficient condition for hamiltonian graphs

Let G be a 2-connected graph of order n. We show that if for each pair of nonadjacent vertices x,y ∈ V(G), then G is Hamiltonian.     

Connectedness of certain random graphs

L. Dubins conjectured in 1984 that the graph on vertices {1, 2, 3, ...} where an edge is drawn between verticesi andj with probabilityp _ij=λ/max(i, j) independently for each pairi andj is a.s. connected forλ=1. S. Kalikow and B. Weiss proved that the graph is a.s. connected for anyλ>1. We prove Dubin’s conjecture and show that the graph is a.s. connected for anyλ>1/4. We give a proof based on a recent combinatorial result that forλ≦1/4 the graph is a.s. disconnected. This was already proved forλ<1/4 by Kalikow and Weiss. Thusλ=1/4 is the critical value for connectedness, which is surprising since it was believed that the critical value is atλ=1.     

Nonexistence of certain pseudogeometric graphs

Izo($r$) is the pseudogeometric graph for pG${}_r(s,t)$ which satisfies the Krein equality and of which the local graph also satisfies the Krein equality. We prove that Izo($r$) exists if and only if a spherical tight 4-design on $S^{{(2r+1)}^2?4}$ exists. Nonexistence of infinitely many spherical tight 4-designs is well known. It gives the nonexistence of Izo($r$) for infinitely many $r$. Especially, Izo(4) does not exist, which was the first open case.     

On the enumeration of certain weighted graphs

We enumerate weighted simple graphs with a natural upper bound condition on the sum of the weight of adjacent vertices. We also compute the generating function of the numbers of these graphs, and prove that it is a rational function. In particular, we show that the generating function for connected bipartite simple graphs is of the form p₁(x)/(1-x)^m+1. For nonbipartite simple graphs, we get a generating function of the form p₂(x)/(1-x)^m+1(1+x)^l. Here m is the number of vertices of the graph, p₁(x) is a symmetric polynomial of degree at most m, p₂(x) is a polynomial of degree at most m+l, and l is a nonnegative integer. In addition, we give computational results for various graphs.     

On the existence of certain distance-regular graphs

Distance-regular graphs of valency > 2, diameter m, and girth 2m with the additional property that any two points having maximal distance belong to a unique 2m circuit are investigated. It is shown that such graphs can exist only if m ≤ 3; if m = 3 only a finite number of valencies prove to be feasible.     

On the total coloring of certain graphs

In this paper we investigate the total chromatic number of certain graphs. In particular, we show that every cubic graph is totally colorable in five colors.     

On the existence of certain generalized Moore geometries,part III

It is shown that generalized Moore geometries of type GM_m(s,t,c) with c = s + 1 do not exist for m = 6 and m = 7, if st > 1.     

On the existence of certain generalized Moore geometries,part I

Using methods of Algebraic Graph Theory, generalized Moore geometries of type GM_m(s, t, c) with c = s + 1 are investigated. It is shown that such geometries do not exist for odd values of the diameter m exceeding 7, if st>1.