1. Introduction
Throughout this paper, we consider connected graphs without loops or multiple edges. For a graph
and
are used to denote the vertex set and edge set of
and
denote the minimum degree and the maximum degree of a graph G, respectively. For a vertex
, the neighborhood of v in G is
is adjacent to v in
. Vertices in
are called neighbors of v,
denotes the number of vertices in
. The other terminology and notations are referred to [1].
For a given graph G, an integer
, an
- labeling of G is defined as a function
such that
if
; and
if
, where
, the distance of u and v, is the length (number of edges) of a shortest path between u and v. the
-labeling number, denoted
, is the least integer
such that G has a
-labeling.
The Motivated by the channel assignment problem introduced by Hale in [2], the
labeling have been studied extensively in the past decade. In 1992, in [3] Griggs and Yeh proposed the famous conjecture, for any graph
.
Griggs and Yeh in [3] proved that the conjecture true fop path, tree, circle, wheel and the graph with diameter 2, G. J. chang and David Kuo in [4] proved that
for any graph. Recently Kral D and Skrekovski R in [5] proved the upper is
. It is difficult to prove the conjecture. Now, the study of
- labeling is focus on special graph. Georges [6,7] give some good results. Zhang and Ma studied the labeling of some special graph, giving some good results in [8-11].
In this paper, we studied the
-labeling number of the product and the join graph on two fans.
2.
-Labeling Number of the Join Graph on Two Fans
Definition 2.1 Let
be a fan with m + 1 vertices
, in which
.
Definition 2.2 Let G and H be two graphs, the join of G and H denoted
, is a graph obtained by starting with a disjoint union of G and H, and adding edges joining each vertex of G to each vertex of H.
Theorem 2.1 Let
, if
, then
.
Proof. In
, for arbitrary vertex u and v, such that
, clearly
.
Let k denote the maximum labeling number of ![](https://www.scirp.org/html/15-7401498\75589e66-0fd0-4f04-9f6b-bffcbc725d82.jpg)
First, we give a
-labeling of
as follows,
.
If ![](https://www.scirp.org/html/15-7401498\dc870c7a-74ef-4c87-832c-64af8e8e7623.jpg)
when
,
when
,
when
,
when
.
If
, let
,
,
.
If
, let
,
,
.
If
, let
,
,
.
If
, let
,
.
Clearly,
.
Then we label the vertex of
as followsIf ![](https://www.scirp.org/html/15-7401498\b7a52f03-afd7-48a1-8083-e7d73d64f0c6.jpg)
,
when
,
when
,
when
,
when
.
If
, let
![](https://www.scirp.org/html/15-7401498\9fad56ab-28f7-491b-b4ca-df0e60eaf95e.jpg)
![](https://www.scirp.org/html/15-7401498\45df9933-5800-4aab-94fc-8d042c1048a8.jpg)
If
, let
![](https://www.scirp.org/html/15-7401498\c5a52555-e173-45c1-a215-c00ab746862e.jpg)
![](https://www.scirp.org/html/15-7401498\1586e063-0456-468a-829c-438dd33b76af.jpg)
If
, let
![](https://www.scirp.org/html/15-7401498\1f843676-ebfc-463b-8fde-4190c4348c85.jpg)
![](https://www.scirp.org/html/15-7401498\ba68a155-06c0-4876-ab3c-36eed9d2e7bf.jpg)
If
, let
![](https://www.scirp.org/html/15-7401498\6316dfd0-0b6d-4007-97c6-6a0e0ca063d6.jpg)
![](https://www.scirp.org/html/15-7401498\87851bfe-03da-4f55-a484-b300a15ab454.jpg)
From aboveIf
,
is the maximum number in
, and
, then
![](https://www.scirp.org/html/15-7401498\da1649f9-1a36-4542-8892-5958fb3a6739.jpg)
If
,
is the maximum number in
, and
, then
![](https://www.scirp.org/html/15-7401498\8bf1526f-5f37-40b8-b600-92be64d0a9c3.jpg)
If
,
is the maximum number in
, and
, then
![](https://www.scirp.org/html/15-7401498\1c020274-053a-4c97-a645-674b6848e285.jpg)
If
,
is the maximum number in
, and
, then
![](https://www.scirp.org/html/15-7401498\2f643e7a-83c6-444e-9aca-b70e42d1d012.jpg)
So
is the maximum number in
, and
, and
.
Obviously, f is a
-
-labeling of GThen
.
3.
-Labeling Number of the Product Graph on Two Fans
Definition 3.1 The Cartesian product of graph G and H, denoted
, which vertex set and edge set are the follows:
![](https://www.scirp.org/html/15-7401498\4eb33d02-21c5-4e2f-909d-0c97c84105ad.jpg)
![](https://www.scirp.org/html/15-7401498\2cf3ad1c-fecf-43d2-ad8b-b4de8fee40ab.jpg)
Theorem 3.1 Let
, if
, then
.
Proof. In
, the other vertices
, In
, the other vertices
![](https://www.scirp.org/html/15-7401498\3cadb12a-67d6-4b50-8925-6518c0f496a7.jpg)
denote the vertex of
, Obviously,
, for
.
We give a
-labeling of G as follows, First, let
![](https://www.scirp.org/html/15-7401498\67ef640a-a5a6-4c64-8dc6-5cff4da6d221.jpg)
We have the maximum labeling number is 2n + 3.
Then let
![](https://www.scirp.org/html/15-7401498\e21871b7-66d0-4a62-aebe-389ef8f43ab0.jpg)
From above,
is the maximum labeling number.
Finally, let
Obviously,
is the maximum labeling number in these
since n ≤ m < 2n, then the maximum labeling number no more than
, and
, so
.