A generalized polygon is an incidence structure that satisfies certain regularity axioms and their incidence graphs are known as Moore graphs. For any fixed non-negative integer values h and k, a ...L(h,k)-coloring is a vertex coloring in which the difference between any pair of vertices at distance one is at least h and the any pair of vertices at distance two has coloring numbers that differ by at least k. The L(h,k)-span is the difference between the maximum and minimum color number. The goal of this problem is to find the L(h,k)-coloring with the smallest span. We present three structures of the generalized 2n-gons for n=3 and n=4 and use them to obtain bounds of the L(h,k)-number of their incidence graphs.
The packing chromatic numberχρ(G) of a graph G is the smallest integer k for which there exists a vertex coloring Γ:V(G)→{1,2,…,k} such that any two vertices of color i are at distance at least i+1. ...For g∈{6,8,12}, (q+1,g)-Moore graphs are (q+1)-regular graphs with girth g which are the incidence graphs of a symmetric generalized g∕2-gons of order q. In this paper we study the packing chromatic number of a (q+1,g)-Moore graph G. For g=6 we present the exact value of χρ(G). For g=8, we determine χρ(G) in terms of the intersection of certain structures in generalized quadrangles. For g=12, we present lower and upper bounds for this invariant when q≥9 is an odd prime power.
A mixed graph is said to be dense, if its order is close to the Moore bound and it is optimal if there is not a mixed graph with the same parameters and bigger order. We give a construction that ...provides dense mixed graphs of undirected degree q, directed degree q−12 and order 2q2, for q being an odd prime power. Since the Moore bound for a mixed graph with these parameters is equal to 9q2−4q+34 the defect of these mixed graphs is (q−22)2−14. In particular we obtain a known mixed Moore graph of order 18, undirected degree 3 and directed degree 1, called Bosák's graph and a new mixed graph of order 50, undirected degree 5 and directed degree 2, which is proved to be optimal.
In this paper we give a lower bound for the discriminant of the polynomials {Gk,i(x)} defined by Gk,0(x)=1,Gk,1(x)=x+1 and Gk,i+2(x)=xGk,i+1(x)−(k−1)Gk,i(x)fori≥0. These polynomials are closely ...related to the Chebyshev polynomials of the second kind. We derive our result by using orthogonality properties of the polynomials {Fk,i(x)} defined by Fk,0(x)=1,Fk,1(x)=x,Fk,2(x)=x2−k and Fk,i+2(x)=xFk,i+1(x)−(k−1)Fk,i(x)fori≥1.
It has been an open question for 6 decades whether a Moore graph of diameter 2 and degree 57 exists. In this paper the question is posed as an optimization problem and an algorithm is described. The ...algorithm converges to solutions which are massively short of the number of edges required. This, and other supporting work, tend to suggest that the graph does not exist. The formulation presented is a particularly hard testbed for optimization algorithms. It is left as a challenge to others to develop alternative algorithms that may support the claim, or find solutions with more edges, or even construct the Moore graph.
We consider the localization number and metric dimension of certain graphs of diameter $2$, focusing on families of Kneser graphs and graphs without 4-cycles. For the Kneser graphs with a diameter of ...$2$, we find upper and lower bounds for the localization number and metric dimension, and in many cases these parameters differ only by an additive constant. Our results on the metric dimension of Kneser graphs improve on earlier ones, yielding exact values in infinitely many cases. We determine bounds on the localization number and metric dimension of Moore graphs of diameter $2$ and polarity graphs.
This is a survey on some known properties of the possible Moore graph (or graphs) ϒ with degree 57 and diameter 2. Moreover, we give some new results about it, such as the following. When we consider ...the distance partition of ϒ induced by a vertex subset C, the following graphs are distance-regular: The induced graph of the vertices at distance 1 from C when C is a set of 400 independent vertices; the induced graphs of the vertices at distance 2 from C when C is a vertex or an edge, and the line graph of ϒ. Besides, ϒ is an edge-distance-regular graph.
The interconnection network comprises a significant portion of the cost of large parallel computers, both in economic terms and power consumption. Several previous proposals exploit large-radix ...routers to build scalable low-distance topologies with the aim of minimizing these costs. However, they fail to consider potential unbalance in the network utilization, which in some cases results in suboptimal designs. Based on an appropriate cost model, this paper advocates the use of networks based on incidence graphs of projective planes, broadly denoted as Projective Networks. Projective Networks rely on generalized Moore graphs with uniform link utilization and encompass several proposed direct (PN and demi-PN) and indirect (OFT) topologies under a common mathematical framework. Compared to other proposals with average distance between 2 and 3 hops, these networks provide very high scalability while preserving a balanced network utilization, resulting in low network costs.
Mixed Cages Araujo-Pardo, Gabriela; Hernández-Cruz, César; Montellano-Ballesteros, Juan José
Graphs and combinatorics,
09/2019, Letnik:
35, Številka:
5
Journal Article
Recenzirano
We introduce the notion of a
z
,
r
;
g
-mixed cage. A
z
,
r
;
g
-mixed cage is a mixed graph
G
,
z
-regular by arcs,
r
-regular by edges, with girth
g
and minimum order. In this paper we prove ...the existence of
z
,
r
;
g
-mixed cages and exhibit families of mixed cages for some specific values. We also give lower and upper bounds for some choices of
z
,
r
and
g
. In particular we present the first results on
z
,
r
;
g
- mixed cages for
z
=
1
and any
r
≥
1
and
g
≥
3
, and for any
z
≥
1
,
r
=
1
and
g
=
4
.
Packing in regular graphs Henning, Michael A.; Klostermeyer, William F.
Quaestiones mathematicae,
07/2018, Letnik:
41, Številka:
5
Journal Article
Recenzirano
A set S of vertices in a graph G is a packing if the vertices in S are pairwise at distance at least 3 apart in G. The packing number of G, denoted by ρ(G), is the maximum cardinality of a packing in ...G. Favaron Discrete Math. 158 (1996), 287-293 showed that if G is a connected cubic graph of order n different from the Petersen graph, then ρ(G) ≥ n/8. In this paper, we generalize Favaron's result. We show that for k ≥ 3, if G is a connected k-regular graph of order n that is not a diameter-2 Moore graph, then ρ(G) ≥ n/(k
2
− 1).
PDF
