A note on binary graph labelings and linear preservers

Abstract

An FM labeling of the vertices of an undirected graph requires that half the neighbors of each vertex are labeled zero and the other half labeled one. Variations of this type of labeling are presented and examples of the smallest and largest of graphs having one of these FM labelings are given. It is also shown that if $T$ is a linear operator on the set of all undirected graphs on $n$ vertices that strongly preserves sets of graphs that are labelable by one of the various FM type labelings, then $T$ is a vertex permutation.

Received: 13 February 2023 | Accepted: 9 September 2023