The number of short cycles in Fibonacci cubes. (English) Zbl 1482.05158
Summary: The Fibonacci cube is the subgraph of the hypercube induced by the vertices whose binary string representations do not contain two consecutive 1s. These cubes were presented as an alternative interconnection network. In this paper, we calculate the number of induced paths and cycles of small length in Fibonacci cubes by using the recursive structure of these graphs.
MSC:
| 05C30 | Enumeration in graph theory |
| 05C38 | Paths and cycles |
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
| 68M10 | Network design and communication in computer systems |
| 68R10 | Graph theory (including graph drawing) in computer science |
Software:
OEISReferences:
| [1] | Alizadeh, Y.; Deutsch, E.; Klavžar, S., On the irregularity of π-permutation graphs, Fibonacci cubes, and trees, Bull. Malays. Math. Sci. Soc., 43, 4443-4456 (2020) · Zbl 1451.05038 |
| [2] | Azarija, J.; Klavžar, S.; Rho, Y.; Sim, S., On domination-type invariants of Fibonacci cubes and hypercubes, Ars Math. Contemp., 14, 387-395 (2018) · Zbl 1393.05196 |
| [3] | Choudum, S. A.; Sunitha, V., Augmented cubes, Networks, 40, 2, 71-84 (2002) · Zbl 1019.05052 |
| [4] | Dehghan, A.; Banihashemi, A. H., Counting short cycles in bipartite graphs: a fast technique/algorithm and a hardness result, IEEE Trans. Commun., 68, 3, 1378-1390 (2020) |
| [5] | Dong, Q.; Wang, X., How many triangles and quadrilaterals are there in an n-dimensional augmented cube?, Theor. Comput. Sci., 771, 93-98 (2019) · Zbl 1423.68334 |
| [6] | Eğecioğlu, Ö.; Saygı, E.; Saygı, Z., The irregularity polynomials of Fibonacci and Lucas cubes, Bull. Malays. Math. Sci. Soc., 44, 753-765 (2021) · Zbl 1462.05187 |
| [7] | Flum, J.; Grohe, M., The parameterized complexity of counting problems, (Proc. IEEE Symp. Foundations of Computer Science. Proc. IEEE Symp. Foundations of Computer Science, Vancouver, BC, Canada (Nov. 2002)), 538-547 |
| [8] | Guo, L., Reliability analysis of twisted cubes, Theor. Comput. Sci., 707, 96-101 (2018) · Zbl 1382.68034 |
| [9] | Hsieh, S.-Y.; Huang, H.-W.; Lee, C.-W., \(\{2, 3 \}\)-restricted connectivity of locally twisted cubes, Theor. Comput. Sci., 615, 78-90 (2016) · Zbl 1334.68025 |
| [10] | Hsu, W.-J., Fibonacci cubes—a new interconnection technology, IEEE Trans. Parallel Distrib. Syst., 4, 1, 3-12 (1993) |
| [11] | Klavžar, S., On median nature and enumerative properties of Fibonacci-like cubes, Discrete Math., 299, 1-3, 145-153 (2005) · Zbl 1073.05007 |
| [12] | Klavžar, S., Structure of Fibonacci cubes: a survey, J. Comb. Optim., 25, 505-522 (2013) · Zbl 1273.90173 |
| [13] | Klavžar, S.; Mollard, M., Cube polynomial of Fibonacci and Lucas cube, Acta Appl. Math., 117, 93-105 (2012) · Zbl 1235.05071 |
| [14] | Saygı, E., On the domination number and the total domination number of Fibonacci cubes, Ars Math. Contemp., 16, 245-255 (2019) · Zbl 1416.05216 |
| [15] | Saygı, E.; Eğecioğlu, Ö., q-Cube enumerator polynomial of Fibonacci cubes, Discrete Appl. Math., 226, 127-137 (2017) · Zbl 1365.05214 |
| [16] | Wang, X.; Fan, J.; Jia, X.; Zhang, S.; Yu, J., Embedding meshes into twisted-cubes, Inf. Sci., 181, 14, 3085-3099 (2011) · Zbl 1218.68111 |
| [17] | Yang, X.; Evans, D. J.; Megson, G. M., The locally twisted cubes, Int. J. Comput. Math., 82, 4, 401-413 (2005) · Zbl 1097.68522 |
| [18] | (2021), OEIS Foundation Inc., The on-line encyclopedia of integer sequences · Zbl 1494.68308 |
| [19] | Zagaglia Salvi, N., On the existence of cycles of every even length on generalized Fibonacci cubes, Matematiche, 51, suppl., 241-251 (1996) · Zbl 0898.05046 |
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.
