Orthogonal colourings of Cayley graphs Janssen, Jeannette; MacKeigan, Kyle
Discrete mathematics,
November 2020, 2020-11-00, Volume:
343, Issue:
11
Journal Article
Peer reviewed
Open access
Two colourings of a graph are orthogonal if they have the property that when two vertices are coloured with the same colour in one colouring, then those vertices receive distinct colours in the other ...colouring. In this paper, orthogonal colourings of Cayley graphs are discussed. Firstly, the orthogonal chromatic number of cycle graphs are completely determined. Secondly, the orthogonal chromatic number of certain circulant graphs is explored. Lastly, orthogonal colourings of product graphs and Hamming graphs are studied.
Let
Γ
=
(
V
,
E
)
be a (non-trivial) finite graph with
λ
:
E
→
R
+
an edge labeling of
Γ
. Let
ρ
:
V
→
R
2
be a map which preserves the edge labeling, i.e.,
‖
ρ
(
u
)
-
ρ
(
v
)
‖
2
=
λ
(
(
u
,
v
)
)
...,
∀
(
u
,
v
)
∈
E
,
where
‖
x
-
y
‖
2
denotes the Euclidean distance between two points
x
,
y
∈
R
2
. The labeled graph is said to be flexible if there exists an infinite number of such maps (up to equivalence by rigid transformations) and it is said to be movable if there exists an infinite number of injective maps (again up to equivalence by rigid transformations). We study movability of Cayley graphs and construct regular movable graphs of all degrees. Further, we give explicit constructions of dense, movable graphs.
A Neumaier graph is a non-complete edge-regular graph containing a regular clique. A Neumaier graph that is not strongly regular is called a strictly Neumaier graph. In this work we present a new ...construction of strictly Neumaier graphs, and using Jacobi sums, we show that our construction produces infinitely many instances. Moreover, we prove some necessary conditions for the existence of (strictly) Neumaier graphs that allow us to show that several parameter sets are not admissible.
Embedding cycles into a network topology is crucial for the network simulation. In particular, embedding Hamiltonian cycles is a major requirement for designing good interconnection networks. A graph ...G is called k-spanning cyclable if, for any k distinct vertices v1,v2,…,vk of G, there exist k cycles C1,C2,…,Ck in G such that vi is on Ci for every i, and every vertex of G is on exactly one cycle Ci. If k=1, this is the classical Hamiltonian problem. In this paper, we focus on embedding spanning disjoint cycles in Cayley graphs Γn generated by transposition trees and show that Γn is k-spanning cyclable if k≤n−2 and n≥3. Moreover, the result is optimal with respect to the degree of Γn.
We prove that the Cayley graphs X(G,S) and X+(G,S) are equienergetic for any abelian group G and any symmetric subset S. We then focus on the family of unitary Cayley graphs GR=X(R,R⁎), where R is a ...finite commutative ring with identity. We show that under mild conditions, {GR,GR+} are pairs of integral equienergetic non-isospectral graphs (generically connected and non-bipartite). Then, we obtain conditions such that {GR,G¯R} are equienergetic non-isospectral graphs. Finally, we characterize all integral equienergetic non-isospectral triples {GR,GR+,G¯R} such that all the graphs are also Ramanujan.
A Cayley graph for a group G is CCA if every automorphism of the graph that preserves the edge-orbits under the regular representation of G is an element of the normaliser of G. A group G is then ...said to be CCA if every connected Cayley graph on G is CCA. We show that a finite simple group is CCA if and only if it has no element of order 4. We also show that “many” 2-groups are non-CCA.
Recently, several works by a number of authors have studied integrality, distance integrality, and distance powers of Cayley graphs over some finite groups, such as dicyclic groups and (generalized) ...dihedral groups. Our aim is to generalize and/or to give analogues of these results for generalized dicyclic groups. For example, we give a necessary and sufficient condition for a Cayley graph over a generalized dicyclic group to be integral (i.e., all eigenvalues of its adjacency matrix are in Z). We also obtain sufficient conditions for the integrality of all distance powers of a Cayley graph over a given generalized dicyclic group. These results extend works on dicyclic groups by Cheng–Feng–Huang and Cheng–Feng–Liu–Lu–Stevanovic, respectively.
In this note, we introduce the notions of color-permutable automorphisms and color-permutable vertex-transitive Cayley graphs of semigroups. As a main result, for a finite monoid
S
and a generating ...set
C
of
S
, we explicitly determine the color-permutable automorphism group of
Cay
(
S
,
C
)
Theorem
1.1
. Also for a monoid
S
and a generating set
C
of
S
, we explicitly determine the color-preserving automorphism group (endomorphism monoid) of
Cay
(
S
,
C
)
Proposition
2.3
and Corollary
2.4
. Then we use these results to characterize when
Cay
(
S
,
C
)
is color-endomorphism vertex-transitive Theorem
3.4
.
PDF
