Symmetric Graph

SYMMETRIC GRAPHS: Two points u and v of the graph G are similar if for some automorphism α of G, α(u) = v. A fixed point is not similar to any other point. Two lines x1 = u1v1 and x2 = u2v2 are called similar if there is an automorphism α of G such that α({u1, v1}) = {u2, u2}. A graph is point-symmetric of every pair of points are similar, it is line-symmetric if every pair of lines are similar, and it is symmetric if it is both point-symmetric and line-symmetric.

HIGHLY SYMMETRIC GRAPHS: A graph G is n-transitive, n ≥ 1, if it has an n-route and if there is always an automorphism of G sending each n-route onto any other n-route. Obviously a cycle of any length is n-transitive for all n, and a path of length n is n-transitive. We note that not every line-symmetric graph is 1-transitive.

Theorem. The line-group and the point-group of a graph G are isomorphism if and only if G has atmost one isolated point and K2 is not a component of G.
Proof. Let α′ be the permutation in Γ1(G) which is induced by the permutation α in Γ(G). By the definition of multiplication in Γ1(G), we have

α′β′ = (αβ)′ for all α, β in Γ(G).

Thus the mapping α → α′ is a group homomorphism from Γ(G) onto Γ1(G). Hence Γ(G) ≅ Γ1(G) if and only if the kernel of this mapping is trivial. To prove the necessity, assume Γ(G) ≅ Γ1(G).
Then α ≠ i (the identity permutation) implies α′ ≠ i.
If G has distinct isolated points v1 and v2, we can define α ∈ Γ(G) by α(v1) = v2, α(v2) = v1 and α(v) = v for all v ≠ v1, v2. Then α ≠ i but α′ = i.
If K2 is a component of G, take the line of K2 to be x = v1v2 and define α ∈ Γ(G) exactly as above to obtain α ≠ i but α′ = i.
To prove the sufficiency, assume that G has at most one isolated point and that K2 is not a component of G.
If Γ(G) is trivial, then obviously Γ1(G) fixes every line and hence Γ1(G) is trivial.
Therefore, suppose there exists α ∈ Γ(G) with α(u) = v ≠ u.
Then the degree of u is equal to the degree of v. Since u and v are not isolated, this degree is not zero.

Case (i). u is adjacent to v. Let x = uv. Since K2 is not a component, the degrees of both u and v are greater than one. Hence there is a line y ≠ x which is incident with u and α′(y) is incident with v. Therefore α′(y) ≠ y and so α′ ≠ i.
Case (ii). u is not adjacent to v. Let x be any line incident with u. Then α′(x) ≠ x and so α′ ≠ i.