Return to Question

To clarify, I'm speaking of homeomorphisms in a graph theoretic context, defined by subdivisions of arcs in a directed graph. A subdivision of an arc $(x,z)$ in a directed graph is obtained by removing $(x,z)$ from the arc-set and adding both $(x,y)$ and $(y,z)$. This is the definition in [BJG2009; page 10]; intuitively, we add a vertex $y$ different from all existing vertices in the "middle" of our arrow, and then give it an arrow-"head" that is pointed in the same direction as the other "head":

Also given any directed graph $G=(V,E)$ when I say an automorphism of $G$ what I am referring to is those permutations in a subgroup $\text{Aut}(G)\subseteq \text{Sym}(V)$ that is given as follows:

           $\text{Aut}(G)=\left\{\sigma\in \text{Sym}(V):\forall x,y\in V\left[(x,y)\in E\iff (\sigma(x),\sigma(y))\in E\right]\right\}$

With that said, after observing different ways in which automorphisms of digraphs permute certain subgraphs I've noticed a number of relationships between homeomorphisms and automorphisms, for instance if $G$ is a finite^(*) directed acyclic graph, then all of the orbits of the action $\text{Aut}(R)$ on the vertex-set $V$ must be anti-chains of the poset $(V,E^{*})$ where the kleene star $*$ in the exponent of $E$ denotes its transitive/reflexive closure. Further from here if we call a vertex $v\in V$ "thin" iff we have $\text{deg}^{+}(v)=\text{deg}^{-}(v)=1$ while also referring to any path $P\subseteq G$ as a "thin path" iff every non source/sink vertex of $P$ is a thin vertex in $G$, then every automorphism of $G$ can be described exactly by which maximal thin paths of like length it permutes in $G$. I.e., for each $\ell\in\omega$, there is a permutation action of $\mathrm{Aut}(G)$ on the set $\mathsf{Thin}_\ell(G)$ of all thin directed length-$\ell$-paths in $G$. Where from here if we subdivide a single arrow in each of the maximal thin paths of some fixed length in $G$ it seems the order of the newly formed automorphism group is the same order as $\text{Aut}(G)$, in fact I'm pretty sure not only is this true but so are a number of other identities similar to this, for example here are two other propositions I'm confident to state (though I haven't formally proved them):

1. Any finite^(**) digraph is homeomorphic to a digraph which has a trivial automorphism group.
2. Two directed acyclic graphs are isomorphic to each other iff their barycentric subdivisions are isomorphic. Or more generally iff $\forall n\in \mathbb{N}$ their $n^{\text{th}}$ barycentric subdivisions are isomorphic.

With that in mind, are there other propositions of this kind that relate the automorphism groups of homeomorphic digraphs with one another, or equivalently, relate their isomorphism classes? Also if anyone could point me to some writings that make such connections, that would be helpful as well.

${}$_______________________________________________________________________________

^(*)The following statement is obviously false for infinite digraphs.

^(**)Without assuming finiteness, this is false: the two-way infinite directed path (i.e., the digraph $(\mathbb{Z},<)$) has the property that any subdivision still has the same, and hence nontrivial, automorphism group.

[BJG2009] Jørgen Bang-Jensen, Gregory Gutin, Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics, Second Edition, 2009, ISBN-13: 978-0857290410

${}$_______________________________________________________________________________

Update: Identities $1$ and $2$ as well as the comments about the order of $\text{Aut}(R)$ that I previously alluded to are in fact true for any finite directed graph. Irregardless though, I am still looking for reading material and or similar identities/formula that may shed additional light on the connections between homeomorphy and isomorphy for directed graphs.

To clarify, I'm speaking of homeomorphisms in a graph theoretic context, defined by subdivisions of arcs in a directed graph. A subdivision of an arc $(x,z)$ in a directed graph is obtained by removing $(x,z)$ from the arc-set and adding both $(x,y)$ and $(y,z)$. This is the definition in [BJG2009; page 10]; intuitively, we add a vertex $y$ different from all existing vertices in the "middle" of our arrow, and then give it an arrow-"head" that is pointed in the same direction as the other "head". While given any directed graph $G=(V,E)$ when I say an automorphism of $G$ what I am referring to is those permutations in a subgroup $\text{Aut}(G)\subseteq \text{Sym}(V)$ that is given as follows:

           $\text{Aut}(G)=\left\{\sigma\in \text{Sym}(V):\forall x,y\in V\left[(x,y)\in E\iff (\sigma(x),\sigma(y))\in E\right]\right\}$

