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, which 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 $\overline{G}$ stand for the complement of a graph $G$. We prove the following results: 1) The graph $\overline{C_{n-1}(P_2)}$ is chromatically unique if and only if n ≠ 5,7. 2) Almost every $\overline{C_n(P_m)}$ is not chromatically unique, where n ≥ 4 and m ≥ 2.

### Almost every complement of a tadpole graph is not chromatically unique

#### Abstract

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, which 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 $\overline{G}$ stand for the complement of a graph $G$. We prove the following results: 1) The graph $\overline{C_{n-1}(P_2)}$ is chromatically unique if and only if n ≠ 5,7. 2) Almost every $\overline{C_n(P_m)}$ is not chromatically unique, where n ≥ 4 and m ≥ 2.
##### Scheda breve Scheda completa Scheda completa (DC)
2013
File in questo prodotto:
Non ci sono file associati a questo prodotto.
##### Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11570/2470621
##### Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

• ND
• 1
• 1