Let us define a symmetric cut of the graph as a cut which cuts the graph into two isomorphic graphs and that the cut preserves the isomorphism i.e. the edges that are cut only connect vertices that are images of each other under this isomorphism. I have a graph that has a property that given any two vertices there exists a symmetric cut that separates them. I would think this is a very restrictive property. One can assume that the graph is regular for simplicity. I know of a family of examples, d-dimensional cubes (their edge and vertex set, as a graph). Can we characterize the general solution to this condition?
7
-
1$\begingroup$ Some easy additions to your family are: even cycles, even-size complete graphs, Cartesian / tensor / strong products of members of the family (this includes the hypercubes). I don't know of a general characterization though. $\endgroup$– Jukka KohonenCommented Nov 13, 2023 at 16:18
-
1$\begingroup$ @JukkaKohonen I do not think complete graphs are such. The author says `'this isomorphism', perhaps meaning that the isomorphism is fixed, not that you consider the family of all isomorphisms between the parts... $\endgroup$– Ilya BogdanovCommented Nov 14, 2023 at 7:53
-
$\begingroup$ Obviously, the graph is not only regular but vertex-transitive (if connected) $\endgroup$– Ilya BogdanovCommented Nov 14, 2023 at 7:54
-
$\begingroup$ For the reason Ilya stated, I don't think the class is closed under strong or tensor product. However, it seems to be closed under cartesian product. So we have the cartesian product of any number of single edges and even length cycles, not necessarily of the same length. I'm wondering if there can be any others. $\endgroup$– Brendan McKayCommented Nov 14, 2023 at 8:53
-
$\begingroup$ Right, I think I was reading something wrong about the cut edges :) But yes, single edges, even cycles and cartesian products. $\endgroup$– Jukka KohonenCommented Nov 14, 2023 at 9:48
|
Show 2 more comments