We express the discrete Ricci curvature of a graph as the minimal eigenvalue of a family of matrices, one for each vertex of a graph whose entries depend on the local adjacency structure of the ...graph. Using this method we compute or bound the Ricci curvature of Cayley graphs of finite Coxeter groups and affine Weyl groups. As an application we obtain an isoperimetric inequality that holds for all Cayley graphs of finite Coxeter groups.
We characterize colour-preserving automorphism vertex transitivity and vertex transitivity of the Cayley graphs of all semigroups in a class of pseudo-unitary homogeneous semigroups.
Towards a proof of the conjecture that only finitely many finite simple groups have no cubic graphical regular representation (GRR), this paper shows that PSL3(q) has a cubic GRR if and only if q≠2. ...Moreover, a cubic GRR of PSL3(q) is constructed for each of these q.
Super Rk-vertex-connectedness Hu, Xiaomin; Tian, Yingzhi; Meng, Jixiang
Applied mathematics and computation,
12/2018, Volume:
339
Journal Article
Peer reviewed
For a graph G=(V,E), a subset F ⊆ V(G) is called an Rk-vertex-cut of G if G−F is disconnected and each vertex u∈V(G)−F has at least k neighbours in G−F. The Rk-vertex-connectivity of G, denoted by ...κk(G), is the cardinality of a minimum Rk-vertex-cut of G. In this paper, we further study the Rk-vertex-connectivity by introducing the concept, called super Rk-vertex-connectedness. The graph G is called super Rk-vertex-connectedness if, for every minimum Rk-vertex-cut S, G−S contains a component which is isomorphic to a certain graph H, where H is related to the graph G and integer k. For the Cayley graphs generated by wheel graphs, H is isomorphic to K2 when k=1 and H is isomorphic to C4 when k=2. In this paper, we show that the Cayley graphs generated by wheel graphs are super R1-vertex-connectedness and super R2-vertex-connectedness. Our studies generalize the main result in 8.
Quadratic unitary Cayley graphs are a generalization of the well-known Paley graphs. Let Zn be the ring of integers modulo n. The quadratic unitary Cayley graph of Zn, denoted by GZn, is the graph ...whose vertices are given by the elements of Zn and two vertices u,v∈Zn are adjacent if and only if u−v or v−u is a quadratic unit in Zn. When p≥3 is a prime and ν≥1 is an integer, all the eigenvalues of GZpν have been given in 8. In this paper, we improve the above result and obtain all the exact eigenvalues of GZ2ν by a new approach. We also determine all the eigenvalues of GZn for general n>1. As an application, we characterize necessary and sufficient conditions on n such that GZn is strongly regular.