World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

Fractional Matching Preclusion for Data Center Networks

    An edge subset F of G is a fractional matching preclusion set (FMP set for short) if GF has no fractional perfect matchings. The fractional matching preclusion number (FMP number for short) of G, denoted by fmp(G), is the minimum size of FMP sets of G. A set F of edges and vertices of G is a fractional strong matching preclusion set (FSMP set for short) if GF has no fractional perfect matchings. The fractional strong matching preclusion number (FSMP number for short) of G, denoted by fsmp(G), is the minimum size of FSMP sets of G. Data center networks have been proposed for data centers as a server-centric interconnection network structure, which can support millions of servers with high network capacity by only using commodity switches. In this paper, we obtain the FMP number and the FSMP number for data center networks Dn,k, and show that fmp(Dn,k)=n+k1 for n2, k0 and fsmp(Dn,k)=n+k1 for n6, k1. In addition, all the optimal fractional strong matching preclusion sets of these graphs are categorized.

    Communicated by Eddie Cheng

    PACS: AMS Subject Classification 2010: 05C05, 05C12, 05C76

    References

    • 1. J. A. Bondy, U. S. R. Murty, Graph Theory, GTM244 (Springer, 2008). CrossrefGoogle Scholar
    • 2. R. C. Birgham, F. Harary, E. C. Violin, J. Yellen, Perfect matching preclusion, Congressus Numerantium 174 (2005) 185–192. Google Scholar
    • 3. E. Cheng, L. Lipták, Matching preclusion for some interconnection networks, Networks 50 (2007) 173–180. Crossref, ISIGoogle Scholar
    • 4. E. Cheng, L. Lesniak, M. J. Lipman, L. Lipták, Matching preclusion for alternating group graphs and their generalizations, Int. J. Found. Comp. Sci. 19 (2008) 1413–1437. Link, ISIGoogle Scholar
    • 5. E. Cheng, L. Lesniak, M. J. Lipman, L. Lipták, Conditional Matching preclusion sets, Inf. Sci. 179 (2009) 1092–1101. Crossref, ISIGoogle Scholar
    • 6. E. Cheng, S. Shah, V. Shah, D. E. Steffy, Strong matching preclusion for augmented cubes, Theor. Comput. Sci. 491 (2013) 71–77. Crossref, ISIGoogle Scholar
    • 7. J.-S. Jwo, S. Lakshmivarahan, S. K. Dhall, A new class of interconnection networks based on the alternating group, Networks 23 (1993) 315–326. Crossref, ISIGoogle Scholar
    • 8. Y. Liu, W. Liu, Fractional matching preclusion of graphs, J. Comb. Optim. 34 (2017) 522–533. Crossref, ISIGoogle Scholar
    • 9. H. Lü, T. Wu, Super edge-connectivity and matching preclusion of data center networks, http s://arxiv.org/abs/1807.05224. Google Scholar
    • 10. T. Ma, Y. Mao, E. Cheng, C. Melekian, Fractional matching preclusion for (burnt) pancake graphs, I-SPAN. 00030 (2018) 133–141. Google Scholar
    • 11. T. Ma, Y. Mao, E. Cheng, P. Han, A note on the strong matching preclusion problem for data center networks, submitted. Google Scholar
    • 12. T. Ma, Y. Mao, E. Cheng, J. Wang, Fractional matching preclusion for arrangement graphs, Discrete Appl. Math. 270 (2019) 181–189. Crossref, ISIGoogle Scholar
    • 13. T. Ma, Y. Mao, E. Cheng, J. Wang, Fractional matching preclusion for (n, k)-Star Graphs, Parallel Process. Lett. 28(4) (2018) 1850017. Link, ISIGoogle Scholar
    • 14. J.-H. Park, I. Ihm, Strong matching preclusion, Theor. Comput. Sci. 412 (2011) 6409–6419. Crossref, ISIGoogle Scholar
    • 15. X. Wang, A. Erickson, J. Fan, X. Jia, Hamiltonian properties of DCell networks, Comput. J. 58(11) (2015) 2944–2955. Crossref, ISIGoogle Scholar
    • 16. X. Wang, J. Fan, J. Zhou, C.-K. Lin, The restricted h-connectivity of the data center network DCell, Discrete Appl. Math. 203 (2016) 144–157. Crossref, ISIGoogle Scholar
    • 17. E. R. Scheinerman, D. H. Ullman, Fractional Graph Theory: A Rational Approach to the Theory of Graphs (John Wiley, New York, 1997). Google Scholar