Is there any polynomial upper bound for the universal labeling of graphs?

Abstract: A {it universal labeling} of a graph

G

is a labeling of the edge set in

G

such that in every orientation

e l l

of

G

for every two adjacent vertices

v

and

u

, the sum of incoming edges of

v

and

u

in the oriented graph are different from each other. The {it universal labeling number} of a graph

G

is the minimum number

k

such that

G

has {it universal labeling} from

1, 2, l d o t s, k

denoted it by

o v e r r i g h t a r r o w c h i_{u} (G)

. We have

2 D e l t a (G) - 2 l e q o v e r r i g h t a r r o w c h i_{u} (G) l e q 2^{D e l t a (G)}

, where

D e l t a (G)

denotes the maximum degree of

G

. In this work, we offer a provocative question that is:" Is there any polynomial function

f

such that for every graph

G

,

o v e r r i g h t a r r o w c h i_{u} (G) l e q f (D e l t a (G))

?". Towards this question, we introduce some lower and upper bounds on their parameter of interest. Also, we prove that for every tree

T

,

o v e r r i g h t a r r o w c h i_{u} (T) = m a t h c a l O (D e l t a^{3})

. Next, we show that for a given 3-regular graph

G

, the universal labeling number of

G

is 4 if and only if

G

belongs to Class 1. Therefore, for a given 3-regular graph

G

, it is an

m a t h b f N P

-complete to determine whether the universal labeling number of

G

is 4. Finally, using probabilistic methods, we almost confirm a weaker version of the problem.

Recommendations

Cites Work

Cited In (5)

Uses Software

This page was built for publication: Is there any polynomial upper bound for the universal labeling of graphs?