On properties of adjoint polynomials of graphs and their applications

Haixing Zhao, Ruying Liu, Xueliang Li, Ligong Wang

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

For a graph G, we denote by P(G, λ) the chromatic polynomial of G and by h(G, x) the adjoint polynomial of G. A graph G is said to be chromatically unique if for any graph H, P(H, λ) = P(G, λ) implies H ≅ G. In this paper, we investigate some algebraic properties of the adjoint polynomials of some graphs. Using these properties, we obtain necessary and sufficient conditions for Kn - E(∪a,bT1,a,b) and (∪iCni) ∪ (∪iDmj) ∪ (∪a,bT1,a,b) to be chromatically unique if Gi ∈ {Cn,Dn, T1,a,b|n ≥ 5, 3 ≤ a ≤ 10, a ≤ b} and h(Pm) h(Gi) for all m ≥ 2. Moreover, many new chromatically unique graphs are given.

Original languageEnglish
Pages (from-to)291-306
Number of pages16
JournalAustralasian Journal of Combinatorics
Volume30
StatePublished - 2004

Fingerprint

Dive into the research topics of 'On properties of adjoint polynomials of graphs and their applications'. Together they form a unique fingerprint.

Cite this