Elif SAYGI, Zülfükar SAYGI, Ömer EĞECİOĞLU

On the chromatic polynomial and the domination number of k-Fibonacci cubes

Fibonacci cubes are defined as subgraphs of hypercubes, where the vertices are those without two consecutive 1’s in their binary string representation. k -Fibonacci cubes are in turn special subgraphs of Fibonacci cubes obtained by eliminating certain edges. This elimination is carried out at the step analogous to where the fundamental recursion is used to construct Fibonacci cubes themselves from the two previous cubes by link edges. In this work, we calculate the vertex chromatic polynomial of k -Fibonacci cubes for k = 1, 2. We also determine the domination number and the total domination number of k -Fibonacci cubes for n, k ≤ 12 by using an integer programming formulation.

PDF

___

[1] Azarija J, Klavžar S, Rho Y, Sim S. On domination-type invariants of Fibonacci cubes and hypercubes. Ars Mathematica Contemporanea 2018; 14: 387-395. doi: 10.26493/1855-3974.1172.bae
[2] Castro A, Klavžar S, Mollard M, Rho Y. On the domination number and the 2-packing number of Fibonacci cubes and Lucas cubes. Computers & Mathematics with Applications 2011; 61: 2655-2660. doi: 10.1016/j.camwa.2011.03.012
[3] Egiazarian K, Astola J. On generalized Fibonacci cubes and unitary transforms. Applicable Algebra in Engineering, Communication and Computing 1997; 8: 371-377. doi: 10.1007/s002000050074
[4] Eğecioğlu Ö, Saygı E, Saygı Z. k -Fibonacci cubes: A family of subgraphs of Fibonacci cubes. International Journal of Foundations of Computer Science 2020; 31 (5): 639-661. doi: 10.1142/S0129054120500318
[5] Hsu WJ. Fibonacci cubes – a new interconnection technology. IEEE Transactions on Parallel and Distributed Systems 1993; 4: 3-12. doi: 10.1109/71.205649
[6] Ilić A, Milošević M. The parameters of Fibonacci and Lucas cubes. Ars Mathematica Contemporanea 2017; 12; 25-29. doi: 10.26493/1855-3974.915.f48
[7] Ilić A, Klavžar S, Rho Y. Generalized Fibonacci cubes. Discrete Mathematics 2012; 312: 2-11. doi: 10.1016/j.disc.2011.02.015
[8] Klavžar S. Structure of Fibonacci cubes: a survey. Journal of Combinatorial Optimization; 25: 505-522. doi: 10.1007/s10878-011-9433-z
[9] Klavžar S, Mollard M. Cube polynomial of Fibonacci and Lucas cube. Acta Applicandae Mathematicae 2012; 117: 93-105. doi: 10.1007/s10440-011-9652-4
[10] Klavžar S, Mollard M. Daisy cubes and distance cube polynomial. European Journal of Combinatorics 2019; 80: 214-223. doi: 10.1016/j.ejc.2018.02.019
[11] Mollard M. Non covered vertices in Fibonacci cubes by a maximum set of disjoint hypercubes. Discrete Applied Mathematics 2017; 219: 219-221. doi: 10.1016/j.dam.2016.10.029
[12] Munarini E. Pell graphs. Discrete Mathematics 2019; 342 (8): 2415-2428. doi: 10.1016/j.disc.2019.05.008
[13] Munarini E, Cippo CP, Zagaglia Salvi N. On the Lucas cubes. Fibonacci Quarterly 2001; 39: 12-21.
[14] Pike DA, Zou Y. The domination number of Fibonacci cubes. Journal of Combinatorial Mathematics and Combinatorial Computing 2012; 80: 433-444.
[15] Saygı E. Upper bounds on the domination and total domination number of Fibonacci cubes. SDU Journal of Natural and Applied Sciences; 21 (3): 782-785. doi: 10.19113/sdufbed.05851
[16] Saygı E. On the domination number and the total domination number of Fibonacci cubes. Ars Mathematica Contemporanea 2019; 16: 245-255. doi: 10.26493/1855-3974.1591.92e
[17] Saygı E, Eğecioğlu Ö. Counting disjoint hypercubes in Fibonacci cubes. Discrete Applied Mathematics 2016; 215: 231-237. doi: 10.1016/j.dam.2016.07.004
[18] Saygı E, Eğecioğlu Ö. q -cube enumerator polynomial of Fibonacci cubes. Discrete Applied Mathematics 2017; 226: 127-137. doi:10.1016/j.dam.2017.04.026
[19] Saygı E, Eğecioğlu Ö. Boundary enumerator polynomial of hypercubes in Fibonacci cubes. Discrete Applied Mathematics 2019; 266: 191-199. doi: 10.1016/j.dam.2018.05.015
[20] Taranenko A. Daisy cubes: a characterization and a generalization. European Journal of Combinatorics 2020; 85: 103058. doi: 10.1016/j.ejc.2019.103058