Preservers of Cover Numbers and Independence Numbers of Undirected Graphs

Abstract

Let ${\mathcal{G}}_n$ be the set of all simple loopless undirected graphs on $n$ vertices. Let $T$ be a linear mapping, $T:{\mathcal{G}}_n\to {\mathcal{G}}_n$ for which the independence number of $T(G)$ is the same as the independence number for $G$ for any $G\in {\mathcal{G}}_n$. We show that $T$ is necessarily a vertex permutation. Similar results are obtained for mappings preserving the matching number of bipartite graphs, the vertex cover number of undirected graphs, and the edge independence number of undirected graphs.