Tight Nordhaus-Gaddum-type upper bound for total-rainbow connection number of graphs

DOI10.1007/S00025-017-0753-XMaRDI QIDQ681264zbMATH OpenOpenAlexFDO

Authors Colton Magnant, Jingshu Zhang, Wenjing Li, Xueliang Li

Publication date 30 January 2018

Published in Results in Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

complementary graphNordhaus-Gaddum-type upper boundtotal-rainbow connection numbertotal-rainbow path

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Connectivity (05C40)

Abstract: A graph is said to be emph{total-colored} if all the edges and the vertices of the graph are colored. A total-colored graph is emph{total-rainbow connected} if any two vertices of the graph are connected by a path whose edges and internal vertices have distinct colors. For a connected graph $G$, the emph{total-rainbow connection number} of $G$, denoted by $trc(G)$, is the minimum number of colors required in a total-coloring of $G$ to make $G$ total-rainbow connected. In this paper, we first characterize the graphs having large total-rainbow connection numbers. Based on this, we obtain a Nordhaus-Gaddum-type upper bound for the total-rainbow connection number. We prove that if $G$ and $overlineG$ are connected complementary graphs on $n$ vertices, then $trc(G)+trc(overlineG)leq2n$ when $ngeq6$ and $trc(G)+trc(overlineG)leq2n+1$ when $n=5$. Examples are given to show that the upper bounds are sharp for $ngeq5$. This completely solves a conjecture in [Y. Ma, Total rainbow connection number and complementary graph, Results in Mathematics 70(1-2)(2016), 173-182].

Recommendations

• Some upper bounds for the total-rainbow connection number of graphs.
• Nordhaus-Gaddum-type theorem for total-proper connection number of graphs
• Total rainbow connection number and complementary graph
• Upper bounds for the total rainbow connection of graphs
• On rainbow total-coloring of a graph

Cites work

• A survey of Nordhaus-Gaddum type relations
• Graph theory with applications
• scientific article; zbMATH DE number 5015716 (Why is no real title available?)
• scientific article; zbMATH DE number 68910 (Why is no real title available?)
• scientific article; zbMATH DE number 3338394 (Why is no real title available?)
• Nordhaus-Gaddum inequalities for domination in graphs
• Nordhaus-Gaddum-type results for the generalized edge-connectivity of graphs
• Nordhaus-Gaddum-type theorem for rainbow connection number of graphs
• On Complementary Graphs
• On rainbow total-coloring of a graph
• Proper connection numbers of complementary graphs
• Rainbow connection in graphs
• Rainbow connection of graphs with diameter 2
• The Diameter of a Graph and its Complement
• Tight Nordhaus-Gaddum-type upper bound for total-rainbow connection number of graphs
• Total rainbow \(k\)-connection in graphs
• Total rainbow connection number and complementary graph

Cited in

(10)

• Rainbow total-coloring of complementary graphs and Erdős-Gallai type problem for the rainbow total-connection number
• Nordhaus-Gaddum-type theorem for total-proper connection number of graphs
• Nordhaus-Gaddum and other bounds for the chromatic edge-stability number
• scientific article; zbMATH DE number 6719578 (Why is no real title available?)
• Total rainbow connection number and complementary graph
• Upper bounds for the total rainbow connection of graphs
• On rainbow total-coloring of a graph
• Some upper bounds for the total-rainbow connection number of graphs.
• Nordhaus-Gaddum type inequalities for tree covering numbers on unitary Cayley graphs of finite rings
• Tight Nordhaus-Gaddum-type upper bound for total-rainbow connection number of graphs

This page was built for publication: Tight Nordhaus-Gaddum-type upper bound for total-rainbow connection number of graphs

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