Page 334 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 334
SYMMETRY OF GRAPHS, MAPS AND POLYTOPES (MS-9)
On rainbow domination in regular and symmetric graphs
Boštjan Kuzman, bostjan.kuzman@pef.uni-lj.si
University of Ljubljana, Slovenia
The k-rainbow domination function of a graph is a function that assigns a subset of {1, 2, . . . , k}
to each vertex of a graph, such that each non-colored vertex has a complete k-rainbow of neigh-
bours, that is, f (v) = ∅ implies ∪u∼vf (u) = {1, . . . , k}. The k-rainbow domination number
γrk(G) of a graph is the minimal possible value of weight w(f ) = |f (v)| over all k-rainbow
domination funtions f on G.
Recently, we have shown that the k-rainbow domination number γrk(G) of a d-regular graph
for d ≤ k ≤ 2d is bounded below by kn/2d , where n is the order of a graph, and determined
some necessary conditions for regular graphs to attain this bound. This enabled us to find
simpler proofs of some known results on kRD-number for specific graph families and determine
exact kRD-numbers for all cubic Cayley graphs over abelian groups, as well as opened several
questions on finding k-rainbow-domination-regular graphs that will be presented in a talk.
Cyclotomic Association Schemes of Broad Classes and Applications to the
Construction of Combinatorial Structures
Luis Martínez, luis.martinez@ehu.eus
University of the Basque Country, Spain
Coauthors: Maria Asunción García, Leire Legarreta, Iker Malaina
In 2010, G. Fernández, R. Kwashira and L. Martínez gave a new cyclotomy on A = n Fqi ,
i=1
where Fqi is a finite field with qi elements. They defined a certain subgroup H of the group of
units of this product ring A for which the quotient is cyclic. The orbits of the corresponding
multiplicative action of the subgroup on the additive group of A are of two types:
• The cyclotomic cosets of the quotient of the group of units of A over the subgroup H.
• The n-tuples with arbitrary non-zero elements in positions indicated by a proper subset S
of {1, . . . , n} and zeroes elsewhere.
In this talk, we introduce and study a fusion of a class of asociation schemes derived from the
mentioned cyclotomy. The association schemes that we are proposing correspond with a fusion
of orbits associated to subsets S of {1, . . . , n} of the same cardinality. We call cyclotomic
association schemes of broad classes to these association schemes. The fusion corresponds to
the operation of adding the permutations of A induced by the permutations of the symmetric
group Sn to the transitive permutation group that determines the original association scheme.
We use these association schemes to obtain sporadic examples and infinite families of dif-
ference sets and partial difference sets.
332
On rainbow domination in regular and symmetric graphs
Boštjan Kuzman, bostjan.kuzman@pef.uni-lj.si
University of Ljubljana, Slovenia
The k-rainbow domination function of a graph is a function that assigns a subset of {1, 2, . . . , k}
to each vertex of a graph, such that each non-colored vertex has a complete k-rainbow of neigh-
bours, that is, f (v) = ∅ implies ∪u∼vf (u) = {1, . . . , k}. The k-rainbow domination number
γrk(G) of a graph is the minimal possible value of weight w(f ) = |f (v)| over all k-rainbow
domination funtions f on G.
Recently, we have shown that the k-rainbow domination number γrk(G) of a d-regular graph
for d ≤ k ≤ 2d is bounded below by kn/2d , where n is the order of a graph, and determined
some necessary conditions for regular graphs to attain this bound. This enabled us to find
simpler proofs of some known results on kRD-number for specific graph families and determine
exact kRD-numbers for all cubic Cayley graphs over abelian groups, as well as opened several
questions on finding k-rainbow-domination-regular graphs that will be presented in a talk.
Cyclotomic Association Schemes of Broad Classes and Applications to the
Construction of Combinatorial Structures
Luis Martínez, luis.martinez@ehu.eus
University of the Basque Country, Spain
Coauthors: Maria Asunción García, Leire Legarreta, Iker Malaina
In 2010, G. Fernández, R. Kwashira and L. Martínez gave a new cyclotomy on A = n Fqi ,
i=1
where Fqi is a finite field with qi elements. They defined a certain subgroup H of the group of
units of this product ring A for which the quotient is cyclic. The orbits of the corresponding
multiplicative action of the subgroup on the additive group of A are of two types:
• The cyclotomic cosets of the quotient of the group of units of A over the subgroup H.
• The n-tuples with arbitrary non-zero elements in positions indicated by a proper subset S
of {1, . . . , n} and zeroes elsewhere.
In this talk, we introduce and study a fusion of a class of asociation schemes derived from the
mentioned cyclotomy. The association schemes that we are proposing correspond with a fusion
of orbits associated to subsets S of {1, . . . , n} of the same cardinality. We call cyclotomic
association schemes of broad classes to these association schemes. The fusion corresponds to
the operation of adding the permutations of A induced by the permutations of the symmetric
group Sn to the transitive permutation group that determines the original association scheme.
We use these association schemes to obtain sporadic examples and infinite families of dif-
ference sets and partial difference sets.
332
