×

How many triangles and quadrilaterals are there in an \(n\)-dimensional augmented cube? (English) Zbl 1423.68334

The article counts how many triangles and quadrilaterals are there in an \(n\)-dimensional augmented cube. It turns out that the number of triangles is equal to \(2^{n} (n-1)\) (for \(n=3,4,5,\ldots )\), and the number of quadrilaterals is equal to \(2^{n-2} (2n^{2} +5n-11)\) (for \(n=3,4,5,\ldots \)). The authors argue that the results indicate the prospects for the use of transmission network designs based on an \(n\)-dimensional augmented cube. The reviewer believes that this is obvious without the obtained formulas, but the design and construction of such networks is a very complex technical, not mathematical problem.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C30 Enumeration in graph theory
68M10 Network design and communication in computer systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Xu, J.-M., Topological Structure and Analysis of Interconnection Networks (2001), Kluwer Academic Publishers · Zbl 1046.68026
[2] Xu, J.-M.; Ma, M., Survey on path and cycle embedding in some networks, Front. Math. China, 4, 2, 217-252 (2009) · Zbl 1176.90081
[3] Axenovich, M.; Martin, R., A note on short cycles in a hypercube, Discrete Math., 306, 18, 2212-2218 (2006) · Zbl 1104.05034
[4] Dong, Q.; Zhao, Q.; An, Y., The hamiltonicity of generalized honeycomb torus networks, Inform. Process. Lett., 115, 2, 104-111 (2015) · Zbl 1302.68214
[5] Choudum, S. A.; Sunitha, V., Augmented cubes, Networks, 40, 2, 71-84 (2002) · Zbl 1019.05052
[6] Harary, F.; Hayes, J. P.; Wu, H. J., A survey of the theory of hypercube graphs, Comput. Math. Appl., 15, 4, 277-289 (1988) · Zbl 0645.05061
[7] Lin, C. K.; Zhang, L.; Fan, J.; Wang, D., Structure connectivity and substructure connectivity of hypercubes, Theoret. Comput. Sci., 634, 97-107 (2016) · Zbl 1339.68208
[8] Park, J.-H., Paired many-to-many disjoint path covers in restricted hypercube-like graphs, Theoret. Comput. Sci., 634, 24-34 (2016) · Zbl 1339.68211
[9] Cheng, B.; Wang, D.; Fan, J., Constructing completely independent spanning trees in crossed cubes, Discrete Appl. Math., 219, 100-109 (2017) · Zbl 1354.05026
[10] Hsieh, S.-Y.; Huang, H.-W.; Lee, C.-W., {2, 3}-restricted connectivity of locally twisted cubes, Theoret. Comput. Sci., 615, 78-90 (2016) · Zbl 1334.68025
[11] Hsieh, S.-Y.; Shiu, J.-Y., Cycle embedding of augmented cubes, Appl. Math. Comput., 191, 2, 314-319 (2007) · Zbl 1193.05098
[12] Wang, Y.; Shen, H.; Fan, J., Edge-independent spanning trees in augmented cubes, Theoret. Comput. Sci., 670, 23-32 (2017) · Zbl 1359.68234
[13] Fan, J.; Jia, X., Embedding meshes into crossed cubes, Inform. Sci., 177, 15, 3151-3160 (2007) · Zbl 1122.68013
[14] Lin, L.; Xu, L.; Zhou, S.; Xiang, Y., Trustworthiness-hypercube-based reliable communication in mobile social networks, Inform. Sci., 369, 34-50 (2016)
[15] Yang, X.; Evans, D. J.; Megson, G. M., The locally twisted cubes, Int. J. Comput. Math., 82, 4, 401-413 (2005) · Zbl 1097.68522
[16] Wang, X.; Fan, J.; Jia, X.; Zhang, S.; Yu, J., Embedding meshes into twisted-cubes, Inform. Sci., 181, 14, 3085-3099 (2011) · Zbl 1218.68111
[17] Yang, X.; Wang, L.; Yang, L., Optimal broadcasting for locally twisted cubes, Inform. Process. Lett., 112, 4, 129-134 (2012) · Zbl 1237.68019
[18] Guo, L., Reliability analysis of twisted cubes, Theoret. Comput. Sci., 707, 96-101 (2018) · Zbl 1382.68034
[19] Liu, Z.; Fan, J.; Jia, X., Complete binary trees embeddings in Möbius cubes, J. Comput. System Sci., 82, 2, 260-281 (2016) · Zbl 1346.68026
[20] Xu, J.-M.; Ma, M.; Lu, M., Paths in Möbius cubes and crossed cubes, Inform. Process. Lett., 97, 3, 94-97 (2006) · Zbl 1177.05062
[21] Mekuta, K.; Gregor, P., Edge-fault-tolerant hamiltonicity of augmented cubes, Electron. Notes Discrete Math., 40, 239-243 (2013)
[22] Ma, M.; Liu, G.; Xu, J.-M., The super connectivity of augmented cubes, Inform. Process. Lett., 106, 2, 59-63 (2008) · Zbl 1186.68339
[23] Graham, N.; Harary, F., The number of perfect matchings in a hypercube, Appl. Math. Lett., 1, 1, 45-48 (1988) · Zbl 0626.05043
[24] Ostergard, P. R.J.; Pettersson, V. H., Enumerating perfect matchings in n-cubes, Order, 30, 3, 821-835 (2013) · Zbl 1276.05095
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.