With that said, after observing different ways in which automorphisms of digraphs permute certain subgraphs I've noticed a number of relationships between homeomorphisms and automorphisms, for instance if $G$ is a finite^(*) directed acyclic graph, then all of the orbits of the action $\text{Aut}(R)$ on the vertex-set $V$ must be anti-chains of the poset $(V,E^{*})$ where the kleene star $*$ in the exponent of $E$ denotes its transitive/reflexive closure. Further from here if we call a vertex $v\in V$ "thin" iff we have $\text{deg}^{+}(v)=\text{deg}^{-}(v)=1$ while also referring to any path $P\subseteq G$ as a "thin path" iff every non source/sink vertex of $P$ is a thin vertex in $G$, then every automorphism of $G$ can be described exactly by which maximal thin paths of like length it permutes in $G$. I.e., for each $\ell\in\omega$, there is a permutation action of $\mathrm{Aut}(G)$ on the set $\mathsf{Thin}_\ell(G)$ of all thin directed length-$\ell$-paths in $G$. Where from here if we subdivide a single arrow in each of the maximal thin paths of some fixed length in $G$ it seems the order of the newly formed automorphism group is the same order as $\text{Aut}(G)$, in fact I'm pretty sure not only is this true but so are a number of other identities similar to this, for example here are two other propositions I'm confident to state (though I haven't formally proved):

1. Any finite^(**) digraph is homeomorphic to a digraph which has a trivial automorphism group.
2. Two directed acyclic graphs are isomorphic to each other iff their barycentric subdivisions are isomorphic. Or more generally iff $\forall n\in \mathbb{N}$ their $n^{\text{th}}$ barycentric subdivisions are isomorphic.

With that in mind, are there other propositions of this kind that relate the automorphism groups of homeomorphic digraphs with one another, or equivalently, relate their isomorphism classes? Also if anyone could point me to some writings that make such connections, that would be helpful as well.

${}$_______________________________________________________________________________

^(*)The following statement is obviously false for infinite digraphs.

^(**)Without assuming finiteness, this is false: the two-way infinite directed path (i.e., the digraph $(\mathbb{Z},<)$) has the property that any subdivision still has the same, and hence nontrivial, automorphism group.

[BJG2009] Jørgen Bang-Jensen, Gregory Gutin, Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics, Second Edition, 2009, ISBN-13: 978-0857290410

${}$_______________________________________________________________________________

Update: Identities $1$ and $2$ as well as the comments about the order of $\text{Aut}(R)$ that I previously alluded to are in fact true for any finite directed graph. Irregardless though, I am still looking for reading material and or similar identities/formula that may shed additional light on the connections between homeomorphy and isomorphy for directed graphs.

To clarify, I'm speaking of homeomorphisms in a graph theoretic context, defined by subdivisions of arcs in a directed graph. A subdivision of an arc $(x,z)$ in a directed graph is obtained by removing $(x,z)$ from the arc-set and adding both $(x,y)$ and $(y,z)$. This is the definition in [BJG2009; page 10]; intuitively, we add a vertex $y$ different from all existing vertices in the "middle" of our arrow, and then give it an arrow-"head" that is pointed in the same direction as the other "head":

Also given any directed graph $G=(V,E)$ when I say an automorphism of $G$ what I am referring to is those permutations in a subgroup $\text{Aut}(G)\subseteq \text{Sym}(V)$ that is given as follows:

           $\text{Aut}(G)=\left\{\sigma\in \text{Sym}(V):\forall x,y\in V\left[(x,y)\in E\iff (\sigma(x),\sigma(y))\in E\right]\right\}$

