[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

More on the Colorful Monochromatic Connectivity

  • Published:
Bulletin of the Malaysian Mathematical Sciences Society Aims and scope Submit manuscript

Abstract

An edge-coloring of a connected graph is a monochromatically-connecting coloring (MC-coloring, for short) if there is a monochromatic path joining any two vertices, which was introduced by Caro and Yuster. Let mc(G) denote the maximum number of colors used in an MC-coloring of a graph G. Note that an MC-coloring does not exist if G is not connected, in which case we simply let \(mc(G)=0\). In this paper, we characterize all connected graphs of size m with \(mc(G)=1, 2, 3, 4\), \(m-1\), \(m-2\) and \(m-3\), respectively. We use G(n, p) to denote the Erdős-Rényi random graph model, in which each of the \(\left( {\begin{array}{c}n\\ 2\end{array}}\right) \) pairs of vertices appears as an edge with probability p independent from other pairs. For any function f(n) satisfying \(1\le f(n)<\frac{1}{2}n(n-1)\), we show that if \(\ell n \log n\le f(n)<\frac{1}{2}n(n-1)\), where \(\ell \in \mathbb {R}^+\), then \(p=\frac{f(n)+n\log \log n}{n^2}\) is a sharp threshold function for the property \(mc\left( G\left( n,p\right) \right) \ge f(n)\); if \(f(n)=o(n\log n)\), then \(p=\frac{\log n}{n}\) is a sharp threshold function for the property \(mc\left( G\left( n,p\right) \right) \ge f(n)\).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

References

  1. Alon, N., Spencer, J.: The Probabilistic Method. Wiley-Interscience Series in Discrete Mathematics and Optimization, 3rd edn. Wiley, Hoboken (2008)

    Book  MATH  Google Scholar 

  2. Bondy, J.A., Murty, U.S.R.: Graph Theory, GTM 244. Springer, Berlin (2008)

    Book  MATH  Google Scholar 

  3. Bollobás, B., Thomason, A.: Threshold functions. Combinatorica 7, 35–38 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  4. Cai, Q., Li, X., Wu, D.: Erdős-Gallai-type results for colorful monochromatic connectivity of a graph. J. Comb. Optim. doi: 10.1007/s10878-015-9938-y

  5. Caro, Y., Lev, A., Roditty, Y., Tuza, Z., Yuster, R.: On rainbow connection. Electron. J. Comb. 15, #R57 (2008)

    MathSciNet  MATH  Google Scholar 

  6. Caro, Y., Yuster, R.: Colorful monochromatic connectivity. Discrete Math. 311, 1786–1792 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  7. Chen, L., Li, X., Yang, K., Zhao, Y.: The 3-rainbow index of a graph. Discuss. Math. Graph Theory 35, 81–94 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  8. Chartrand, G., Johns, G.L., McKeon, K.A., Zhang, P.: Rainbow connection in graphs. Math. Bohem. 133, 85–98 (2008)

    MathSciNet  MATH  Google Scholar 

  9. Chartrand, G., Johns, G., McKeon, K., Zhang, P.: The rainbow connectivity of a graph. Networks 54(2), 75–81 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  10. Erdös, P., Rényi, A.: On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. 5, 17–61 (1960)

    MathSciNet  MATH  Google Scholar 

  11. Friedgut, E., Kalai, G.: Every monotone graph property has a sharp threshold. Proc. Am. Math. Soc. 124, 2993–3002 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  12. He, J., Liang, H.: On rainbow-\(k\)-connectivity of random graphs. Inf. Process. Lett. 112, 406–410 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  13. Huang, X., Li, X., Shi, Y.: Note on the hardness of rainbow connections for planar and line graphs. Bull. Malays. Math. Sci. Soc. 38, 1235–1241 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  14. Li, X., Shi, Y., Sun, Y.: Rainbow connections of graphs: a survey. Graph Combin. 29, 1–38 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  15. Li, X., Sun, Y.: Rainbow Connections of Graphs. Springer Briefs in Mathematics. Springer, New York (2012)

    Book  MATH  Google Scholar 

  16. Li, X., Sun, Y., Zhao, Y.: Characterization of graphs with rainbow connection number \(m-2\) and \(m-3\). Aust. J. Comb. 60, 306–313 (2014)

    MathSciNet  MATH  Google Scholar 

  17. Li, X., Schiermeyer, I., Yang, K., Zhao, Y.: Graphs with 3-rainbow index \(n-1\) and \(n-2\). Discuss. Math. Graph Theory 35(1), 105–120 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  18. Li, X., Schiermeyer, I., Yang, K., Zhao, Y.: Graphs with 4-rainbow index 3 and \(n-1\). Discuss. Math. Graph Theory 35(2), 387–398 (2015)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

This worl was supported by NSFC Nos. 11371205 and 11531011, and PCSIRT. The authors are very grateful to the reviewers for their valuable suggestions and comments, which helped to improve the presentation of the paper.

Author information

Authors and Affiliations

  1. Center for Combinatorics and LPMC-TJKLC, Nankai University, Tianjin, 300071, China

    Ran Gu, Xueliang Li, Zhongmei Qin & Yan Zhao

Authors
  1. Ran Gu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xueliang Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Zhongmei Qin
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Yan Zhao
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Xueliang Li.

Additional information

Communicated by Sandi Klavžar.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Gu, R., Li, X., Qin, Z. et al. More on the Colorful Monochromatic Connectivity. Bull. Malays. Math. Sci. Soc. 40, 1769–1779 (2017). https://doi.org/10.1007/s40840-015-0274-2

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s40840-015-0274-2

Keywords

Mathematics Subject Classification

Search

Navigation