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.     

The beginnings of the R.L. Moore school of topology

The roots of the R.L. Moore school of point set topology were formed around 1900, with Moore's most direct influences coming from his University of Texas teacher, G.B. Halsted, and from his graduate school teachers at the University of Chicago, mainly O. Veblen and E.H. Moore. It was recognized as a school by the 1930s as Moore and his students achieved recognition for their work and as this group interacted with the Polish school of topology. In addition to the mathematical subject, the other main factor that helped to identify this group as a school was the distinctive method of teaching Moore used to introduce the subject to students.     

Moore bound for mixed networks

Mixed graphs contain both undirected as well as directed links between vertices and therefore are an interesting model for interconnection communication networks. In this paper, we establish the Moore bound for mixed graphs, which generalizes both the directed and the undirected Moore bound.     

Multipartite Moore digraphs

We derive some Moore-like bounds for multipartite digraphs, which extend those of bipartite digraphs, under the assumption that every vertex of a given partite set is adjacent to the same number δ of vertices in each of the other independent sets. We determine when a multipartite Moore digraph is weakly distance-regular. Within this framework, some necessary conditions for the existence of a r-partite Moore digraph with interpartite outdegree δ > 1 and diameter k = 2m are obtained. In the case δ = 1, which corresponds to almost Moore digraphs, a necessary condition in terms of the permutation cycle structure is derived. Additionally, we present some constructions of dense multipartite digraphs of diameter two that are vertex-transitive.     

On Moore bipartite digraphs

In the context of the degree/diameter problem for directed graphs, it is known that the number of vertices of a strongly connected bipartite digraph satisfies a Moore‐like bound in terms of its diameter k and the maximum out‐degrees (d₁, d₂) of its partite sets of vertices. It has been proved that, when d₁d₂ > 1, the digraphs attaining such a bound, called Moore bipartite digraphs, only exist when 2 ≤ k ≤ 4. This paper deals with the problem of their enumeration. In this context, using the theory of circulant matrices and the so‐called De Bruijn near‐factorizations of cyclic groups, we present some new constructions of Moore bipartite digraphs of diameter three and composite out‐degrees. By applying the iterated line digraph technique, such constructions also provide new families of dense bipartite digraphs with arbitrary diameter. Moreover, we show that the line digraph structure is inherent in any Moore bipartite digraph G of diameter k = 4, which means that G = L G′, where G′ is a Moore bipartite digraph of diameter k = 3. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 171–187, 2003     

On critical sets of a finite Moore family

Cluster collections obtained within the framework of most cluster structures studied in data analysis and classification are essentially Moore families. In this paper, we propose a simple intuitive necessary and sufficient condition for some subset of objects to be a critical set of a finite Moore family. This condition is based on a new characterization of quasi-closed sets. Moreover, we provide a necessary condition for a subset containing more than k objects (k ≥ 2) to be a critical set of a k-weakly hierarchical Moore family. Finally, as a consequence of this result, we identify critical sets of some k-weakly hierarchical Moore families and thereby generalize a result earlier obtained by Domenach and Leclerc in the particular case of weak hierarchies.     

Higher Dimensional Moore Bounds

Upper bounds on the face numbers of simplicial complexes are proven in terms on their girths, in analogy with the Moore bound from graph theory. Our definition of girth generalizes the usual definition for graphs.     

Fleissner's normal Moore space and lynxes

We review Fleissner's CH construction of a normal non-metrizable Moore space and investigate forcings that preserve its non-metrizability.     

Complete characterization of almost Moore digraphs of degree three

It is well known that Moore digraphs do not exist except for trivial cases (degree 1 or diameter 1), but there are digraphs of diameter two and arbitrary degree which miss the Moore bound by one. No examples of such digraphs of diameter at least three are known, although several necessary conditions for their existence have been obtained. In this paper, we prove that digraphs of degree three and diameter k ≥ 3 which miss the Moore bound by one do not exist. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 112–126, 2005     

Domain representability and the Choquet game in Moore and BCO-spaces

In this paper we investigate the role of domain representability and Scott-domain representability in the class of Moore spaces and the larger class of spaces with a base of countable order. We show, for example, that in a Moore space, the following are equivalent: domain representability; subcompactness; the existence of a winning strategy for player α (= the nonempty player) in the strong Choquet game Ch(X); the existence of a stationary winning strategy for player α in Ch(X); and Rudin completeness. We note that a metacompact ?ech-complete Moore space described by Tall is not Scott-domain representable and also give an example of ?ech-complete separable Moore space that is not co-compact and hence not Scott-domain representable. We conclude with a list of open questions.     

