×

The (vertex-)monochromatic index of a graph. (English) Zbl 1379.05038

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.

MSC:

05C15 Coloring of graphs and hypergraphs
05C40 Connectivity
05C05 Trees
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bondy JA, Murty USR (1976) Graph theory with applications. The Macmillan Press, London · Zbl 1226.05083 · doi:10.1007/978-1-349-03521-2
[2] Cai Q, Li X, Wu D (2015a) Erdös-Gallai-type results for colorful monochromatic connectivity of a graph. J Comb Optim. doi:10.1007/s10878-015-9938-y, in press · Zbl 1358.05097
[3] Cai Q, Li X, Wu D (2015b) Some extremal results on the colorful monochromatic vertex-connectivity of a graph. arXiv:1503.08941 · Zbl 1393.05162
[4] Caro Y, Lev A, Roditty Y, Tuza Z, Yuster R (2008) On rainbow connection. Electron J Combin 15(1):R57 · Zbl 1181.05037
[5] Caro Y, Yuster R (2011) Colorful monochromatic connectivity. Discrete Math 311:1786-1792 · Zbl 1223.05065 · doi:10.1016/j.disc.2011.04.020
[6] Chartrand G, Johns G, McKeon K, Zhang P (2008) Rainbow connection in graphs. Math Bohem 133:85-98 · Zbl 1199.05106
[7] Chen L, Li X, Lian H (2013) Nordhaus-Gaddum-type theorem for rainbow connection number of graphs. Graphs Combin 29:1235-1247 · Zbl 1272.05044 · doi:10.1007/s00373-012-1183-x
[8] Garey MR, Johnson DS (1979) Computers and intractability. Freeman, New York · Zbl 0411.68039
[9] Harary F, Haynes TW (1996) Nordhaus-Gaddum inequalities for domination in graphs. Discrete Math 155:99-105 · Zbl 0856.05053 · doi:10.1016/0012-365X(94)00373-Q
[10] Krivelevich M, Yuster R (2010) The rainbow connection of a graph is (at most) reciprocal to its minimum degree. J Graph Theory 63(3):185-191 · Zbl 1193.05079
[11] Laskar R, Peters K (1985) Vertex and edge domination parameters in graphs. Congr Numer 48:291-305 · Zbl 0622.05056
[12] Li X, Shi Y, Sun Y (2013) Rainbow connections of graphs: a survey. Graphs Combin 29:1-38 · Zbl 1258.05058 · doi:10.1007/s00373-012-1243-2
[13] Li X, Sun Y (2012) Rainbow connections of graphs. Springer briefs in math. Springer, New York · Zbl 1250.05066 · doi:10.1007/978-1-4614-3119-0
[14] Nordhaus EA, Gaddum JW (1956) On complementary graphs. Am Math Monthly 63:175-177 · Zbl 0070.18503 · doi:10.2307/2306658
[15] Zhang L, Wu B (2005) The Nordhaus-Gaddum-type inequalities of some chemical indices. MATCH Commun Math Comput Chem 54:189-194 · Zbl 1084.05072
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.