An edge coloring of a simple graph G is said to be proper rainbow-cycle-forbidding (PRCF, for short) if no two incident edges receive the same color and for any cycle in G, at least two edges of that ...cycle receive the same color. A graph G is defined to be PRCF-good if it admits a PRCF edge coloring, and G is deemed PRCF-bad otherwise. In recent work, Hoffman, et al. study PRCF edge colorings and find many examples of PRCF-bad graphs having girth less than or equal to 4. They then ask whether such graphs exist having girth greater than 4. In our work, we give a straightforward counting argument showing that the Hoffman-Singleton graph answers this question in the affirmative for the case of girth 5. It is then shown that certain generalized polygons, constructed of sufficiently large order, are also PRCF-bad, thus proving the existence of PRCF-bad graphs of girth 6, 8, 12, and 16.
A directed strongly regular graph with parameters (n,k,t,λ,μ) is a k-regular directed graph with n vertices satisfying that the number of walks of length 2 from a vertex x to a vertex y is t if x=y, ...λ if there is an edge directed from x to y and μ otherwise. If λ=0 and μ=1 then we say that it is a mixed Moore graph. It is known that there are unique mixed Moore graphs with parameters (k2+k,k,1,0,1), k≥2, and (18,4,3,0,1). We construct a new mixed Moore graph with parameters (108,10,3,0,1) and also new directed strongly regular graphs with parameters (36,10,5,2,3) and (96,13,5,0,2). This new graph on 108 vertices can also be seen as an example of a so called multipartite Moore digraph. Finally we consider the possibility that mixed Moore graphs with other parameters could exist, in particular the first open case which is (40,6,3,0,1).
Graphs and digraphs with maximum order allowed by its degree and diameter have been widely studied in the context of the Degree/Diameter problem. This problem turns out to be very interesting in the ...mixed case, where many open problems arise, specially when the diameter is two and the order of the graph achieves the largest theoretical value given by the mixed Moore bound. These extremal graphs are known as mixed Moore graphs. In this paper we construct by voltage assignment some infinite families of mixed graphs of diameter two and order approaching the Moore bound. One of these families, in particular, yields most of the known mixed Moore graphs. We also present other families which are the result of the first known extension of the paradigmatic McKay-Miller-Širáň construction (McKay et al., 1998).
We give simple arithmetic conditions that force the Sylow p-subgroup of the critical group of a strongly regular graph to take a specific form. These conditions depend only on the parameters ...(v,k,λ,μ) of the strongly regular graph under consideration. We give many examples, including how the theory can be used to compute the critical group of Conway's 99-graph and to give an elementary argument that no srg(28,9,0,4) exists.
Mixed graphs with maximum number of vertices regarding to a given maximum degree and given diameter are known as mixed Moore graphs. In this paper we model the problem of the existence of mixed Moore ...graphs of diameter 2 through the Boolean satisfiability problem. As a consequence, we prove the non existence of mixed Moore graphs of order 40, 54 and 84.
Let ρ(G) denote the number of convex cycles of a simple graph G of order n, size m, and girth 3≤g≤n. It is proved that ρ(G)≤ng(m−n+1) 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.
A Note on Moore Cayley Digraphs Gavrilyuk, Alexander L.; Hirasaka, Mitsugu; Kabanov, Vladislav
Graphs and combinatorics,
09/2021, Letnik:
37, Številka:
5
Journal Article
Recenzirano
Let
Δ
be a digraph of diameter 2 with the maximum undirected vertex degree
t
and the maximum directed out-degree
z
. The largest possible number
v
of vertices of
Δ
is given by the following ...generalization of the Moore bound:
v
≤
(
z
+
t
)
2
+
z
+
1
,
and a digraph attaining this bound is called a Moore digraph. Apart from the case
t
=
1
, only three Moore digraphs are known, which are also Cayley graphs. Using computer search, Erskine (J Interconnect Netw, 17: 1741010, 2017) ruled out the existence of further examples of Cayley digraphs attaining the Moore bound for all orders up to 485. We use an algebraic approach to this problem, which goes back to an idea of G. Higman from the theory of association schemes, also known as Benson’s Lemma in finite geometry, and show non-existence of Moore Cayley digraphs of certain orders.
The cage problem asks for the smallest number c(k,g) of vertices in a k-regular graph of girth g and graphs meeting this bound are known as cages. While cages are known to exist for all integers k⩾2 ...and g⩾3, the exact value of c(k,g) is known only for some small values of k,g and three infinite families where g∈{6,8,12} and k−1 is a prime power. These infinite families come from the incidence graphs of generalized polygons. Some of the best known upper bounds on c(k,g) for g∈{6,8,12} have been obtained by constructing small regular induced subgraphs of these cages.
In this paper, we first use the Expander Mixing Lemma to give a general lower bound on the size of an induced k-regular subgraph of a regular bipartite graph in terms of the second largest eigenvalue of the host graph. We use this bound to show that the known construction of (k,6)-graphs using Baer subplanes of the Desarguesian projective plane is the best possible. For generalized quadrangles and hexagons, our bounds are new. In particular, we improve the known lower bound on the size of an induced q-regular subgraph of the classical generalized quadrangle Q(4,q) and show that the known constructions are asymptotically sharp, which answers a question of Metsch 21, Section 6.
For prime powers q, we also improve the known upper bounds on c(q,8) and c(q,12) by giving new geometric constructions of q-regular induced subgraphs in the symplectic generalized quadrangle W(3,q) and the split Cayley hexagon H(q), respectively. Our constructions show thatc(q,8)⩽2(q3−qq−q) for q an even power of a prime, andc(q,12)⩽2(q5−3q3) for all prime powers q. For q∈{3,4,5} we also give a computer classification of all q-regular induced subgraphs of the classical generalized quadrangles of order q. For W(3,7) we classify all 7-regular induced subgraphs which have a non-trivial automorphism.
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
.
PDF
