Results 151 to 160 of about 472 (183)
Some of the next articles are maybe not open access.
Embedding graphs in Cayley graphs
Graphs and Combinatorics, 1987Over ten years ago Babai showed that for any graph Y and for any sufficiently large group G, there is a Cayley graph X of G such that Y is an induced subgraph of X. The bounds given by him for \(| G|\) have been recently reduced by Babai and Sós to approximately \(9.5| Y|^ 3\).
Chris D. Godsil, Wilfried Imrich
openaire +2 more sources
1991
This paper demonstrates the power of the Cayley graph approach to solve specific applications, such as rearrangement problems and the design of interconnection networks for parallel CPU's. Recent results of the authors for efficient use of Cayley graphs are used here in exploratory analysis to extend recent results of Babai et al.
Gene Cooperman +2 more
openaire +1 more source
This paper demonstrates the power of the Cayley graph approach to solve specific applications, such as rearrangement problems and the design of interconnection networks for parallel CPU's. Recent results of the authors for efficient use of Cayley graphs are used here in exploratory analysis to extend recent results of Babai et al.
Gene Cooperman +2 more
openaire +1 more source
2000
Given a class C of Cayley graphs, and given an edge-colored graph G of n vertices and m edges, we are interested in the problem of checking whether there exists an isomorphism Φ preserving the colors such that G is isomorphic by Φ to a graph in C colored by the elements of its generating set. In this paper, we give an O(m log n)-time algorithm to check
Lali Barrière +4 more
openaire +1 more source
Given a class C of Cayley graphs, and given an edge-colored graph G of n vertices and m edges, we are interested in the problem of checking whether there exists an isomorphism Φ preserving the colors such that G is isomorphic by Φ to a graph in C colored by the elements of its generating set. In this paper, we give an O(m log n)-time algorithm to check
Lali Barrière +4 more
openaire +1 more source
On undirected Cayley graphs [PDF]
Australas. J Comb., 2002 Summary: We determine all periodic (and, therefore, all finite) semigroups \(G\) for which there exists a non-empty subset \(S\) such that the Cayley graph of \(G\) relative to \(S\) is an undirected Cayley graph.
openaire +1 more source
An Isoperimetric Problem in Cayley Graphs
Theory of Computing Systems, 1999A graph \(\Gamma\) is said to be \(k\)-separable if there is a subset \(X\) of \(V\) such that \(|X|\geq k\) and \(|\delta X|\geq k\). If \(\Gamma\) is \(k\)-separable, the \(k\)-isoperimetric number of \(\Gamma\) is \(\kappa_k(\Gamma)= \min\{|\delta X|:|X|\geq k\) and \(|\delta X|\geq k\}\).
Yahya Ould Hamidoune +2 more
openaire +1 more source
Cayley Graph Automatic Groups Are Not Necessarily Cayley Graph Biautomatic
2012We show that there are Cayley graph automatic groups that are not Cayley graph biautomatic. In addition, we show that there are Cayley graph automatic groups with undecidable Conjugacy Problem and that the Isomorphism Problem is undecidable in the class of Cayley graph automatic groups.
Alexei Miasnikov, Zoran Sunic
openaire +1 more source
When is the cayley graph of a semigroup isomorphic to the cayley graph of a group
Mathematica Slovaca, 2017Abstract 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.
openaire +1 more source
On non-Cayley vertex-transitive graphs and the meta-Cayley graphs
Quaestiones Mathematicae, 2011The pursuit to identify vertex-transitive non-Cayley graphs has been deliberate for some time now. In that vein, Alspach and Parsons [1] introduced metacirculant graphs. They are de ned on two cyclic groups with adjacency re-sembling twisting that is typically used in de ning semi-direct products of groups.
openaire +2 more sources
2020
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.
openaire +1 more source
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.
openaire +1 more source
Parallel sorting on cayley graphs
Algorithmica, 1991zbMATH Open Web Interface contents unavailable due to conflicting licenses.
openaire +1 more source