The (k, )-proper index of graphs

DOI10.1007/S10878-018-0307-5zbMATH Open1391.05103arXiv1606.03872OpenAlexW2962755022MaRDI QIDQ721930FDOQ721930

Authors: Hong Chang, Colton Magnant, Zhongmei Qin, Xueliang Li

Publication date: 20 July 2018

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1606.03872

Recommendations

zbMATH Keywords

random graphs threshold function proper index proper tree

Mathematics Subject Classification ID

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)

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)