Linear maps on graphs preserving a given independence number

Yanan Hu, Zejun Huang

Published 2018-04-30Version 1

Denote by $\mathscr{G}_n$ the set of simple graphs with vertex set $\{1,2,\ldots,n\}$. A complete linear map $\phi: \mathscr{G}_n \rightarrow\mathscr{G}_n$ is a map satisfying $\phi(K_n)=K_n$ and $$\phi(G_1\cup G_2)=\phi(G_1)\cup \phi(G_2)~~~~{\rm for ~all~}G_1,G_2\in \mathscr{G}_n.$$ Given positive integers $n$ and $t$ such that $t\le n-1$, we prove that a complete linear map $\phi: \mathscr{G}_n\rightarrow \mathscr{G}_n$ satisfies $$\alpha(\phi(G))=t~\iff \alpha(G)=t {~~~~\rm for~ all~}G\in \mathscr{G}_n$$ iff $\phi$ is an edge permutation when $t=1$ and $\phi$ is a vertex permutation when $t\ge 2$, where $\alpha(G)$ is the independence number of a graph $G$.