3
votes
2answers
60 views

Subcategory generated by a graph

I was wondering whether there was a notion of subcategory generated by a "part" of a fixed category $\mathcal{C}$. My thoughts started from the well known concept of the substructure generated by a ...
0
votes
2answers
51 views

Restriction on Graph Automorphism

This question referes to a definition in Eugene M. Luks paper "Isomorphism of Graphs of Bounded Valence Can Be Tested in Polynomial Time" (1981), page 48, available at ...
1
vote
2answers
532 views

Variations : Anti-Symmetric Relations on an $n$-Element Set : Graph Theoretic Elucidation

Question: How many antisymmetric relations are there on an $n$-element set? Guess: I suspect that there are $2^n$ such relations. Discussion: I'm told that anti-symmetric relations on a ...
0
votes
1answer
169 views

Prove that the group of automorphisms of a labelled Cayley graph of a group G is the group G itself (Just stumped on one direction)

I feel like for this question it is just a matter of showing the mapping in both directions, from the group to the graph and the graph to the group. So for the mapping from the group to the graph, I ...
4
votes
1answer
200 views

Graphs with a unique $3$-path free acyclic orientation up to isomorphism.

Let $\Gamma$ be a simple, $3$-colorable graph such that, up to isomorphism, there exists exactly one acyclic orientation of $\Gamma$ that does not contain a directed 3-path. (To be clear, when I say ...
3
votes
1answer
92 views

Condition for a vertex-transitive graph to be symmetric

I am reading "Algebraic Graph Theory" by Biggs 1974. In the section about symmetric graphs, it is stated that: A vertex transitive graph $X$ is symmetric, if and only if each vertex-stabilizer ...