Antimagic graph

Перейти к:навигация, поиск

Antimagic graphантимагический граф.

An antimagic graph is a graph whose edges can be labeled with integers $1,2, \ldots, e$ so that the sum of the labels at any given vertex is different from the sum of the labels of any other vertex, that is, no two vertices have the same sum. Hartsfield and Ringel conjecture that every tree other than $\,K_{2}$ is antimagic and, more strongly, that every connected graph other than $\,K_{2}$ is antimagic.

A special case is an $\,(a,d)$-antimagic graph. The weight $\,w(x)$ of a vertex $x \in V(G)$ under an edge labeling $f: \; E \rightarrow \{1,2, \ldots,e\}$ is the sum of values $\,f(xy)$ assigned to all edges incident with a given vertex $\,x$. A connected graph $\,G = (V,E)$ is said to be $\,(a,d)$-antimagic if there exist positive integers $\,a,d$ and a bijection $f: \; E \rightarrow \{1,2, \ldots, e\}$ such that the induced mapping $g_{f}: \; V(G) \rightarrow W$ is also bijection, where $W = \{w(x); x \in V(G)\} = \{a, a+d, a+2d, \ldots, a+(v-1)D\}$ is the set of the weights of vertices.