The (k, )-proper index of graphs

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: A tree

T

in an edge-colored graph is called a {it proper tree} if no two adjacent edges of

T

receive the same color. Let

G

be a connected graph of order

n

and

k

be an integer with

2 l e q k l e q n

. For

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

and

| S | g e 2

, an

S

-tree is a tree containing the vertices of

S

in

G

. Suppose

T_{1}, T_{2}, l d o t s, T_{e} l l

is a set of

S

-trees, they are called emph{internally disjoint} if

E (T_{i}) c a p E (T_{j}) = e m p t y s e t

and

V (T_{i}) c a p V (T_{j}) = S

for

1 l e q i e q j l e q e l l

. For a set

S

of

k

vertices of

G

, the maximum number of internally disjoint

S

-trees in

G

is denoted by

k a p p a (S)

. The

k a p p a

-connectivity

k a p p a_{k} (G)

of

G

is defined by

is a

k

-subset of

. For a connected graph

G

of order

n

and for two integers

k

and

e l l

with

2 l e k l e n

and

1 l e q e l l l e q k a p p a_{k} (G)

, the emph{

(k, e l l)

-proper index

p x_{k, e l l} (G)

} of

G

is the minimum number of colors that are needed in an edge-coloring of

G

such that for every

k

-subset

S

of

V (G)

, there exist

e l l

internally disjoint proper

S

-trees connecting them. In this paper, we show that for every pair of positive integers

k

and

e l l

with

k g e 3

, there exists a positive integer

N_{1} = N_{1} (k, e l l)

such that

p x_{k, e l l} (K_{n}) = 2

for every integer

n g e N_{1}

, and also there exists a positive integer

N_{2} = N_{2} (k, e l l)

such that

p x_{k, e l l} (K_{m, n}) = 2

for every integer

n g e N_{2}

and

m = O (n^{r}) (r g e 1)

. In addition, we show that for every

p g e c s q r t [k] f r a c l o g_{a} n n

(

c g e 5

),

p x_{k, e l l} (G_{n, p}) l e 2

holds almost surely, where

G_{n, p}

is the Erd"{o}s-R'{e}nyi random graph model.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: The \((k,\ell )\)-proper index of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q721930)