Tutte polynomials and a stronger version of the Akiyama-Harary problem (Q497304)

Two graphs are said to be chromatically equivalent if they have the same chromatic polynomials, and Tutte equivalent if they have the same Tutte polynomials. This paper is concerned with non self-complementary graphs that are chromatically equivalent or Tutte equivalent to their complements. It offers two results on such graphs. The first result is the construction of an infinite family of graphs such that each graph in the family is chromatically equivalent to its complement, but has a different degree sequence to its complement. (This disproves a conjecture of \textit{J. Xu} and \textit{Z. Liu} [Graphs Comb. 11, No. 4, 337--345 (1995; Zbl 0844.05044)].) The second result is the construction of an infinite family of graphs such that each graph in the family has a non-isomorphic complement, but is Tutte equivalent to it. With reference to their result on chromatically equivalent, each graph in this family has a different degree sequence to its complement, and the authors ask if there is a graph that is Tutte equivalent to its complement, but with a different degree sequence to its complement.