Show simple item record

dc.contributor.authorWang, J.
dc.contributor.authorHuang, J.
dc.contributor.authorTeo, Kok Lay
dc.contributor.authorBelardo, F.
dc.contributor.authorLiu, R.
dc.contributor.authorYe, C.
dc.identifier.citationWang, J. and Huang, J. and Teo, K.L. and Belardo, F. and Liu, R. and Ye, C. 2013. Almost every complement of a tadpole graph is not chromatically unique. Ars Combinatoria. 108: pp. 33-49.

The study of chromatically unique graphs has been drawing much attention and many results are surveyed in [4, 12, 13]. The notion of adjoint polynomials of graphs was first introduced and applied to the study of the chromaticity of the complements of the graphs by Liu [17] (see also [4]). Two invariants for adjoint equivalent graphs that have been employed successfully to determine chromatic unique graphs were introduced by Liu [17] and Dong et al. [4] respectively. In the paper, we shall utilize, among other things, these two invariants to investigate the chromaticity of the complement of the tadpole graphs C n (P m ), the graph obtained from a path P m and a cycle C n by identifying a pendant vertex of the path with a vertex of the cycle. Let G stand for the complement of a graph G. We prove the following results: The graph C n-1 (P 2 ) is chromatically unique if and only if n = 5, 7. Almost every C n (P m ) is not chromatically unique, where n = 4 and m = 2. AMS classification: 05C15, 05C60. Copyright © 2013, Charles Babbage Research Centre.

dc.publisherCharles Babbage
dc.titleAlmost every complement of a tadpole graph is not chromatically unique
dc.typeJournal Article
dcterms.source.titleArs Combinatoria
curtin.departmentSchool of Electrical Engineering, Computing and Mathematical Science (EECMS)
curtin.accessStatusFulltext not available

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record