3
$\begingroup$

I have a Cayley graph $\mathrm{Cay}(G,S)$, its group presentation $G=\langle S | R \rangle$, and it becomes a metric graph by assigning a length equal to $1$ to each edge. I also have an induced subgraph of that Cayley graph. The distance between two vertices $u$ and $v$ in $\mathrm{Cay}(G,S)$ is the shortest path between them, which is equivalent to find the shortest word over the alphabet $S$ with the property that represents the product $g^{-1}h$, where $g$ and $h$ are group elements which represents $u$ and $v$, respectively.

My question is:

Is there any way to determine the distance between two vertices in the induced subgraph by using group theory?

I know that the distance between two vertices in the induced subgraphs can be equal or greater than the distance in the original graph, so I can’t use the word metric in the $\mathrm{Cay}(G,S)$ to determine the distance in the induced subgraph.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ If the subgraph is not given "by using group theory" I think is difficult to describe its metric "by using group theory". $\endgroup$
    – user126154
    Mar 31, 2014 at 9:14
  • $\begingroup$ Thanks. Is it possible that induced subgraph of cayley graphs are Schreier coset graph? $\endgroup$
    – Miguel C.
    Mar 31, 2014 at 9:42
  • 4
    $\begingroup$ Paley graphs are Cayley graphs, and contain all small grpahs as induced subgraphs. (Small means order $\log(n)$, iirc.) $\endgroup$
    – Chris Godsil
    Mar 31, 2014 at 12:00
  • $\begingroup$ Thanks for your answer. I'm trying to embed simple graphs into Cayley graphs. I’m following the ideas of L. Babai (Sidon set in group and induced subgraphs of Cayley graphs, 1985) and C. Godsil (Embedding graphs in Cayley Graphs,1987). Focusing the question in what I need, I would like to know if is it possible to ensure that the embedding of any graph into a Cayley graph to be an isometric embedding? Or at least a greedy embedding. $\endgroup$
    – Miguel C.
    Mar 31, 2014 at 13:28

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.