On the non-productivity of normality in Moore spaces

Under Martin's Axiom and the denial of the Continuum Hypothesis, the authors give examples of normal Moore spaces whose squares are not normal.

     

Which Faber–Moore–Chen digraphs are Cayley digraphs?

The problem of finding the largest graphs and digraphs of given degree and diameter is known as the ‘degree–diameter’ problem. One of the families of largest known vertex-transitive digraphs of given degree and diameter is the Faber–Moore–Chen digraphs. In our contribution we will classify those Faber–Moore–Chen digraphs that are Cayley digraphs.     

One method for proving the impossibility of certain Moore graphs

A Moore (d, k)-graph is a regular graph of degree d with diameter k and girth 2k + 1. It is proved that every edge of a Moore (d, k)-graph is contained in the same number r_m cycles of length m, where m ? 4k + 1. A recurrence relation for r_m is given. Further, some corollaries, as for the impossibility of certain Moore graphs, are shown, e.g., if 3 ? d ? 100 and 3 ? k ? 100, then there is no Moore (d, k)-graph.     

Further results on the Moore–Penrose invertibility of projectors and its applications

The aim of this article is to investigate new results on the Moore–Penrose invertibility of the products and differences of projectors and generalized projectors. The range relations of projectors and the detailed representations for Moore–Penrose inverses are presented.     

The Moore–Penrose inverse of a companion matrix

Necessary and sufficient conditions are given for the Moore–Penrose inverse of a companion matrix over an arbitrary ring to exist.     

Search for properties of the missing Moore graph

In the degree-diameter problem, the only extremal graph the existence of which is still in doubt is the Moore graph of order 3250, degree 57 and diameter 2. It has been known that such a graph cannot be vertex-transitive. Also, certain restrictions on the structure of the automorphism group of such a graph have been known in the case when the order of the group is even. In this paper we further investigate symmetries and structural properties of the missing Moore (57, 2)-graph(s) with the help of a combination of spectral, group-theoretic, combinatorial, and computational methods. One of the consequences is that the order of the automorphism group of such a graph is at most 375.     

On mixed Moore graphs

The Moore bound for a directed graph of maximum out-degree d and diameter k is $M_{d,k}=1+d+d^2+\cdots +d^k$. It is known that digraphs of order $M_{d,k}$ (Moore digraphs) do not exist for $d>1$ and $k>1$. Similarly, the Moore bound for an undirected graph of maximum degree d and diameter k is $M_{d,k}^{*}=1+d+d(d-1)+\cdots +d(d-1{)}^{k-1}$. Undirected Moore graphs only exist in a small number of cases. Mixed (or partially directed) Moore graphs generalize both undirected and directed Moore graphs. In this paper, we shall show that all known mixed Moore graphs of diameter $k=2$ are unique and that mixed Moore graphs of diameter $k⩾3$ do not exist.     

The Moore Bound for Irregular Graphs

 What is the largest number of edges in a graph of order n and girth g? For d-regular graphs, essentially the best known answer is provided by the Moore bound. This result is extended here to cover irregular graphs as well, yielding an affirmative answer to an old open problem ([4] p. 163, problem 10). Received: June 27, 2000 Final version received: July 3, 2001     

Moore Graphs and Cycles Are Extremal Graphs for Convex Cycles

Let denote the number of convex cycles of a simple graph G of order n, size m, and girth . It is proved that and that equality holds if and only if G is an even cycle or a Moore graph. The equality also holds for a possible Moore graph of diameter 2 and degree 57 thus giving a new characterization of Moore graphs.     

Enumerations of vertex orders of almost Moore digraphs with selfrepeats

An almost Moore digraph G of degree d>1, diameter k>1 is a diregular digraph with the number of vertices one less than the Moore bound. If G is an almost Moore digraph, then for each vertex u∈V(G) there exists a vertex v∈V(G), called repeat of u and denoted by r(u)=v, such that there are two walks of length ?k from u to v. The smallest positive integer p such that the composition r^p(u)=u is called the order of u. If the order of u is 1 then u is called a selfrepeat. It is known that if G is an almost Moore digraph of diameter k?3 then G contains exactly k selfrepeats or none. In this paper, we propose an exact formula for the number of all vertex orders in an almost Moore digraph G containing selfrepeats, based on the vertex orders of the out-neighbours of any selfrepeat vertex.