Near automorphisms of cycles (Q2469986): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.disc.2007.03.062 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2069417366 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Total relative displacement of permutations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Quadratic integer programming with application to the chaotic mappings of complete multipartite graphs. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Total relative displacement of vertex permutations of <i>K</i> / rank | |||
Normal rank |
Latest revision as of 15:42, 27 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Near automorphisms of cycles |
scientific article |
Statements
Near automorphisms of cycles (English)
0 references
11 February 2008
0 references
Let \(f\) be a permutation of the vertex set \(V(G)\) of a connected finite simple graph \(G\). Let \(\delta_f(G)=\sum_{x,y\in V(G)}| d_G(x,y)-d_G(f(x),f(y))| \), where the sum is over all unordered pairs of vertices. It is clear that \(f\) is an automorphism of \(G\) if and only if \(\delta_f(G)=0\). By a near automorphism of \(G\) the authors mean a permutation \(f\) for which \(\delta_f(G)\) takes the smallest possible strictly positive value, this value is denoted \(\pi(G)\). This quantity has been computed for a path by \textit{W. Aitken} [J. Comb. Theory, Ser. A 87, No.~1, 1--21 (1999; Zbl 0937.05001)], and for a complete multipartite graphs by \textit{K. B. Reid} [J. Graph Theory 41, No.~2, 85--100 (2002; Zbl 1020.05034)]. The purpose of this paper is to prove that \(\pi(C_n)=4\lfloor n/2\rfloor -4\) and to describe the set of near automorphisms of \(C_n\), where \(C_n\) is a cycle of length \(n\).
0 references
Graph automorphism
0 references
near automorphism
0 references