Total monochromatic connection of graphs

DOI10.1016/J.DISC.2016.08.020MaRDI QIDQ2374173zbMATH OpenOpenAlexFDO

Authors Hui Jiang, Yingying Zhang, Xueliang Li

Publication date 14 December 2016

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

spanning tree with maximum number of leavestotal monochromatic connectiontotal-colored graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: A graph is said to be {it total-colored} if all the edges and the vertices of the graph are colored. A path in a total-colored graph is a {it total monochromatic path} if all the edges and internal vertices on the path have the same color. A total-coloring of a graph is a {it total monochromatically-connecting coloring} ({it TMC-coloring}, for short) if any two vertices of the graph are connected by a total monochromatic path of the graph. For a connected graph $G$, the {it total monochromatic connection number}, denoted by $tmc(G)$, is defined as the maximum number of colors used in a TMC-coloring of $G$. These concepts are inspired by the concepts of monochromatic connection number $mc(G)$, monochromatic vertex connection number $mvc(G)$ and total rainbow connection number $trc(G)$ of a connected graph $G$. Let $l(T)$ denote the number of leaves of a tree $T$, and let $$ $T$ is a spanning tree of $G$ $$ for a connected graph $G$. In this paper, we show that there are many graphs $G$ such that $tmc(G)=m-n+2+l(G)$, and moreover, we prove that for almost all graphs $G$, $tmc(G)=m-n+2+l(G)$ holds. Furthermore, we compare $tmc(G)$ with $mvc(G)$ and $mc(G)$, respectively, and obtain that there exist graphs $G$ such that $tmc(G)$ is not less than $mvc(G)$ and vice versa, and that $tmc(G)=mc(G)+l(G)$ holds for almost all graphs. Finally, we prove that $tmc(G)leqmc(G)+mvc(G)$, and the equality holds if and only if $G$ is a complete graph.

Recommendations

• More on total monochromatic connection of graphs.
• Erdős-Gallai-type results for colorful monochromatic connectivity of a graph
• Further results on the total monochromatic connectivity of graphs
• Erdős-Gallai-type results for total monochromatic connection of graphs
• Extremal graphs with maximum monochromatic connectivity

Cites work

• Colorful monochromatic connectivity
• Erdős-Gallai-type results for colorful monochromatic connectivity of a graph
• Graph theory
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2123255 (Why is no real title available?)
• More on the colorful monochromatic connectivity
• Properties of almost all graphs and complexes
• Rainbow vertex \(k\)-connection in graphs
• Some extremal results on the colorful monochromatic vertex-connectivity of a graph
• Total rainbow \(k\)-connection in graphs

Cited in

(5)

• Further results on the total monochromatic connectivity of graphs
• Monochromatic \(k\)-edge-connection colorings of graphs
• Erdős-Gallai-type results for total monochromatic connection of graphs
• More on total monochromatic connection of graphs.
• Highly connected monochromatic subgraphs of two-colored complete graphs

This page was built for publication: Total monochromatic connection of graphs

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