Nonisomorphic graphs with the same t-polynomial

DOI10.1016/0020-0190(86)90057-8MaRDI QIDQ1089010zbMATH OpenOpenAlexFDO

Authors Yoshio Hattori

Publication date 1986

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(86)90057-8

zbMATH Keywords

characteristic polynomialHT-polynomialLaplace matrix

Mathematics Subject Classification ID

Graph theory (05C99)

Review text

It is known that the smallest positive integer n for which there exist nonisomorphic trees (with n vertices) which have the same T-polynomial is 11. In this note, it is shown that if the trees in the above are replaced by simple graphs then 6 is the smallest positive integer. Further, it is shown that there exist two such (non-isomorphic) pairs (for \(n=6)\). It is observed that one pair is the complement of the other.

Recommendations

• Tutte polynomials and a stronger version of the Akiyama-Harary problem
• On graphs determined by their Tutte polynomials
• On the smallest trees with the same restricted U-polynomial and the rooted U-polynomial
• Indistinguishable trees and graphs
• On graphs with the same restricted \(U\)-polynomial and the \(U\)-polynomial for rooted graphs

Cites work

• A certain polynomial of a graph and graphs with an extremal number of trees
• Comparison of graphs by their number of spanning trees
• Nonisomorphic trees with the same T-polynomial
• Tree counting polynomials for labelled graphs. I: Properties

Cited in

(3)

• Laplacian matrices of graphs: A survey
• Terminal polynomials and star-like graphs
• Ordering trees by algebraic connectivity

This page was built for publication: Nonisomorphic graphs with the same t-polynomial

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1089010)