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.
2013
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.
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11588/620314
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact