The k-proper index of complete bipartite and complete multipartite graphs

Publication date: 29 November 2017

Abstract: Let

G

be a nontrivial connected graph of order

n

with an edge-coloring

c : E (G) i g h t a r r o w 1, 2, d o t s, t

,

t i n m a t h b b N

, where adjacent edges may be colored with the same color. A tree

T

in

G

is a emph{proper tree} if no two adjacent edges of it are assigned the same color. Let

k

be a fixed integer with

2 l e q k l e q n

. For a vertex subset

S s u b s e t e q V (G)

with

| S | g e q 2

, a tree is called an emph{

S

-tree} if it connects

S

in

G

. A emph{

k

-proper coloring} of

G

is an edge-coloring of

G

having the property that for every set

S

of

k

vertices of

G

, there exists a proper

S

-tree

T

in

G

. The minimum number of colors that are needed in a

k

-proper coloring of

G

is defined as the emph{

k

-proper index} of

G

, denoted by

p x_{k} (G)

. In this paper, we determine the 3-proper index of all complete bipartite and complete multipartite graphs and partially determine the

k

-proper index of them for

k g e q 4

.

Recommendations

Cited In (4)

This page was built for publication: The $k$-proper index of complete bipartite and complete multipartite graphs