Let $R$ be a commutative ring with the non-zero identity and $n$ be a natural number. $\Gamma ^n_R$ is a simple graph with $R^n \setminus \{0\}$ as the vertex set and two distinct vertices $X$ and ...$Y$ in $R^{n}$ are adjacent if and only if there exists an $n \times n$ lower triangular matrix $A$ over $R$ whose entries on the main diagonal are non-zero such that $AX^{t}=Y^{t}$ or $AY^{t}=X^{t}$, where, for a matrix $B$, $B^{t}$ is the matrix transpose of $B$. $\Gamma ^n_R$ is a generalization of Cayley graph. Let $T_n (R)$ denote the $n \times n$ upper triangular matrix ring over $R$. In this paper, for an arbitrary ring $R$, we investigate the properties of the graph $\Gamma ^n_{T_n(R)}$. KCI Citation Count: 1
There is presented an infinite class of subgroups of the modular group
PSL
(
2
,
Z
)
that serve as Cayley representations of the distant graph of the projective line of integers. They are infinite ...countable free products of subgroups of
PSL
(
2
,
Z
)
isomorphic with
Z
2
,
Z
3
and
Z
subject to the restriction that the number of copies of
Z
is 0 or 2. The proof technique is based on a 1–1 correspondence between some involutions
ι
of
Z
that fulfill the equation
ι
(
ι
(
n
)
-
δ
n
)
=
ι
(
n
+
1
)
+
δ
n
+
1
,
δ
n
=
±
1
,
δ
ι
(
n
)
=
δ
n
,
and groups from this class.
Cayley graphs provide a group-theoretic model for designing and analyzing symmetric interconnection networks. In this paper, we give a sufficient condition for the existence of m vertex-disjoint ...shortest paths from one source vertex to other m (not necessarily distinct) destination vertices in a Cayley graph of an abelian group, where m≤n and n is the cardinality of a (group) generator of the abelian group. In addition, when the condition holds, the m vertex-disjoint shortest paths can be constructed in O(mn) time, which is optimal in the worst case when O(n) ≤ the order of diameter. By applying our results, we can easily obtain the necessary and sufficient conditions, which can be verified in nearly optimal time, for the existence of all shortest vertex-disjoint paths in generalized hypercubes and odd tori. In the situation that all of the source vertex and destination vertices are mutually distinct, brute-force computations show that the probability of the existence of the m vertex-disjoint shortest paths in an r-dimensional generalized hypercube with r coordinates each of order k is greater than 94%, 70%, 96%, 99%, and 99% for (k,r,m)=(2,7,7),(3,4,8),(4,3,6),(5,3,6), and (6,3,6), respectively.
Renteln proved that the eigenvalues of the distance matrix of a Cayley graph of a real reflection group with respect to the set of all reflections are integral and provided a combinatorial formula ...for some such spectra. We prove the eigenvalues of the distance, adjacency, and codimension matrices of Cayley graphs of complex reflection groups with connection sets consisting of all reflections are integral and provide a combinatorial formula for the codimension spectra for a family of monomial complex reflection groups.
Let 𝑅 be a finite commutative ring. In this paper, we find the number of representations of a fixed member of 𝑅 to be the sum of 𝑘 units in 𝑅, and the sum of 𝑘 non-units, and as a sum of a unit ...and a non-unit. We prove that, if ℤ₂ is not a quotient of 𝑅, then every 𝑟 ∈ 𝑅 can be written as a sum of 𝑘 units, for each integer 𝑘 > 1.
We investigate the relationship between geometric, analytic and probabilistic indices for quotients of the Cayley graph of the free group ${\rm Cay}(F_n)$ by an arbitrary subgroup $G$ of $F_n$. Our ...main result, which generalizes Grigorchuk's cogrowth formula to variable edge lengths, provides a formula relating the bottom of the spectrum of weighted Laplacian on $G \backslash {\rm Cay}(F_n)$ to the Poincaré exponent of $G$. Our main tool is the Patterson–Sullivan theory for Cayley graphs with variable edge lengths.
We define a group
G
to be
graphically abelian if the function
g
↦
g
−
1
induces an automorphism of every Cayley graph of
G
. We give equivalent characterizations of graphically abelian groups, note ...features of the adjacency matrices for Cayley graphs of graphically abelian groups, and show that a non-abelian group
G
is graphically abelian if and only if
G
=
E
×
Q
, where
E
is an elementary abelian 2-group and
Q
is a quaternion group.
PDF
