# A Type of Arithmetic Labels about Circulating Ring

Ergen Liu, Dan Wu, Kewen Cai

► To cite this version:

Ergen Liu, Dan Wu, Kewen Cai. A Type of Arithmetic Labels about Circulating Ring. 4th Conference on Computer and Computing Technologies in Agriculture (CCTA), Oct 2010, Nanchang, China. pp.390-397, 10.1007/978-3-642-18369-0_45. hal-01564833

HAL Id: hal-01564833

https://inria.hal.science/hal-01564833

Submitted on 19 Jul 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A type of Arithmetic Labels about Circulating ring

Ergen Liu Dan Wu Kewen Cai

(School of Basic Sciences, East China Jiaotong University, Nanchang, P.R.China, 330013)

E-mail: leg_eg@sina.com

## Abstract

The graph composed with several rings is a kind of important and interesting graph, many scholars studied on the gracefulness of this kind of the graph, The reference [1] is given the gracefulness of m kinds C₄ with one common point. In this paper, we researched the arithmetic labels of four kinds graph: C₈,₁,ₙ, C₈,₂,ₙ, C₈,₃,ₙ, C₈,₄,ₙ, and we proved they are all (d,2d)--arithmetic graph.

**Key Word:** Arithmetic graph; labeling of graph; C₈,ᵢ,ₙ

## 1. Introduction

The graph in this paper discussed are undirected, no multiple edges and simple graph, the unorganized state of definitions and terminology and the symbols in this graph referred to reference[2][3].

There are two kinds of labels of the graph: one is the reduced label, is to say that in order to get the label of one edge you should reduce the endpoints of the edge; the other is additive label, for the same you should acttive the endpoints of one edge to get the label of the edge. For example, the well-known of “Gracefulness” is reduced. the “Compatible labels” is additive. In 1990, B.D.Achaya and S.M.Hegde import the concept of “Arithmetic lables”(referred to reference[2]), which is a more extensive additive label, it have applied value on solution to question of the joint ventures in rights and obligations.

**Definition 1.1** For $G = (V, E)$, if there is a mapping $f$ (called the vertices $v$ of the label) from $V(G)$ to the set of nonnegative integer $N_0$, meet:

(1) $f(u) \neq f(v)$, which $u \neq v$, and $u, v \in V(G)$;

(2) $\{f(u) + f(v) | uv \in E(G)\} = \{k, k+d, \dots, k+(q-1)d\}$.

Then we call graph $G$ is a $(k, d)$--arithmetic graph.

## 2. Main results and certification

**Theorem 2.1** $C_{8,1,n}$ is a $(d,2d)$--arithmetic graph.

**Proof** As the graph shown on fig.1.

<figure><img src="image_2.png" /><figcaption>Fig.1.The Graf $C_{8,1,n}$</figcaption></figure>
Label all vertices as follows:

$$
\begin{align*}
f(v_1^{(i)}) &= 8id(i=0,1,2,\dots,n), & f(v_2^{(i)}) &= 8id+d(i=0,1,2,\dots,n-1), \\
f(v_3^{(i)}) &= 8id+3d(i=0,1,2,\dots,n-1), & f(v_4^{(i)}) &= 8id+6d(i=0,1,2,\dots,n-1), \\
f(v_5^{(i)}) &= 8id+2d(i=0,1,2,\dots,n-1), & f(v_6^{(i)}) &= 8id+5d(i=0,1,2,\dots,n-1), \\
f(v_7^{(i)}) &= 8id+7d(i=0,1,2,\dots,n-1).
\end{align*}
$$

Now we proof that the mapping $f$ is arithmetic labeling of $C_{8,1,n}$.

We can see the mapping $f$ meet $f(u) \neq f(v)$ which $u \neq v$ and $u,v \in V(C_{8,1,n})$.

Next we prove $\{f(u) + f(v) | uv \in E(C_{8,1,n})\}$ is an arithmetic progression in the way of mathematical induction.

When $n=1$

$$
\text{Then } f(v_1^{(0)}) = 0, \ f(v_2^{(0)}) = d, \ f(v_3^{(0)}) = 3d, \ f(v_4^{(0)}) = 6d, \ f(v_5^{(0)}) = 2d, \ f(v_6^{(0)}) = 5d, \\
f(v_7^{(0)}) = 7d, \ f(v_1^{(1)}) = 8d.
$$

