Talk:Vertex-transitive graph

it would be nice to have an example of a regular graph that is not vertex-transitive, however, I don't know any. Evilbu 20:43, 14 February 2006 (UTC)

This is precisely what I came here looking for!! there are semisymmetric examples at mathworld, but these are edge transitive. Should be able to find a non-vertex-transitive regular graph with fewer than 20 vertices!MotherFunctor

The (connected) counterexample with the least number of vertices is an order-7 quartic graph. Consider the graph consisting of a disjoint 3-cycle and 4-cycle. Its complement graph is the desired example. This graph is not planar, having crossing number 2. The smallest planar example is an order-8 cubic graph, so has fewer edges than the first one. I don't know how this stuff can be worked into the article, because it's original research. Ntsimp (talk) 21:36, 16 February 2008 (UTC)

Automorphism

Why is the automorphism written as V(G) --> V(G)? This seems as if it is just an automorphism (i.e. bijection) of the underlying vertex sets. It should be G --> G, right? ---oo- (talk) 09:14, 17 March 2016 (UTC)

A graph automorphism is defined to be a bijection from the vertex set to itself such that adjacency and non-adjacency are preserved. If it isn't a function acting on the vertex set, you can't write something like f(v). The notation G-->G doesn't make mathematical sense. I'm changing it back. McKay (talk) 07:47, 8 August 2024 (UTC)

What -oo- is talking about is: get your categories right. An arrow in the category of graphs is not the same thing as an arrow in Set. In both categories, we know what "automorphism" means, and there's a difference: In one case there is additional structure to preserve, in the other, there isn't. And when we use function application notation on an arrow in the category of graphs, it is clear that we mean application of the underlying function, i.e. there is an implicit application of the forgetful functor Graph --> Set. --Daniel5Ko (talk) 09:47, 8 August 2024 (UTC)

@Daniel5Ko: However, this isn't an article on category theory and your use of category notation will confuse the majority of readers, most of whom will not be familiar with it. There isn't a single mention of categories in the whole article. My version of the notation uses the basic $f:A\to B$ notation from naive set theory that everyone knows. It is standard in books on graph theory and also consistent with the notation at Isomorphism and Graph isomorphism. McKay (talk) 07:42, 29 August 2024 (UTC)

See Graph homomorphism. The notation $f\colon G\to H$ for a graph homomorphism from a graph $G$ to a graph $H$ is standard. Also, a graph homomorphism from $G$ to $H$ is in general not the same kind of thing as a graph homomorphism from $G'$ to $H$, even if $V(G)=V(G')$.

If we like to be very strict and pedantic, we might also say that such an $f\colon G\to H$ isn't really a function from $V(G)$ to $V(H)$, but consists of such a function, which we could project out with something we also call $V$, just to suggest that we might have a functor: $V(f)\colon V(G)\to V(H)$. Normally, this isn't done, but it might fall out naturally if we formalize the stuff in something like Lean:

-- We take "graph" to mean simple graph
structure Graph where
V: Type
E: V → V → Prop
symm: E x y → E y x
noloop: ¬ E x x

structure GraphHom(G H : Graph) where
V: G.V → H.V
E: G.E x y → H.E (V x) (V y)

example (f : GraphHom G H): G.V → H.V := f.V

-- We can make the extraction of the function out of a homomorphism implicit and automatic, if we like:
instance: CoeFun (GraphHom G H) (λ _ => G.V → H.V) where coe := GraphHom.V

-- Usage of the implicit coercion:
example (f : GraphHom G H): G.V → H.V := f

--Daniel5Ko (talk) 14:29, 29 August 2024 (UTC)

I've been publishing papers in graph theory for 49 years, but thank you for the definition of a graph. What Lean has to do with it, I don't know. To business: homomorphisms are one of several things that an arrow notation is used for in graph theory. It is also true that an isomorphism is a trivial example of a homomorphism, but the converse is not true. Even being bijective is not enough to ensure that a homomorphism is an isomorphism (exercise for the reader). So using homomorphism notation when only isomorphisms are under consideration can only serve to confuse the reader. Besides that, we are supposed to follow published sources and in all of the vast literature on automorphism groups of graphs I doubt if there is 1% which don't consider an automorphism to be a permutation of the vertex set. Not just to induce a permutation of the vertex set but to be a permutation of the vertex set. I looked at all the references on this page and none of them use the notation you want. So now I will use the definition in the first reference, which is simple, clear and standard. If you want to use a different definition, you'll need a different source (which had better not be a work on homomorphisms or categories) and get consensus to use it. McKay (talk) 05:28, 2 September 2024 (UTC)

By the power of using the right definitions (from category theory), if we know what the homomorphisms are, we also know what are the isomorphisms and the automorphisms (these are just special homomorphism, where in formulating the speciality, we don't need any graph theoretic notions, or any special notions that go beyond the vocabulary of an unknown category). Bijectivity can't be mentioned on this general way, because we don't assume that the arrows are functions. The definition you now wrote into the article is just an easy to prove theorem, if the general way is taken, and given we know what graph homomorphisms are. Writing $f\colon G\to H$ to mean that $f$ is a graph homomorphism from $G$ to $H$ is standard everywhere, and it doesn't preclude that we might be willing to talk about more special graph homomorphisms, as in "an automorphism $f:G\to G$ [bla]".

That pushed to the side, I appreciate that the contested notation is now gone thanks to your last edit. Daniel5Ko (talk) 20:19, 3 September 2024 (UTC)