Sigma partitioning: complexity and random graphs

Abstract: A

e x t i t s i g m a p a r t i t i o n i n g

of a graph

G

is a partition of the vertices into sets

P_{1}, l d o t s, P_{k}

such that for every two adjacent vertices

u

and

v

there is an index

i

such that

u

and

v

have different numbers of neighbors in

P_{i}

. The

e x t i t s i g m a n u m b e r

of a graph

G

, denoted by

s i g m a (G)

, is the minimum number

k

such that

G

has a sigma partitioning

P_{1}, l d o t s, P_{k}

. Also, a

e x t i t l u c k y l a b e l i n g

of a graph

G

is a function

e l l : V (G) i g h t a r r o w m a t h b b N

, such that for every two adjacent vertices

v

and

u

of

G

,

s u m_{w s i m v} e l l (w) e q s u m_{w s i m u} e l l (w)

(

x s i m y

means that

x

and

y

are adjacent). The

e x t i t l u c k y n u m b e r

of

G

, denoted by

e t a (G)

, is the minimum number

k

such that

G

has a lucky labeling

e l l : V (G) i g h t a r r o w m a t h b b N_{k}

. It was conjectured in [Inform. Process. Lett., 112(4):109--112, 2012] that it is

m a t h b f N P

-complete to decide whether

e t a (G) = 2

for a given 3-regular graph

G

. In this work, we prove this conjecture. Among other results, we give an upper bound of five for the sigma number of a uniformly random graph.

Recommendations

Cited in

(6)

This page was built for publication: Sigma partitioning: complexity and random graphs