With that said, after observing different ways in which automorphisms of digraphs permute certain subgraphs I've noticed a number of relationships between homeomorphisms and automorphisms, for instance if $G$ is a finite^(*) directed acyclic graph, then all of the orbits of the action $\text{Aut}(R)$ on the vertex-set $V$ must be anti-chains of the poset $(V,E^{*})$ where the kleene star $*$ in the exponent of $E$ denotes its transitive/reflexive closure. Further from here if we call a vertex $v\in V$ "thin" iff we have $\text{deg}^{+}(v)=\text{deg}^{-}(v)=1$ while also referring to any path $P\subseteq G$ as a "thin path" iff every non source/sink vertex of $P$ is a thin vertex in $G$, then every automorphism of $G$ can be described exactly by which maximal thin paths of like length it permutes in $G$. I.e., for each $\ell\in\omega$, there is a permutation action of $\mathrm{Aut}(G)$ on the set $\mathsf{Thin}_\ell(G)$ of all thin directed length-$\ell$-paths in $G$. Where from here if we subdivide a single arrow in each of the maximal thin paths of some fixed length in $G$ it seems the order of the newly formed automorphism group is the same order as $\text{Aut}(G)$, in fact I'm pretty sure not only is this true but so are a number of other identities similar to this, for example here are two other propositions I'm confident to state (though I haven't formally proved them):

1. Any finite^(**) digraph is homeomorphic to a digraph which has a trivial automorphism group.
2. Two directed acyclic graphs are isomorphic to each other iff their barycentric subdivisions are isomorphic. Or more generally iff $\forall n\in \mathbb{N}$ their $n^{\text{th}}$ barycentric subdivisions are isomorphic.

With that in mind, are there other propositions of this kind that relate the automorphism groups of homeomorphic digraphs with one another, or equivalently, relate their isomorphism classes? Also if anyone could point me to some writings that make such connections, that would be helpful as well.

${}$_______________________________________________________________________________

^(*)The following statement is obviously false for infinite digraphs.

^(**)Without assuming finiteness, this is false: the two-way infinite directed path (i.e., the digraph $(\mathbb{Z},<)$) has the property that any subdivision still has the same, and hence nontrivial, automorphism group.

[BJG2009] Jørgen Bang-Jensen, Gregory Gutin, Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics, Second Edition, 2009, ISBN-13: 978-0857290410

${}$_______________________________________________________________________________

Update: Identities $1$ and $2$ as well as the comments about the order of $\text{Aut}(R)$ that I previously alluded to are in fact true for any directed graph. Irregardless though, I am still looking for reading material and or similar identities/formula that may shed additional light on the connections between homeomorphy and isomorphy for directed graphs.

To clarify, I'm speaking of homeomorphisms in a graph theoretic context, defined by subdivisions of arcs in a directed graph. A subdivision of an arc $(x,z)$ in a directed graph is obtained by removing $(x,z)$ from the arc-set and adding both $(x,y)$ and $(y,z)$. This is the definition in [BJG2009; page 10]; intuitively, we add a vertex $y$ different from all existing vertices in the "middle" of our arrow, and then give it an arrow-"head" that is pointed in the same direction as the other "head":

Also given any directed graph $G=(V,E)$ when I say an automorphism of $G$ what I am referring to is those permutations in a subgroup $\text{Aut}(G)\subseteq \text{Sym}(V)$ that is given as follows:

           $\text{Aut}(G)=\left\{\sigma\in \text{Sym}(V):\forall x,y\in V\left[(x,y)\in E\iff (\sigma(x),\sigma(y))\in E\right]\right\}$

With that said, after observing different ways in which automorphisms of digraphs permute certain subgraphs I've noticed a number of relationships between homeomorphisms and automorphisms, for instance if $G$ is a finite^(*) directed acyclic graph, then all of the orbits of the action $\text{Aut}(R)$ on the vertex-set $V$ must be anti-chains of the poset $(V,E^{*})$ where the kleene star $*$ in the exponent of $E$ denotes its transitive/reflexive closure. Further from here if we call a vertex $v\in V$ "thin" iff we have $\text{deg}^{+}(v)=\text{deg}^{-}(v)=1$ while also referring to any path $P\subseteq G$ as a "thin path" iff every non source/sink vertex of $P$ is a thin vertex in $G$, then every automorphism of $G$ can be described exactly by which maximal thin paths of like length it permutes in $G$. I.e., for each $\ell\in\omega$, there is a permutation action of $\mathrm{Aut}(G)$ on the set $\mathsf{Thin}_\ell(G)$ of all thin directed length-$\ell$-paths in $G$. Where from here if we subdivide a single arrow in each of the maximal thin paths of some fixed length in $G$ it seems the order of the newly formed automorphism group is the same order as $\text{Aut}(G)$, in fact I'm pretty sure not only is this true but so are a number of other identities similar to this, for example here are two other propositions I'm confident to state (though I haven't formally proved them):

