Abstract | ||
---|---|---|
An automorphism σ of a finite simple graph Γ is an adjacency automorphism if for every vertex x ∈ V(Γ), either σx = x or σx is adjacent to x in Γ. An adjacency automorphism fixing no vertices is a shift. A connected graph Γ is strongly adjacency-transitive (respectively, uniquely shift-transitive) if there is, for every pair of adjacent vertices x, y ∈ V(Γ), an adjacency automorphism (respectively, a unique shift) σ ∈ Aut Γ sending x to y. The action graph Γ = ActGrph(G,X,S) of a group G acting on a set X, relative to an inverse-closed nonempty subset S ⊆ G, is defined as follows: the vertex-set of Γ is X, and two different vertices x,y ∈ V(Γ) are adjacent in Γ if and only if y=sx for some s ∈ S. A characterization of strongly adjacency-transitive graphs in terms of action graphs is given. A necessary and sufficient condition for cartesian products of graphs to be uniquely shift-transitive is proposed, and two questions concerning uniquely shift-transitive graphs are raised. |
Year | DOI | Venue |
---|---|---|
2002 | 10.1016/S0012-365X(01)00096-6 | Discrete Mathematics |
Keywords | Field | DocType |
connected graph,vertex transitive graph | Graph theory,Adjacency list,Discrete mathematics,Combinatorics,Two-graph,Vertex-transitive graph,Vertex (geometry),Automorphism,Cartesian product,Cayley graph,Mathematics | Journal |
Volume | Issue | ISSN |
244 | 1-3 | 0012-365X |
Citations | PageRank | References |
3 | 0.44 | 10 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tomaz Pisanski | 1 | 82 | 19.67 |
Thomas W. Tucker | 2 | 191 | 130.07 |
Boris Zgrablić | 3 | 23 | 3.69 |