We consider the critical group of a hypothetical Moore graph of diameter 2 and valency 57. Determining this group is equivalent to finding the Smith normal form of the Laplacian matrix of such a ...graph. We show that all of the Sylow p-subgroups of the critical group must be elementary abelian with the exception of p=5. We prove that the 5-rank of the Laplacian matrix determines the critical group up to two possibilities.
Let
k
be a positive integer. A
k
-tuple (total) dominating set in a graph
G
is a subset
S
of its vertices such that any vertex
v
in
G
has at least
k
vertices inside
S
among its neighbors and
v
itself ...(resp. among its neighbors only). The minimum size of a
k
-tuple (total) dominating set for
G
is called the
k
-tuple (total) domination number of
G
. It is shown in this article that the
k
-tuple total domination number of a connected
(
k
+
1
)
-regular graph with
n
vertices is at most
k
2
+
k
-
1
k
2
+
k
n
, unless it is the incident graph of a finite projective plane of order
k
, where this number is
k
2
+
k
k
2
+
k
+
1
n
. We also show that the
k
-tuple domination number of a connected
k
-regular graph with
n
vertices is at most
k
2
-
1
k
2
n
, unless it is a Moore graph of diameter 2, where this number is
k
2
k
2
+
1
n
.
We point out possible automorphisms of a distance-regular graph Γ with intersection array {55, 54, 2; 1, 1, 54} and spectrum 55
1
, 7
1617
,−1
110
,−8
1408
.
Mixed graphs of order n such that for any pair of vertices there is a unique trail of length at most k between them are known as mixed Moore graphs. These extremal graphs may only exist for diameter ...k=2 and certain (infinitely many) values of n. In this paper we give some properties of mixed Moore graphs of directed degree one and reduce their existence to the existence of some (undirected) strongly regular graphs.
Mixed almost Moore graphs appear in the context of the Degree/Diameter problem as a class of extremal mixed graphs, in the sense that their order is one less than the Moore bound for mixed graphs. ...The problem of their existence has been considered before for directed graphs and undirected ones, but not for the mixed case, which is a kind of generalization. In this paper we give some necessary conditions for the existence of mixed almost Moore graphs of diameter two derived from the factorization in $\mathbb{Q}x$ of their characteristic polynomial. In this context, we deal with the irreducibility of $\Phi_i(x^2+x-(r-1))$, where $\Phi_i(x)$ denotes the i-th cyclotomic polynomial.
Radial Moore graphs of radius three Exoo, Geoffrey; Gimbert, Joan; López, Nacho ...
Discrete Applied Mathematics,
July 2012, 2012-07-00, Letnik:
160, Številka:
10-11
Journal Article
Recenzirano
Odprti dostop
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.
Delsarte et al. (Geom Dedicata 6:363–388,
1977
) used the linear programming method in order to find bounds for the size of spherical codes endowed with prescribed inner products between distinct ...points in the code. In this paper, we develop the linear programming method to obtain bounds for the number of vertices of connected regular graphs endowed with given distinct eigenvalues. This method is proved by some “dual” technique of the spherical case, motivated from the theory of association scheme. As an application of this bound, we prove that a connected
k
-regular graph satisfying
g
>
2
d
-
1
has the minimum second-largest eigenvalue of all
k
-regular graphs of the same size, where
d
is the number of distinct non-trivial eigenvalues, and
g
is the girth. The known graphs satisfying
g
>
2
d
-
1
are Moore graphs, incidence graphs of regular generalized polygons of order (
s
,
s
), triangle-free strongly regular graphs, and the odd graph of degree 4.
The Degree/diameter problem asks for the largest graphs given diameter and maximum degree. This problem has been extensively studied both for directed and undirected graphs, ando also for special ...classes of graphs. In this work we present the state of art of the degree/diameter problem for mixed graphs.
PDF
