The (vertex-)monochromatic index of a graph

DOI10.1007/S10878-016-0048-2MaRDI QIDQ2012896zbMATH OpenOpenAlexFDO

Publication date 3 August 2017

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

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

\(k\)-monochromatic index \(k\)-monochromatic vertex index monochromatic tree NP-complete problem

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: A tree

T

in an edge-colored graph

H

is called a emph{monochromatic tree} if all the edges of

T

have the same color. For

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

, a emph{monochromatic

S

-tree} in

H

is a monochromatic tree of

H

containing the vertices of

S

. For a connected graph

G

and a given integer

k

with

2 l e q k l e q | V (G) |

, the emph{

k

-monochromatic index

m x_{k} (G)

} of

G

is the maximum number of colors needed such that for each subset

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

of

k

vertices, there exists a monochromatic

S

-tree. In this paper, we prove that for any connected graph

G

,

m x_{k} (G) = | E (G) | - | V (G) | + 2

for each

k

such that

3 l e q k l e q | V (G) |

. A tree

T

in a vertex-colored graph

H

is called a emph{vertex-monochromatic tree} if all the internal vertices of

T

have the same color. For

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

, a emph{vertex-monochromatic

S

-tree} in

H

is a vertex-monochromatic tree of

H

containing the vertices of

S

. For a connected graph

G

and a given integer

k

with

2 l e q k l e q | V (G) |

, the emph{

k

-monochromatic vertex-index

m v x_{k} (G)

} of

G

is the maximum number of colors needed such that for each subset

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

of

k

vertices, there exists a vertex-monochromatic

S

-tree. We show that for a given a connected graph

G

, and a positive integer

L

with

L l e q | V (G) |

, to decide whether

m v x_{k} (G) g e q L

is NP-complete for each integer

k

such that

2 l e q k l e q | V (G) |

. We also obtain some Nordhaus-Gaddum-type results for the

k

-monochromatic vertex-index.

Review text

Let \(G\) be an edge colored graph, let \(k\) be an integer such that \(2\leq k\leq |V(G)|\) and let \(S\) be a subset of \(V(G)\) of cardinality \(k\). A monochromatic \(S\)-tree is a tree that contains all vertices of \(S\) and all edges of \(T\) are of the same color. The \(k\)-monochromatic index \(\mathrm{mx}_k(G)\) of \(G\) is the maximum number of colors, such that for each \(S\) there exists a monochromatic \(S\)-tree. This invariant is a generalization of monochromatic connection number \(\mathrm{mc}(G)\) with the connection \(\mathrm{mc}(G)=\mathrm{mx}_2(G)\). In the first part of present work, authors prove that \(\mathrm{mx}_k(G)=|E(G)|-|V(G)|+2\) for each \(k\geq 3\) and any connected graph \(G\). The second part is devoted to \(k\)-monochromatic vertex index \(\mathrm{mvx}_k(G)\) of a graph \(G\). The difference in the definitions is that we observe vertex colored graphs and all inner vertices of a monochromatic \(S\)-tree have the same color. This problem is much harder as it is a NP-complete problem for every \(k\), \(2\leq k\leq |V(G)|\), to decide whether \(\mathrm{mvx}_k(G)\geq \ell\) where \(\ell\leq |V(G)|\), as presented by the authors.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: The (vertex-)monochromatic index of a graph

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