Preservers of Cover Numbers and Independence Numbers of Undirected Graphs

LeRoy B. Beasley1
1Department of Mathematics and Statistics, Utah State University Logan, Utah 84322-3900, USA

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 \rightarrow \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.