Skip to main content
Title
Source Link
LSpice
  • 12.9k
  • 4
  • 45
  • 69

The Necessary and sufficient conditions for the Cayley graph isto be bipartite if and only if

Let $G$ be a finite group with identity $1$. If $S$ be an inverse closed generated subset of $G$, then $S$ is called a Cayley subset of $G$.The Cayley graph $\Gamma=Cay(G, S)$$\Gamma=\operatorname{Cay}(G, S)$ is a simple undirected connected graph whose vertex set $V\Gamma=G$ and edge set $E\Gamma=\left\{\{g, h\} \mid g^{-1} h \in S \right\} .$$E\Gamma=\left\{\{g, h\} \mid g^{-1} h \in S \right\}$. It is well known $\Gamma$ is a vertex transitive graph.

A bipartite graph is defined as a graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex from one set to a vertex in the other set. Equivalently, a graph $ G = (V, E)$ is bipartite if and only if it does not contain any odd-length cycles.

I want to know under what conditions the Cayley graph is bipartite. Of course, the conclusion is simple when $G$ is a cyclic group, but what about when $G$ is aan abelian group, or even a non-abelian one? Are there any conclusions?

The Cayley graph is bipartite if and only if

Let $G$ be a finite group with identity $1$. If $S$ be an inverse closed generated subset of $G$, then $S$ is called a Cayley subset of $G$.The Cayley graph $\Gamma=Cay(G, S)$ is a simple undirected connected graph whose vertex set $V\Gamma=G$ and edge set $E\Gamma=\left\{\{g, h\} \mid g^{-1} h \in S \right\} .$ It is well known $\Gamma$ is a vertex transitive graph.

A bipartite graph is defined as a graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex from one set to a vertex in the other set. Equivalently, a graph $ G = (V, E)$ is bipartite if and only if it does not contain any odd-length cycles.

I want to know under what conditions the Cayley graph is bipartite. Of course, the conclusion is simple when $G$ is a cyclic group, but what about when $G$ is a abelian group, or even a non-abelian one? Are there any conclusions?

Necessary and sufficient conditions for the Cayley graph to be bipartite

Let $G$ be a finite group with identity $1$. If $S$ be an inverse closed generated subset of $G$, then $S$ is called a Cayley subset of $G$.The Cayley graph $\Gamma=\operatorname{Cay}(G, S)$ is a simple undirected connected graph whose vertex set $V\Gamma=G$ and edge set $E\Gamma=\left\{\{g, h\} \mid g^{-1} h \in S \right\}$. It is well known $\Gamma$ is a vertex transitive graph.

A bipartite graph is defined as a graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex from one set to a vertex in the other set. Equivalently, a graph $ G = (V, E)$ is bipartite if and only if it does not contain any odd-length cycles.

I want to know under what conditions the Cayley graph is bipartite. Of course, the conclusion is simple when $G$ is a cyclic group, but what about when $G$ is an abelian group, or even a non-abelian one? Are there any conclusions?

edited tags
Link
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40
Became Hot Network Question
Source Link
Loading