Binary Graph Labelings and Linear Preservers
Keywords:
Binary vertex labeling, Freyberg-Marr labeling, linear operator, vertex permutation
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.
References
\bibitem{BP} L. B. Beasley and N. J. Pullman, ``Linear operators preserving properties of graphs", {\it Congressus Num.}, 70(1990) 105-112.
\bibitem{B} L. B. Beasley, ``Cordial Digraphs'', J. of Comb. Math. and Comb. Comput., (2022), Vol 117, P1, 1-23. arXiv 2212.05142,
\bibitem{B2} L. B. Beasley, ``Graph Cordiality -- Extremes and Preservers'', preprint.
\bibitem{BG} L. B. Beasley, and S.-Z. Song, ``Genus of a Graph and its Strong Preservers'', Linear and Multilinear Alg., 68(2020)1655-1662.
\bibitem{BMSB} L. B. Beasley, J. Mousley, M. A. Santana, and D. E. Brown, Cordiality of Digraphs, J. Alg. Comb. Disc. Math. and Appl., (2022), Vol 10(1), 1-13.
\bibitem{C} I. Cahit, Cordial graphs: A weaker version of graceful and harmonious graphs, Ars Comb. 23(1987) 201-208.
\bibitem{FM} B. Freyberg and A. Marr, Red-Blue Colorings of Graphs, a talk (virtual) given by B. Freyberg at the 53rd Southeastern International Conference on Combinatorics, Graph Theory \& Computing, Florida Atlantic University, March 2022.
\bibitem{B} L. B. Beasley, ``Cordial Digraphs'', J. of Comb. Math. and Comb. Comput., (2022), Vol 117, P1, 1-23. arXiv 2212.05142,
\bibitem{B2} L. B. Beasley, ``Graph Cordiality -- Extremes and Preservers'', preprint.
\bibitem{BG} L. B. Beasley, and S.-Z. Song, ``Genus of a Graph and its Strong Preservers'', Linear and Multilinear Alg., 68(2020)1655-1662.
\bibitem{BMSB} L. B. Beasley, J. Mousley, M. A. Santana, and D. E. Brown, Cordiality of Digraphs, J. Alg. Comb. Disc. Math. and Appl., (2022), Vol 10(1), 1-13.
\bibitem{C} I. Cahit, Cordial graphs: A weaker version of graceful and harmonious graphs, Ars Comb. 23(1987) 201-208.
\bibitem{FM} B. Freyberg and A. Marr, Red-Blue Colorings of Graphs, a talk (virtual) given by B. Freyberg at the 53rd Southeastern International Conference on Combinatorics, Graph Theory \& Computing, Florida Atlantic University, March 2022.
