Almost every complement of a tadpole graph is not chromatically unique
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 invar...
| Main Authors: | , , , , , |
|---|---|
| Format: | Journal Article |
| Published: |
Charles Babbage
2013
|
| Online Access: | http://hdl.handle.net/20.500.11937/63383 |
| _version_ | 1848761073760468992 |
|---|---|
| author | Wang, J. Huang, J. Teo, Kok Lay Belardo, F. Liu, R. Ye, C. |
| author_facet | Wang, J. Huang, J. Teo, Kok Lay Belardo, F. Liu, R. Ye, C. |
| author_sort | Wang, J. |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T10:25:53Z |
| format | Journal Article |
| id | curtin-20.500.11937-63383 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T10:25:53Z |
| publishDate | 2013 |
| publisher | Charles Babbage |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-633832018-02-06T06:17:02Z Almost every complement of a tadpole graph is not chromatically unique Wang, J. Huang, J. Teo, Kok Lay Belardo, F. Liu, R. Ye, C. 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. 2013 Journal Article http://hdl.handle.net/20.500.11937/63383 Charles Babbage restricted |
| spellingShingle | Wang, J. Huang, J. Teo, Kok Lay Belardo, F. Liu, R. Ye, C. Almost every complement of a tadpole graph is not chromatically unique |
| title | Almost every complement of a tadpole graph is not chromatically unique |
| title_full | Almost every complement of a tadpole graph is not chromatically unique |
| title_fullStr | Almost every complement of a tadpole graph is not chromatically unique |
| title_full_unstemmed | Almost every complement of a tadpole graph is not chromatically unique |
| title_short | Almost every complement of a tadpole graph is not chromatically unique |
| title_sort | almost every complement of a tadpole graph is not chromatically unique |
| url | http://hdl.handle.net/20.500.11937/63383 |