E k-Cordial graph

[math]\displaystyle{ \,E_{k} }[/math]-Cordial graph — [math]\displaystyle{ \,E_{k} }[/math]-сердечный граф.

Let [math]\displaystyle{ \,f }[/math] be an edge labelling of a graph [math]\displaystyle{ \,G = (V,E) }[/math], such that

[math]\displaystyle{ \,f: \; E(G) \rightarrow \{0,1, \ldots, k-1\} }[/math]

and the induced vertex labelling is given as

[math]\displaystyle{ \,f(v) = \sum_{\forall u}f(u,v)\pmod{k}, }[/math]

where [math]\displaystyle{ \,v \in V }[/math] and [math]\displaystyle{ \,\{u,v\} \in E }[/math]. [math]\displaystyle{ \,f }[/math] is called an [math]\displaystyle{ \,E_{k} }[/math]-cordial labelling of [math]\displaystyle{ \,G }[/math], if the following conditions are satisfied for [math]\displaystyle{ \,i,j = 0, 1, \ldots, k-1 }[/math], [math]\displaystyle{ \,i\neq j }[/math].

[math]\displaystyle{ \,1) \; |e_{f}(i) - e_{f}(j)| \leq 1, }[/math]

[math]\displaystyle{ \,2) \; |v_{f}(i) - v_{f}(j)| \leq 1, }[/math]

where [math]\displaystyle{ \,e_{f}(i), \; e_{f}(j) }[/math] denote the number of edges, and [math]\displaystyle{ \,v_{f}(i), \; v_{f}(j) }[/math] denote the number of vertices labelled with [math]\displaystyle{ \,i }[/math]'s and [math]\displaystyle{ \,j }[/math]'s respectively.

The graph [math]\displaystyle{ \,G }[/math] is called [math]\displaystyle{ \,E_{k} }[/math]-cordial if it admits an [math]\displaystyle{ \,E_{k} }[/math]-cordial labelling.

See also

• Edge-graceful graph.

Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.