Moore digraph is a digraph with maximum out-degree
d, diameter
k and order
M
d
,
k
=
1
+
d
+
…
+
d
k
. Moore digraphs exist only in trivial cases if
d
=
1
(i.e., directed cycle
C
k
) or
k
=
1
(i.e., ...complete symmetric digraph). Almost Moore digraphs are digraphs of order one less than Moore bound. We shall present new properties of almost Moore digraphs with selfrepeats from which we prove nonexistence of almost Moore digraphs for some
k and
d.
On mixed Moore graphs Nguyen, Minh Hoang; Miller, Mirka; Gimbert, Joan
Discrete mathematics,
04/2007, Letnik:
307, Številka:
7
Journal Article, Conference Proceeding
Recenzirano
Odprti dostop
The Moore bound for a directed graph of maximum out-degree
d and diameter
k is
M
d
,
k
=
1
+
d
+
d
2
+
⋯
+
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
)
+
⋯
+
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 high-density server is featured as low power, low volume, and high computational density. With the rising use of high-density servers in data-intensive and large-scale web applications, it ...requires a high-performance and cost-efficient intra-server interconnection network. Most of state-of-the-art high-density servers adopt the fully-connected intra-server network to attain high network performance. Unfortunately, this solution costs too much due to the high degree of nodes. In this paper, we exploit the theoretically optimized Moore graph to interconnect the chips within a server. Accounting for the suitable size of applications, a 50-size Moore graph, called Hoffman-Singleton graph, is adopted. In practice, multiple chips should be integrated onto one processor board, which means that the original graph should be partitioned into homogeneous connected subgraphs. However, the existing partition scheme does not consider above problem and thus generates heterogeneous subgraphs. To address this problem, we propose two equivalent-partition schemes for the Hoffman-Singleton graph. In addition, a logic-based and minimal routing mechanism, which is both time and area efficient, is proposed. Finally, we compare the proposed network architecture with its counterparts, namely the fully-connected, Kautz and Torus networks. The results show that our proposed network can achieve competitive performance as fully-connected network and cost close to Torus.
On graphs of defect at most 2 Feria-Purón, Ramiro; Miller, Mirka; Pineda-Villavicencio, Guillermo
Discrete Applied Mathematics,
08/2011, Letnik:
159, Številka:
13
Journal Article
Recenzirano
Odprti dostop
In this paper we consider the
degree/diameter problem, namely, given natural numbers
Δ
≥
2
and
D
≥
1
, find the maximum number
N
(
Δ
,
D
)
of vertices in a graph of maximum degree
Δ
and diameter
D
. ...In this context, the Moore bound
M
(
Δ
,
D
)
represents an upper bound for
N
(
Δ
,
D
)
.
Graphs of maximum degree
Δ
, diameter
D
and order
M
(
Δ
,
D
)
, called
Moore graphs, have turned out to be very rare. Therefore, it is very interesting to investigate graphs of maximum degree
Δ
≥
2
, diameter
D
≥
1
and order
M
(
Δ
,
D
)
−
ϵ
with small
ϵ
>
0
, that is,
(
Δ
,
D
,
−
ϵ
)
-graphs. The parameter
ϵ
is called the
defect.
Graphs of defect
1
exist only for
Δ
=
2
. When
ϵ
>
1
,
(
Δ
,
D
,
−
ϵ
)
-graphs represent a wide unexplored area. This paper focuses on graphs of defect
2
. Building on the approaches developed in Feria-Purón and Pineda-Villavicencio (2010)
11 we obtain several new important results on this family of graphs.
First, we prove that the girth of a
(
Δ
,
D
,
−
2
)
-graph with
Δ
≥
4
and
D
≥
4
is
2
D
. Second, and most important, we prove the non-existence of
(
Δ
,
D
,
−
2
)
-graphs with even
Δ
≥
4
and
D
≥
4
; this outcome, together with a proof on the non-existence of
(
4
,
3
,
−
2
)
-graphs (also provided in the paper), allows us to complete the catalogue of
(
4
,
D
,
−
ϵ
)
-graphs with
D
≥
2
and
0
≤
ϵ
≤
2
. Such a catalogue is only the second census of
(
Δ
,
D
,
−
2
)
-graphs known at present, the first being that of
(
3
,
D
,
−
ϵ
)
-graphs with
D
≥
2
and
0
≤
ϵ
≤
2
Jørgensen (1992)
14.
Other results of this paper include necessary conditions for the existence of
(
Δ
,
D
,
−
2
)
-graphs with odd
Δ
≥
5
and
D
≥
4
, and the non-existence of
(
Δ
,
D
,
−
2
)
-graphs with odd
Δ
≥
5
and
D
≥
5
such that
Δ
≡
0
,
2
(
mod
D
)
.
Finally, we conjecture that there are no
(
Δ
,
D
,
−
2
)
-graphs with
Δ
≥
4
and
D
≥
4
, and comment on some implications of our results for the upper bounds of
N
(
Δ
,
D
)
.
Moore bound for mixed networks Nguyen, Minh Hoang; Miller, Mirka
Discrete mathematics,
12/2008, Letnik:
308, Številka:
23
Journal Article
Recenzirano
Odprti dostop
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.
In this paper, we provide some analytical insights into physical architectures that can serve as benchmarks for designing a cost-efficient WDM metropolitan area network (MAN). For uniform all-to-all ...traffic and regular topologies with nodal symmetry, we identify a class of regular graphs-Generalized Moore Graphs-that have several attractive properties by formulating a first-order cost model and characterizing the tradeoff between fiber and switching resources. Our results show that, in conjunction with minimum hop routing, Moore Graphs achieve the minimum cost and simultaneously use the least number of wavelengths. We also take steps to broaden the scope of our work by addressing irregular network topologies, which represent most existing networks. Our results show that Generalized Moore Graphs can be used to provide useful estimates of the cost of irregular networks and can serve as good reference architectures for the designs of practical networks.
A Moore graph is a regular graph of degree
k
and diameter
d
with
v
vertices such that
v
≤ 1 +
k
+
k
(
k
− 1) + ... +
k
(
k
− 1)
d
−1
. It is known that a Moore graph of degree
k
≥ 3 has diameter 2; ...i.e., it is strongly regular with parameters
λ
= 0, µ = 1, and
v
=
k
2
+ 1, where the degree
k
is equal to 3, 7, or 57. It is unknown whether there exists a Moore graph of degree
k
= 57. Aschbacher showed that a Moore graph with
k
= 57 is not a graph of rank 3. In this connection, we call a Moore graph with
k
= 57 the Aschbacher graph and investigate its automorphism group
G
without additional assumptions (earlier, it was assumed that
G
contains an involution).
The (d,k) graph problem which is a stiu open extremal problem in graph theory, has received very much attention from many authors due to its theoretic interest, and also due to its possible ...applications in communication network design. The problem consists in maximizing the number of nodes n of an undirected regular graph (d,k) of degree d and diameter k. In this paper, after a survey of the known results, we present two new families of graphs, and two methods of generating graphs given some existing ones, leading to further substantial improvements of some of the results gathered by Storwick 21 and recently improved by Arden and Lee 3 and also by Imase and Itoh 11.
PDF
