If $G$ is a super edge magic graph with $p$ vertices and $q$ edges then $\displaystyle \sum_{v \in V(G)}f(v)deg(v) $ equals some expression

70 Views Asked by At

So I am studying some material on supeer edge magic graphs and the definition is: $G$ (always with $p$ vertices and $q$ edges) is super edge magic iff there is a bijection $f:V(G)\cup E(G) \rightarrow \{1,\dots,p+q\}$ st $f(u)+f(v)+f(uv)$ is constant for every $uv \in E(G)$.

Then there is a theorem which proves that the following is an equivalent definition: $G$ is super edge magic iff there is a bijection $f:V(G) \rightarrow \{1,\dots,p\}$ st $S=\{f(u)+f(v):uv \in E(G)\}$ is a set of $q$ conscutive integers.

So far so good.

And then there is this obvious corollary which for me is not so obvious that states that if $G$ is super edge magic and $f$ is as on the first definition, then $$ \displaystyle \sum_{v \in V(G)} f(v) \deg(v) = qs + \binom{q}{2},$$ where $s = \min S$, as in the equivalent definition.

So... how exactly is this a direct corollary? I don't see the relation of the equation and the definition. On the definition of $S$ there is a difference $f(u)-f(v)$ and there is only $f(v)$ on that equation. Also I'm not sure where that 2-combination of $q$ appeared from?

Anyone can help?

1

There are 1 best solutions below

1
On BEST ANSWER

For each edge $uv \in E(G)$, add $f(u)$ and $f(v)$. When we do this for every edge, it becomes

$$\sum_{uv \in E(G)} f(u) + f(v) = \sum_{v \in V(G)} f(v) \deg (v)$$

because $f(v)$ gets added $\deg (v)$ times. But by definition, $$\sum_{uv \in E(G)} f(u) + f(v) = \operatorname{sum} (S) ,$$

and $S$ is a set of $q$ consecutive integers, starting at $s$. Therefore,

$$\operatorname{sum}(S) = \sum_{k=s}^{s+q-1} k = qs + \sum_{k=0}^{q-1} k = qs + \binom{q}{2}.$$