# 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 *v**w* ∈ *E*(*G*), there is an edge *x**y* ∈ *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.