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 Cn(Pm), the graph obtained from a path P m and a cycle Cn 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 Cn-1(P2) is chromatically unique if and only if n = 5, 7. Almost every Cn(P m) is not chromatically unique, where n ≥ 4 and m ≥ 2.
Almost every complement of a tadpole graph is not chromatically unique / Wang, J. F.; Huang, J. Q. X.; Teo, K. L.; Belardo, Francesco; Liu, R. Y.; Ye, C. F.. - In: ARS COMBINATORIA. - ISSN 0381-7032. - 108:(2013), pp. 33-49.
Almost every complement of a tadpole graph is not chromatically unique
BELARDO, Francesco;
2013
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 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 Cn(Pm), the graph obtained from a path P m and a cycle Cn 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 Cn-1(P2) is chromatically unique if and only if n = 5, 7. Almost every Cn(P m) is not chromatically unique, where n ≥ 4 and m ≥ 2.File | Dimensione | Formato | |
---|---|---|---|
Almost every complement of a tadpole graph is not chromatically unique.pdf
non disponibili
Descrizione: Articolo completo in Post-print
Tipologia:
Documento in Post-print
Licenza:
Accesso privato/ristretto
Dimensione
220.08 kB
Formato
Adobe PDF
|
220.08 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.