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.
On Cayley graphs of Baburin, Igor A.
Acta crystallographica. Section A, Foundations and advances,
September 2020, Letnik:
76, Številka:
5
Journal Article
Recenzirano
Odprti dostop
The generating sets of have been enumerated which consist of integral four‐dimensional vectors with components −1, 0, 1 and allow Cayley graphs without edge intersections in a straight‐edge embedding ...in a four‐dimensional Euclidean space. Owing to computational restrictions the valency of enumerated graphs has been fixed to 10. Up to isomorphism 58 graphs have been found and characterized by coordination sequences, shortest cycles and automorphism groups. To compute automorphism groups, a novel strategy is introduced that is based on determining vertex stabilizers from the automorphism group of a sufficiently large finite ball cut out from an infinite graph. Six exceptional, rather `dense' graphs have been identified which are locally isomorphic to a five‐dimensional cubic lattice within a ball of radius 10. They could be built by either interconnecting interpenetrated three‐ or four‐dimensional cubic lattices and therefore necessarily contain Hopf links between quadrangular cycles. As a consequence, a local combinatorial isomorphism does not extend to a local isotopy.
Cayley graphs of with valency 10 have been enumerated which correspond to generating sets of integral vectors with components −1, 0, 1 and which are embedded in a four‐dimensional Euclidean space without edge intersections.
Partial cubes are graphs isometrically embeddable into hypercubes. In this article, it is proved that every cubic, vertex‐transitive partial cube is isomorphic to one of the following graphs: K2□C2n, ...for n≥2, the generalized Petersen graph G(10, 3), the cubic permutahedron, the truncated cuboctahedron, or the truncated icosidodecahedron. This classification is a generalization of results of Brešar et al. (Eur J Combin 25 (2004), 55–64) on cubic mirror graphs; it includes all cubic, distance‐regular partial cubes (P. M. Weichsel, Discrete Math 109 (1992), 297–306), and presents a contribution to the classification of all cubic partial cubes.
The k-dimensional Weisfeiler-Leman algorithm (k-WL) is a very useful combinatorial tool in graph isomorphism testing. We address the applicability of k-WL to recognition of graph properties. Let G be ...an input graph with n vertices. We show that, if n is prime, then vertex-transitivity of G can be seen in a straightforward way from the output of 2-WL on G and on the vertex-individualized copies of G. This is perhaps the first non-trivial example of using the Weisfeiler-Leman algorithm for recognition of a natural graph property rather than for isomorphism testing. On the other hand, we show that, if n is divisible by 16, then k-WL is unable to distinguish between vertex-transitive and non-vertex-transitive graphs with n vertices unless k=Ω(n). Similar results are obtained for recognition of arc-transitivity. Our lower bounds are based on an analysis of the Cai-Fürer-Immerman construction, which might be of independent interest. In particular, we provide sufficient conditions under which the Cai-Fürer-Immerman graphs can be made colorless.
•The Weisfeiler-Leman algorithm is used to recognize vertex-transitivity of graphs with a prime number of vertices•This is perhaps the first example of using it for recognition of a natural graph property rather than for isomorphism testing•This is no longer possible if the number of vertices is divisible by 16•The negative result is based on an analysis of the Cai-Fürer-Immerman construction•This analysis might be of independent interest as it provides a very straight way of making the CFI graphs colorless
For a connected graph G, let κ′(G) be the edge-connectivity of G. The ℓ-edge-connectivityκℓ′(G) of G with order n≥ℓ is the minimum number of edges that are required to be deleted from G to produce a ...graph with at least ℓ components. It has been observed that while both κ′(G) and κℓ′(G) are related edge connectivity measures. In general, κℓ′(G) cannot be upper bounded by a function of κ′(G). Let κ¯′(G)=max{κ′(H):H⊆G} be the maximum subgraph edge-connectivity of G. We prove that for integers k′,k and ℓ with k′≥k≥1 and ℓ≥2, each of the following holds.
(i) sup{κℓ′(G):κ′(G)=k,κ¯′(G)=k′}=k+(ℓ−2)k′.
(ii) inf{κℓ′(G):κ′(G)=k,κ¯′(G)=k′}=kℓ2.
In interconnection networks, matching preclusion is a measure of robustness in the event of link failure. Let G be a graph of even order. The matching preclusion number mp(G) is defined as the ...minimum number of edges whose deletion results in a graph without perfect matchings. Many interconnection networks are super matched, that is, their optimal matching preclusion sets are precisely those induced by a single vertex. In this paper, we obtain general results of vertex-transitive graphs including many known networks. A k-regular connected vertex-transitive graph of even order has matching preclusion number k and is super matched except for six classes of graphs. From this many results already known can be directly obtained and matching preclusion for some other networks, such as folded k-cube graphs, Hamming graphs and halved k-cube graphs, are derived.
PDF
