Skip to main content
added 8 characters in body
Source Link

Let $G$ be a simple (finite) graph. Consider the next natural equivalence relation $\sim$ on $V(G)$:

$u\sim v$ iff there exists and automorphism $\phi\in Aut(G)$, such that $\phi(u)=v$.

Define a new graph $G_{Aut}$ with $V(G_{Aut})=G/{\sim}$ and there exists an edge $A-B$, for $A,B\in G/{\sim}$ iff there exists $a\in A$ and $b\in B$, such that $ab\in E(G)$.

Note, that if $G$ has trivial automorphism group, then $G_{Aut}\simeq G$. Similarly, if $G$ is vertex-transitive, then $G_{Aut}\simeq K_{1}$.

I have two questions

Question 1:$\cdot$ Does for every $G$ there exists $H$ such that $H_{Aut}\simeq G\ ?$ (I think the answer is YES)

Question 2:$\cdot$ If so, how many vertices $H$ must have?

Let $G$ be a simple (finite) graph. Consider the next natural equivalence relation $\sim$ on $V(G)$:

$u\sim v$ iff there exists and automorphism $\phi\in Aut(G)$, such that $\phi(u)=v$.

Define a new graph $G_{Aut}$ with $V(G_{Aut})=G/{\sim}$ and there exists an edge $A-B$, for $A,B\in G/{\sim}$ iff there exists $a\in A$ and $b\in B$, such that $ab\in E(G)$.

Note, that if $G$ has trivial automorphism group, then $G_{Aut}\simeq G$. Similarly, if $G$ is vertex-transitive, then $G_{Aut}\simeq K_{1}$.

Question 1: Does for every $G$ there exists $H$ such that $H_{Aut}\simeq G\ ?$ (I think the answer is YES)

Question 2: If so, how many vertices $H$ must have?

Let $G$ be a simple (finite) graph. Consider the next natural equivalence relation $\sim$ on $V(G)$:

$u\sim v$ iff there exists and automorphism $\phi\in Aut(G)$, such that $\phi(u)=v$.

Define a new graph $G_{Aut}$ with $V(G_{Aut})=G/{\sim}$ and there exists an edge $A-B$, for $A,B\in G/{\sim}$ iff there exists $a\in A$ and $b\in B$, such that $ab\in E(G)$.

Note, that if $G$ has trivial automorphism group, then $G_{Aut}\simeq G$. Similarly, if $G$ is vertex-transitive, then $G_{Aut}\simeq K_{1}$.

I have two questions

$\cdot$ Does for every $G$ there exists $H$ such that $H_{Aut}\simeq G\ ?$ (I think the answer is YES)

$\cdot$ If so, how many vertices $H$ must have?

added 24 characters in body; edited tags
Source Link

Let $G$ be a simple (finite) graph. Consider the next natural equivalence relation $\sim$ on $V(G)$:

$u\sim v$ iff there exists and automorphism $\phi\in Aut(G)$, such that $\phi(u)=v$.

Define a new graph $G_{Aut}$ with $V(G_{Aut})=G/{\sim}$ and there exists an edge $A-B$, for $A,B\in G/{\sim}$ iff there exists $a\in A$ and $b\in B$, such that $ab\in E(G)$.

Note, that if $G$ has trivial automorphism group, then $G_{Aut}\simeq G$. Similarly, if $G$ is vertex-transitive, then $G_{Aut}\simeq K_{1}$.

Question 1: Does for every $G$ there exists $H$ with $H_{Aut}\simeq G\ ?$ (I think the answer is YES)

Question 2: If so, how many vertices $H$ must have?

Question 1: Does for every $G$ there exists $H$ such that $H_{Aut}\simeq G\ ?$ (I think the answer is YES)

Question 2: If so, how many vertices $H$ must have?

Let $G$ be a simple graph. Consider the natural equivalence relation $\sim$ on $V(G)$:

$u\sim v$ iff there exists and automorphism $\phi\in Aut(G)$, such that $\phi(u)=v$.

Define a new graph $G_{Aut}$ with $V(G_{Aut})=G/{\sim}$ and there exists an edge $A-B$, for $A,B\in G/{\sim}$ iff there exists $a\in A$ and $b\in B$, such that $ab\in E(G)$.

Note, that if $G$ has trivial automorphism group, then $G_{Aut}\simeq G$. Similarly, if $G$ is vertex-transitive, then $G_{Aut}\simeq K_{1}$.

Question 1: Does for every $G$ there exists $H$ with $H_{Aut}\simeq G\ ?$ (I think the answer is YES)

Question 2: If so, how many vertices $H$ must have?

Let $G$ be a simple (finite) graph. Consider the next natural equivalence relation $\sim$ on $V(G)$:

$u\sim v$ iff there exists and automorphism $\phi\in Aut(G)$, such that $\phi(u)=v$.

Define a new graph $G_{Aut}$ with $V(G_{Aut})=G/{\sim}$ and there exists an edge $A-B$, for $A,B\in G/{\sim}$ iff there exists $a\in A$ and $b\in B$, such that $ab\in E(G)$.

Note, that if $G$ has trivial automorphism group, then $G_{Aut}\simeq G$. Similarly, if $G$ is vertex-transitive, then $G_{Aut}\simeq K_{1}$.

Question 1: Does for every $G$ there exists $H$ such that $H_{Aut}\simeq G\ ?$ (I think the answer is YES)

Question 2: If so, how many vertices $H$ must have?

Source Link

Automorphism group action leads to a "quotient graph"

Let $G$ be a simple graph. Consider the natural equivalence relation $\sim$ on $V(G)$:

$u\sim v$ iff there exists and automorphism $\phi\in Aut(G)$, such that $\phi(u)=v$.

Define a new graph $G_{Aut}$ with $V(G_{Aut})=G/{\sim}$ and there exists an edge $A-B$, for $A,B\in G/{\sim}$ iff there exists $a\in A$ and $b\in B$, such that $ab\in E(G)$.

Note, that if $G$ has trivial automorphism group, then $G_{Aut}\simeq G$. Similarly, if $G$ is vertex-transitive, then $G_{Aut}\simeq K_{1}$.

Question 1: Does for every $G$ there exists $H$ with $H_{Aut}\simeq G\ ?$ (I think the answer is YES)

Question 2: If so, how many vertices $H$ must have?