Almost every complement of a tadpole graph is not chromatically unique
MetadataShow full item record
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  (see also ). Two invariants for adjoint equivalent graphs that have been employed successfully to determine chromatic unique graphs were introduced by Liu  and Dong et al.  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.
Showing items related by title, author, creator and subject.
Achuthan, Nirmala; Achuthan, Narasimaha; Simanihuruk, M. (2011)A graph is (m, k)-colourable if its vertices can be coloured with m colours such that the maximum degree of the subgraph induced on vertices receiving the same colour is at most k. The k-defective chromatic number Xk(G) ...
Pearce, Adrian (1996)Spatial interpretation involves the intelligent processing of images for learning, planning and visualisation. This involves building systems which learn to recognise patterns from the content of unconstrained data such ...
Evaluation of anthropometry activities for high school science: student outcomes and classroom environmentLightburn, Millard E. (2002)The study involved the evaluation of anthropometric activities for high school science. The activities actively engaged students in the process of gathering, processing and analyzing data derived from human body measurements, ...