Harmonious colourings of graphs

详细信息    查看全文

• 作者：Ewa Drgas-Burchardt ; ^{E.Drgas-Burchardt@wmie.uz.zgora.pl} ; Katarzyna Gibek ^{katarzynagibek@wp.pl}
• 关键词：Nordhaus&ndash ; Gaddum type theorem ; Graph polynomials ; Harmonious colourings
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：30 January 2017
• 年：2017
• 卷：217
• 期：part_P2
• 页码：175-184
• 全文大小：509 K
• 卷排序：217

文摘

A λλ-harmonious colouring   of a graph GG is a mapping from V(G)V(G) into {1,…,λ}{1,…,λ} that assigns colours to the vertices of GG such that each vertex has exactly one colour, adjacent vertices have different colours, and any two edges have different colour pairs. The harmonious chromatic number  h(G)h(G) of a graph GG is the least positive integer λλ, such that there exists a λλ-harmonious colouring of GG.Let h(G,λ)h(G,λ) denote the number of all λλ-harmonious colourings of GG. In this paper we analyse the expression h(G,λ)h(G,λ) as a function of a variable λλ. We observe that this is a polynomial in λλ of degree ∣V(G)∣∣V(G)∣, with a zero constant term. Moreover, we present a reduction formula for calculating h(G,λ)h(G,λ). Using reducing steps we show the meaning of some coefficients of h(G,λ)h(G,λ) and prove the Nordhaus–Gaddum type theorem, which states that for a graph GG with diameter greater than two h(G)+12χ(G2¯)≤∣V(G)∣, whereχ(G2¯) is the chromatic number of the complement of the square of a graph GG. Also the notion of harmonious uniqueness is discussed.