Catalogue Search | MBRL
Are you sure you want to remove the book from the shelf?
{{itemTitle}}
266
result(s) for
"Cayley graphs."
Sort by:
Expander families and Cayley graphs : a beginner's guide
\"The theory of expander graphs is a rapidly developing topic in mathematics and computer science, with applications to communication networks, error-correcting codes, cryptography, complexity theory, and much more. Expander Families and Cayley Graphs: A Beginner's Guide is a comprehensive introduction to expander graphs, designed to act as a bridge between classroom study and active research in the field of expanders. It equips those with little or no prior knowledge with the skills necessary to both comprehend current research articles and begin their own research. Central to this book are four invariants that measure the quality of a Cayley graph as a communications network-the isoperimetric constant, the second-largest eigenvalue, the diameter, and the Kazhdan constant. The book poses and answers three core questions: How do these invariants relate to one another? How do they relate to subgroups and quotients? What are their optimal values/growth rates? Chapters cover topics such as: ℗ʺ Graph spectra ℗ʺ A Cheeger-Buser-type inequality for regular graphs ℗ʺ Group quotients and graph coverings ℗ʺ Subgroups and Schreier generators ℗ʺ Ramanujan graphs and the Alon-Boppana theorem ℗ʺ The zig-zag product and its relation to semidirect products of groups ℗ʺ Representation theory and eigenvalues of Cayley graphs ℗ʺ Kazhdan constants The only introductory text on this topic suitable for both undergraduate and graduate students, Expander Families and Cayley Graphs requires only one course in linear algebra and one in group theory. No background in graph theory or representation theory is assumed. Examples and practice problems with varying complexity are included, along with detailed notes on research articles that have appeared in the literature. Many chapters end with suggested research topics that are ideal for student projects\"-- Provided by publisher.
Book
Graphs Defined on Rings: A Review
The study on graphs emerging from different algebraic structures such as groups, rings, fields, vector spaces, etc. is a prominent area of research in mathematics, as algebra and graph theory are two mathematical fields that focus on creating and analysing structures. There are numerous studies linking algebraic structures and graphs, which began with the introduction of Cayley graphs of groups. Several algebraic graphs have been defined on rings, a fast-growing area in the literature. In this article, we systematically review the literature on some variants of Cayley graphs that are defined on rings and highlight the properties and characteristics of such graphs, to showcase the research in this area.
Journal Article
The Planar Cubic Cayley Graphs
We obtain a complete description of the planar cubic Cayley graphs, providing an explicit presentation and embedding for each of
them. This turns out to be a rich class, comprising several infinite families. We obtain counterexamples to conjectures of Mohar,
Bonnington and Watkins. Our analysis makes the involved graphs accessible to computation, corroborating a conjecture of Droms.
eBook
On transitive Cayley graphs of homogeneous inverse semigroups
Let
S
be a pseudo-unitary homogeneous (graded) inverse semigroup with zero 0, that is, an inverse semigroup with zero, and with a family
{
S
δ
}
δ
∈
Δ
of nonzero subsets of
S
, called components of
S
, indexed by a partial groupoid
Δ
, that is, by a set with a partial binary operation, such that
S
=
⋃
δ
∈
Δ
S
δ
, and: i)
S
ξ
∩
S
η
⊆
{
0
}
for all distinct
ξ
,
η
∈
Δ
;
ii)
S
ξ
S
η
⊆
S
ξ
η
whenever
ξ
η
is defined; iii)
S
ξ
S
η
⊈
{
0
}
if and only if the product
ξ
η
is defined; iv) for every idempotent element
ϵ
∈
Δ
, the subsemigroup
S
ϵ
is with identity
1
ϵ
;
v) for every
x
∈
S
there exist idempotent elements
ξ
,
η
∈
Δ
such that
1
ξ
x
=
x
=
x
1
η
;
vi)
1
ξ
1
η
=
1
ξ
η
whenever
ξ
η
∈
Δ
is an idempotent element, where
ξ
,
η
are idempotent elements of
Δ
. Let
A
be a subset of the union of the subsemigroup components of
S
, which does not contain 0. By
Cay
(
S
∗
,
A
)
we denote a graph obtained from the Cayley graph
Cay
(
S
,
A
)
by removing 0 and its incident edges. We characterize vertex-transitivity of
Cay
(
S
∗
,
A
)
and relate it to the vertex-transitivity of its subgraph whose vertex set is
S
μ
\\
{
0
}
, where
μ
is the maximum element of the set of all idempotent elements of
Δ
, with respect to the natural order.
Journal Article
Total chromatic number for some classes of Cayley graphs
In this paper, we have obtained the total chromatic number for some classes of Cayley graphs, particularly the Unitary Cayley graphs on even order and some other Circulant graphs. We have also proved the Total Coloring Conjecture for some perfect Cayley graphs.
Journal Article
On Some Properties of Signed Cayley Graph Sn
We define the signed Cayley graph on Cayley graph Xn denoted by Sn, and study several properties such as balancing, clusterability and sign-compatibility of the signed Cayley graph Sn. Apart from it we also study the characterization of the canonical consistency of Sn, for some n.
Journal Article
Perfect state transfer on quasi-abelian semi-Cayley graphs
Perfect state transfer on graphs has attracted extensive attention due to its application in quantum information and quantum computation. A graph is a semi-Cayley graph over a group
G
if it admits
G
as a semiregular subgroup of the full automorphism group with two orbits of equal size. A semi-Cayley graph
SC
(
G
,
R
,
L
,
S
) is called quasi-abelian if each of
R
,
L
and
S
is a union of some conjugacy classes of
G
. This paper establishes necessary and sufficient conditions for a quasi-abelian semi-Cayley graph to have perfect state transfer. As a corollary, it is shown that if a quasi-abelian semi-Cayley graph over a finite group
G
has perfect state transfer between distinct vertices
g
and
h
, and
G
has a faithful irreducible character, then
g
h
-
1
lies in the center of
G
and
g
h
=
h
g
; in particular,
G
cannot be a non-abelian simple group. We also characterize quasi-abelian Cayley graphs over arbitrary groups having perfect state transfer, which is a generalization of previous works on Cayley graphs over abelian groups, dihedral groups, semi-dihedral groups and dicyclic groups.
Journal Article
Certain Structural Properties for the Direct Product of Cayley Graphs and Their Theoretical Applications
Symmetry properties are of vital importance for graphs. The famous Cayley graph is a good mathematical model as its high symmetry. The normality of the graph can well reflect the symmetry of the graph. In this paper, we characterize the normality of the direct product of Cayley graphs and give a sufficient and necessary condition for the direct product of two graphs to be a Cayley graph. Moreover, a sufficient and necessary condition for judging the normality of the direct product of two graphs is given.
Journal Article
On Automorphisms and Structural Properties of Generalized Cayley Graphs
In this paper, generalized Cayley graphs are studied. It is proved that every generalized Cayley graph of order two times a prime is a Cayley graph. Special attention is given to generalized Cayley graphs on abelian groups. It is proved that every generalized Cayley graph on an abelian group with respect to an automorphism which acts as inversion is a Cayley graph if and only if the group is elementary abelian 2-group, or its Sylow 2-subgroup is cyclic. Necessary and sufficient conditions for a generalized Cayley graph to be unworthy are given.
Journal Article
When is the cayley graph of a semigroup isomorphic to the cayley graph of a group
It is well known that Cayley graphs of groups are automatically vertex-transitive. A pioneer result of Kelarev and Praeger implies that Cayley graphs of semigroups can be regarded as a source of possibly new vertex-transitive graphs. In this note, we consider the following problem: Is every vertex-transitive Cayley graph of a semigroup isomorphic to a Cayley graph of a group? With the help of the results of Kelarev and Praeger, we show that the vertex-transitive, connected and undirected finite Cayley graphs of semigroups are isomorphic to Cayley graphs of groups, and all finite vertex-transitive Cayley graphs of inverse semigroups are isomorphic to Cayley graphs of groups. Furthermore, some related problems are proposed.
Journal Article