1. Any finite^(**) digraph is homeomorphic to a digraph which has a trivial automorphism group.
2. Two directed acyclic graphs are isomorphic to each other iff their barycentric subdivisions are isomorphic. Or more generally iff $\forall n\in \mathbb{N}$ their $n^{\text{th}}$ barycentric subdivisions are isomorphic.

With that in mind, are there other propositions of this kind that relate the automorphism groups of homeomorphic digraphs with one another, or equivalently, relate their isomorphism classes? Also if anyone could point me to some writings that make such connections, that would be helpful as well.

${}$_______________________________________________________________________________

^(*)The following statement is obviously false for infinite digraphs.

^(**)Without assuming finiteness, this is false: the two-way infinite directed path (i.e., the digraph $(\mathbb{Z},<)$) has the property that any subdivision still has the same, and hence nontrivial, automorphism group.

[BJG2009] Jørgen Bang-Jensen, Gregory Gutin, Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics, Second Edition, 2009, ISBN-13: 978-0857290410

${}$_______________________________________________________________________________

Update: Identities $1$ and $2$ as well as the comments about the order of $\text{Aut}(R)$ that I previously alluded to are in fact true for any finite directed graph. Irregardless though, I am still looking for reading material and or similar identities/formula that may shed additional light on the connections between homeomorphy and isomorphy for directed graphs.

To clarify, I'm speaking of homeomorphisms in a graph theoretic context, defined by subdivisions of arcs in a directed graph. A subdivision of an arc $(x,z)$ in a directed graph is obtained by removing $(x,z)$ from the arc-set and adding both $(x,y)$ and $(y,z)$. This is the definition in [BJG2009; page 10]; intuitively, we add a vertex $y$ different from all existing vertices in the "middle" of our arrow, and then give it an arrow-"head" that is pointed in the same direction as the other "head":

Now, while studying the automorphism groups of digraphs. Namely if $G=(V,E)$ is our digraph,

$\text{Aut}(G)=\{\sigma\in \text{Sym}(V):\ \forall x,y\in V \qquad (x,y)\in E\iff (\sigma(x),\sigma(y))\in E\ \}$.

