Upper bounds for the total rainbow connection of graphs

DOI10.1007/s10878-015-9874-xzbMath1347.05068arXiv1501.01806MaRDI QIDQ328717

Yingying Zhang, Hui Jiang, Xue Liang Li

Publication date: 20 October 2016

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

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

zbMATH Keywords

minimum degree; total rainbow connection; 2-step dominating set; total-colored graph

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

05C40: Connectivity

05D40: Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)

Related Items

On various (strong) rainbow connection numbers of graphs, On the total proper connection of graphs, Total rainbow connection numbers of some special graphs, Erdős-Gallai-type results for total monochromatic connection of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Further hardness results on the rainbow vertex-connection number of graphs
• Total rainbow \(k\)-connection in graphs
• Hardness and algorithms for rainbow connection
• The complexity of determining the rainbow vertex-connection of a graph
• On rainbow connection
• Spanning trees in graphs of minimum degree 4 or 5
• Rainbow connections of graphs: a survey
• On the rainbow vertex-connection
• Rainbow connection number and connected dominating sets
• Spanning Trees with Many Leaves
• Rainbow connection in graphs
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree