Lexicographic palindromic products
Jamie Shive · The Art of Discrete and Applied Mathematics · 2022
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.