Ive noticed a number of relationships between homeomorphisms and automorphisms, for instance if $G$ is a finite^(*) directed acyclic graph, then all orbits of the action $\text{Aut}(R)$ on the vertex-set $V$ are anti-chains of the poset on $V$ given by $\leq:=E^{+}$, where ${}^+$ denotes transitive closure of a relation. Also, if we call a vertex $v\in V$ "thin" iff $\text{deg}^{+}(v)=\text{deg}^{-}(v)=1$ while also referring to any path $P\subseteq G$ as a "thin path" iff every vertex of $P$ is a thin vertex in $G$, then every automorphism of $G$ permutes the maximal thin paths of like length in $G$. I.e., for each $\ell\in\omega$, there is a permutation action of $\mathrm{Aut}(G)$ on the set $\mathsf{Thin}_\ell(G)$ of all thin directed length-$\ell$-paths in $G$. Now from here if we subdivide a single arrow in each of the maximal thin paths of some fixed length in $G$ it seems the order of the newly formed automorphism group is the same order as $\text{Aut}(G)$, in fact I'm pretty sure not only is this true but so are a number of other possible identities similar to this, for example here are two other propositions I'm confident to state (though I haven't formally proved them):

1. Any finite^(**) digraph is homeomorphic to a digraph which has a trivial automorphism group.
2. Two directed acyclic graphs are isomorphic to each other iff their barycentric subdivisions are isomorphic. Or more generally iff $\forall n\in \mathbb{N}$ their $n^{\text{th}}$ barycentric subdivisions are isomorphic.

With that in mind, are there other propositions of this kind that relate the automorphism groups of homeomorphic digraphs with one another, or equivalently, relate their isomorphism classes? Also if anyone could point me to some writings that make such connections, that would be helpful as well.

${}$_______________________________________________________________________________

^(*)The following statement is obviously false for infinite digraphs.

^(**)Without assuming finiteness, this is false: the two-way infinite directed path (i.e., the digraph $(\mathbb{Z},<)$) has the property that any subdivision still has the same, and hence nontrivial, automorphism group.

[BJG2009] Jørgen Bang-Jensen, Gregory Gutin, Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics, Second Edition, 2009, ISBN-13: 978-0857290410

To clarify, I'm speaking of homeomorphisms in a graph theoretic context, defined by subdivisions of arcs in a directed graph. A subdivision of an arc $(x,z)$ in a directed graph is obtained by removing $(x,z)$ from the arc-set and adding both $(x,y)$ and $(y,z)$. This is the definition in [BJG2009; page 10]; intuitively, we add a vertex $y$ different from all existing vertices in the "middle" of our arrow, and then give it an arrow-"head" that is pointed in the same direction as the other "head":

Also given any directed graph $G=(V,E)$ when I say an automorphism of $G$ what I am referring to is those permutations in a subgroup $\text{Aut}(G)\subseteq \text{Sym}(V)$ that is given as follows:

           $\text{Aut}(G)=\left\{\sigma\in \text{Sym}(V):\forall x,y\in V\left[(x,y)\in E\iff (\sigma(x),\sigma(y))\in E\right]\right\}$

With that said, after observing different ways in which automorphisms of digraphs permute certain subgraphs I've noticed a number of relationships between homeomorphisms and automorphisms, for instance if $G$ is a finite^(*) directed acyclic graph, then all of the orbits of the action $\text{Aut}(R)$ on the vertex-set $V$ must be anti-chains of the poset $(V,E^{*})$ where the kleene star $*$ in the exponent of $E$ denotes its transitive/reflexive closure. Further from here if we call a vertex $v\in V$ "thin" iff we have $\text{deg}^{+}(v)=\text{deg}^{-}(v)=1$ while also referring to any path $P\subseteq G$ as a "thin path" iff every non source/sink vertex of $P$ is a thin vertex in $G$, then every automorphism of $G$ can be described exactly by which maximal thin paths of like length it permutes in $G$. I.e., for each $\ell\in\omega$, there is a permutation action of $\mathrm{Aut}(G)$ on the set $\mathsf{Thin}_\ell(G)$ of all thin directed length-$\ell$-paths in $G$. Where from here if we subdivide a single arrow in each of the maximal thin paths of some fixed length in $G$ it seems the order of the newly formed automorphism group is the same order as $\text{Aut}(G)$, in fact I'm pretty sure not only is this true but so are a number of other identities similar to this, for example here are two other propositions I'm confident to state (though I haven't formally proved them):

1. Any finite^(**) digraph is homeomorphic to a digraph which has a trivial automorphism group.
2. Two directed acyclic graphs are isomorphic to each other iff their barycentric subdivisions are isomorphic. Or more generally iff $\forall n\in \mathbb{N}$ their $n^{\text{th}}$ barycentric subdivisions are isomorphic.

With that in mind, are there other propositions of this kind that relate the automorphism groups of homeomorphic digraphs with one another, or equivalently, relate their isomorphism classes? Also if anyone could point me to some writings that make such connections, that would be helpful as well.

${}$_______________________________________________________________________________

^(*)The following statement is obviously false for infinite digraphs.

^(**)Without assuming finiteness, this is false: the two-way infinite directed path (i.e., the digraph $(\mathbb{Z},<)$) has the property that any subdivision still has the same, and hence nontrivial, automorphism group.

[BJG2009] Jørgen Bang-Jensen, Gregory Gutin, Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics, Second Edition, 2009, ISBN-13: 978-0857290410

${}$_______________________________________________________________________________

Update: Identities $1$ and $2$ as well as the comments about the order of $\text{Aut}(R)$ that I previously alluded to are in fact true for any directed graph. Irregardless though, I am still looking for reading material and or similar identities/formula that may shed additional light on the connections between homeomorphy and isomorphy for directed graphs.