Lexicographic palindromic products

Abstract

A graph G on n vertices is palindromic if there is a vertex-labeling bijection f : V(G) → {1, 2, …, n} with the property that for any edge vw ∈ E(G), there is an edge xy ∈ E(G) for which f(x) = n − f(v) + 1 and f(y) = n − f(w) + 1.

We characterize the conditions under which a lexicographic product G ∘ H is palindromic, as follows: If G ∘ H has an even number of vertices, then it is palindromic if and only if at least one of G or H is palindromic. If G ∘ H has an odd number of vertices, then it is palindromic if and only if both G and H are palindromic.

Published
2022-01-04
Section
Articles