Near automorphisms of complement or square of a path

Dein Wong (), Jiahui Yin and Jiao Wang
Additional contact information
Dein Wong: China University of Mining and Technology
Jiahui Yin: China University of Mining and Technology
Jiao Wang: China University of Mining and Technology

Journal of Combinatorial Optimization, 2023, vol. 45, issue 2, No 22, 10 pages

Abstract: Abstract Let G be a connected graph with vertex set V(G), f a permutation of V(G). Define $$\delta _f (x,y)=|d(x,y)-d(f(x),f(y))|$$ δ f ( x , y ) = | d ( x , y ) - d ( f ( x ) , f ( y ) ) | and $$\delta _f (G)= \sum \delta _f (x,y)$$ δ f ( G ) = ∑ δ f ( x , y ) , where the sum is taken over all unordered pairs x, y of distinct vertices of G. Let $$\pi (G)$$ π ( G ) denote the smallest positive value of $$\delta _f (G)$$ δ f ( G ) among all permutations of V(G). A permutation f with $$\delta _f (G) =\pi (G)$$ δ f ( G ) = π ( G ) is called a near automorphism of G and $$\pi (G)$$ π ( G ) is called the value of near automorphisms of G. In this paper, the near automorphisms of the complement of a path and the near automorphisms of the square of a path are characterized, respectively. Moreover, $$\pi (\overline{P_n})$$ π ( P n ¯ ) and $$\pi (P_n^2)$$ π ( P n 2 ) are determined. As a result, one can find how much the near automorphisms of $$\overline{P_n}$$ P n ¯ and $$P_n^2$$ P n 2 differ from those of $$P_n$$ P n .

Keywords: Near automorphism; Automorphism; Complement of a graph; Square graph; 05C15; 05C78 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-023-01013-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:45:y:2023:i:2:d:10.1007_s10878-023-01013-w

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-023-01013-w

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().