$$
\begin{align*}
\text{Therefore } \{f(u) + f(v) | uv \in E(C_{8,1,1})\} \\
&= \{f(v_1^{(0)}) + f(v_2^{(0)}), f(v_1^{(0)}) + f(v_3^{(0)}), f(v_3^{(0)}) + f(v_5^{(0)}), f(v_2^{(0)}) + f(v_4^{(0)}), \\
& \qquad f(v_5^{(0)}) + f(v_7^{(0)}), f(v_4^{(0)}) + f(v_6^{(0)}), f(v_6^{(0)}) + f(v_1^{(1)}), f(v_7^{(0)}) + f(v_1^{(1)})\} \\
&= \{d, 3d, 5d, 7d, 9d, 11d, 13d, 15d\}
\end{align*}
$$

is an arithmetic progression, and the common difference is 2d.

Suppose when $n=k-1$, we know

$$
\{f(u) + f(v) | uv \in E(C_{8,1,k-1})\} = \{d, d+1 \times 2d, d+2 \times 2d, \dots, d+(8k-9) \times 2d\}
$$

is an arithmetic progression, and the common difference is 2d.

Then when $n=k$

$$
\begin{align*}
& \{f(u) + f(v) | uv \in E(C_{8,1,k})\} \\
&= \{f(u) + f(v) | uv \in E(C_{8,1,k-1})\} \cup \{f(v_1^{(k-1)}) + f(v_2^{(k-1)}), f(v_1^{(k-1)}) + f(v_3^{(k-1)}), f(v_3^{(k-1)}) + f(v_5^{(k-1)}), \\
& \phantom{= \{f(u) + f(v) | uv \in E(C_{8,1,k-1})\} \cup \{f(v_1^{(k-1)}) + f(v_2^{(k-1)}),} f(v_2^{(k-1)}) + f(v_4^{(k-1)}), f(v_5^{(k-1)}) + f(v_7^{(k-1)}), f(v_4^{(k-1)}) + f(v_6^{(k-1)}), f(v_6^{(k-1)}) + f(v_1^{(k)}), f(v_7^{(k-1)}) + f(v_1^{(k)})\} \\
&= \{d, d+1 \times 2d, d+2 \times 2d, \dots, d+(8k-9) \times 2d\} \cup \{d+(8k-8) \times 2d, d+(8k-7) \times 2d, \\
& \phantom{= \{d, d+1 \times 2d, d+2 \times 2d, \dots, d+(8k-9) \times 2d\} \cup \{d+(8k-8) \times 2d,} d+(8k-6) \times 2d, d+(8k-5) \times 2d, d+(8k-4) \times 2d, d+(8k-3) \times 2d, d+(8k-2) \times 2d, d+(8k-1) \times 2d\} \\
&= \{d, d+1 \times 2d, d+2 \times 2d, \dots, d+(8k-1) \times 2d\}
\end{align*}
$$

is an arithmetic progression, and the common difference is 2d.

In sum for the arbitrary $n \in N_0$, the mapping $f:V(C_{8,1,n}) \rightarrow N_0$ meet:

(1) $f(u) \neq f(v)$ when $u \neq v$ and $u, v \in V(C_{8,1,n})$;

(2) $\{f(u) + f(v) | uv \in E(C_{8,1,n})\} = \{d, d+1 \times 2d, d+2 \times 2d, \dots, d+(8n-1) \times 2d\}$.

Therefore $C_{8,1,n}$ is a $(d,2d)$-arithmetic graph.

**Theorem 2.2** $C_{8,2,n}$ is a $(d,2d)$--arithmetic graph.

**Proof** As the graph shown on fig.2.
<figure><img src="image_3.png" /><figcaption>Fig.2. The Graph $C_{8,2,n}$</figcaption></figure>

Label all vertices as follows:

$$f(v_1^{(i)}) = 7id(i = 0,1,2,\dots,n), \qquad f(v_4^{(i)}) = 7id + 6d(i = 0,1,2,\dots,n-1),$$

$$f(v_2^{(i)}) = 7id + d(i = 0,1,2,\dots,n), \qquad f(v_5^{(i)}) = 7id + 2d(i = 0,1,2,\dots,n-1),$$

$$f(v_3^{(i)}) = 7id + 3d(i = 0,1,2,\dots,n-1), \qquad f(v_6^{(i)}) = 7id + 5d(i = 0,1,2,\dots,n-1).$$

Now we prove that the mapping $f$ is arithmetic labeling of $C_{8,2,n}$

We can see the mapping $f$ meet $f(u) \neq f(v)$ which $u \neq v$ and $u,v \in V(C_{8,2,n})$.

Next we prove $\{f(u) + f(v) | uv \in E(C_{8,2,n})\}$ is an arithmetic progression in the way of mathematical induction.

When $n=1$

$$\text{Then } f(v_1^{(0)}) = 0, f(v_2^{(0)}) = d, f(v_3^{(0)}) = 3d, f(v_4^{(0)}) = 6d, f(v_5^{(0)}) = 2d, f(v_6^{(0)}) = 5d, \\ f(v_1^{(1)}) = 7d, f(v_2^{(1)}) = 8d.$$

$$\text{Therefore } \{f(u) + f(v) | uv \in E(C_{8,2,1})\} \\ = \{f(v_1^{(0)}) + f(v_2^{(0)}), f(v_1^{(0)}) + f(v_3^{(0)}), f(v_3^{(0)}) + f(v_5^{(0)}), \\ f(v_2^{(0)}) + f(v_4^{(0)}), f(v_5^{(0)}) + f(v_1^{(1)}), f(v_4^{(0)}) + f(v_6^{(0)}), f(v_6^{(0)}) + f(v_2^{(1)}), f(v_1^{(1)}) + f(v_2^{(1)})\} \\ = \{d, 3d, 5d, 7d, 9d, 11d, 13d, 15d\}$$

is an arithmetic progression, and the common difference is $2d$.

Suppose when $n=k-1$, we know

$$\{f(u) + f(v) | uv \in E(C_{8,2,k-1})\} = \{d, d+1 \times 2d, d+2 \times 2d, \dots, d+(7k-7) \times 2d\}$$

is an arithmetic progression, and the common difference is $2d$.

Then when $n=k$

$$\begin{aligned} & \{f(u) + f(v) | uv \in E(C_{8,2,k})\} \\ &= \{f(u) + f(v) | uv \in E(C_{8,2,k-1})\} \cup \{f(v_1^{(k-1)}) + f(v_3^{(k-1)}), f(v_3^{(k-1)}) + f(v_5^{(k-1)}), \\ & f(v_2^{(k-1)}) + f(v_4^{(k-1)}), f(v_5^{(k-1)}) + f(v_1^{(k)}), f(v_4^{(k-1)}) + f(v_6^{(k-1)}), f(v_6^{(k-1)}) + f(v_2^{(k)}), f(v_1^{(k)}) + f(v_2^{(k)})\} \\ &= \{d, d+1 \times 2d, d+2 \times 2d, \dots, d+(7k-7) \times 2d\} \cup \{d+(7k-6) \times 2d, d+(7k-5) \times 2d, \\ & d+(7k-4) \times 2d, d+(7k-3) \times 2d, d+(7k-2) \times 2d, d+(7k-1) \times 2d, d+7k \times 2d\} \\ &= \{d, d+1 \times 2d, d+2 \times 2d, \dots, d+7k \times 2d\} \end{aligned}$$

is an arithmetic progression, and the common difference is $2d$.

In sum for the arbitrary $n \in N_0$, the mapping $f: V(C_{8,2,n}) \to N_0$ meet:
(1) $f(u) \neq f(v)$ when $u \neq v$ and $u, v \in V(C_{8,2,n})$;

(2) $\{f(u) + f(v) | uv \in E(C_{8,2,n})\} = \{d, d+1 \times 2d, d+2 \times 2d, \dots, d+7n \times 2d\}$.

Therefore $C_{8,2,n}$ is a $(d,2d)$--arithmetic graph.

**Theorem 2.3** $C_{8,3,n}$ is a $(d,2d)$--arithmetic graph.

**Proof** As the graph shown on fig.3.

<figure><img src="image_4.png" /><figcaption>Fig.3.The Graf $C_{8,3,n}$</figcaption></figure>

Label all vertices as follows:

$$f(v_0^{(i)}) = 8id(i = 0,1,2,\dots,n),$$

$$f(v_1^{(i)}) = 4id + d(i = 0,1,2,\dots,n),$$

$$f(v_3^{(i)}) = 4id + 3d(i = 0,1,2,\dots,n),$$

$$f(v_2^{(i)}) = 8id + 6d(i = 0,1,2,\dots,n-1),$$

$$f(v_4^{(i)}) = 8id + 2d(i = 0,1,2,\dots,n-1).$$

**Proof** in imitation of Theorem 2.1.

For the arbitrary $n \in N_0$, the mapping $f: V(C_{8,3,n}) \to N_0$ meet:

(1) $f(u) \neq f(v)$ when $u \neq v$ and $u, v \in V(C_{8,3,n})$;

(2) $\{f(u) + f(v) | uv \in E(C_{8,3,n})\} = \{d, d+1 \times 2d, d+2 \times 2d, \dots, d+(6n+1) \times 2d\}$.

By (1), (2) we know the mapping $f$ is arithmetic labeling of $C_{8,3,n}$. Therefore $C_{8,3,n}$ is a $(d,2d)$--arithmetic graph.

**Theorem 2.4** $C_{8,4,n}$ is a $(d,2d)$--arithmetic graph.

**Proof** As the graph shown on fig.4.

<figure><img src="image_5.png" /><figcaption>Fig.4.The Graf $C_{8,4,n}$</figcaption></figure>

Label all vertices as follows:

$$f(v_1^{(i)}) = 5id(i = 0,1,2,\dots,n),$$

$$f(v_2^{(i)}) = 5id + d(i = 0,1,2,\dots,n),$$
$$f(v_3^{(i)}) = 5id + 3d(i = 0,1,2,\dots,n),$$

$$f(v_4^{(i)}) = 5id + 2d(i = 0,1,2,\dots,n).$$

Proof in imitation of Theorem 2.2.

For the arbitrary $n \in N_0$, the mapping $f:V(C_{8,4,n}) \to N_0$ meet:

(1) $f(u) \neq f(v)$ when $u \neq v$ and $u, v \in V(C_{8,4,n})$;

(2) $\{f(u) + f(v) | uv \in E(C_{8,4,n})\} = \{d, d+1 \times 2d, d+2 \times 2d, \dots, d+(5n+2) \times 2d\}$.

By (1), (2) we know the mapping $f$ is arithmetic labeling of $C_{8,4,n}$. Therefore $C_{8,4,n}$ is a $(d,2d)$--arithmetic graph.

### 3. Labels of Some Special Graph

In order to explain the correctness of the aforementioned labels, we give the arithmetic labeling of $C_{8,1,3}$, $C_{8,2,3}$, $C_{8,3,3}$ and $C_{8,4,3}$.

(1) The arithmetic labeling of $C_{8,1,3}$ on fig.5.

<figure><img src="image_6.png" /><figcaption>Fig.5. The Graf $C_{8,1,3}$</figcaption></figure>

(2) The arithmetic labeling of $C_{8,2,3}$ on fig.6.

<figure><img src="image_7.png" /><figcaption>Fig.6. The Graf $C_{8,2,3}$</figcaption></figure>

(3) The arithmetic labeling of $C_{8,3,3}$ on fig.7.

<figure><img src="image_8.png" /><figcaption>Fig.7. The Graf $C_{8,3,3}$</figcaption></figure>

(4) The arithmetic labeling of $C_{8,4,3}$ on fig.8.
<figure><img src="image_9.png" /><figcaption>Fig.8. The Graph $C_{8,4,3}$</figcaption></figure>

References

[1] Ma Kejie. Gracefulness[M].Beijing:the press of technology,1991.

[2] Chartrand G,Lesniak L. Graphs and Digraphs[M].Wadsworth and Brooks/Cole,Monterey,1996.

[3] Bondy J A,Murty U S R. Graph Theory with Applications[M].Elsevier North-Holland, 1976.

[4] LIU Er-gen, WU Dan and CAI Ke-wen. Two Graphs Arithmetic Labeling[J], Journal of East China Jiaotong University. 2009, Vol.26(5): 89-92.

[5] Achaya B D and Hegde S M. Arithmetic graphs[J]. Journal of Graph Theory. 1990, 18(3):275-299.