Edge general position sets in Fibonacci and Lucas cubes. (English) Zbl 1517.05046
Summary: A set of edges \(X\subseteq E(G)\) of a graph \(G\) is an edge general position set if no three edges from \(X\) lie on a common shortest path in \(G\). The cardinality of a largest edge general position set of \(G\) is the edge general position number of \(G\). In this paper, edge general position sets are investigated in partial cubes. In particular, it is proved that the union of two largest \(\Theta\)-classes of a Fibonacci cube or a Lucas cube is a maximal edge general position set.
MSC:
| 05C12 | Distance in graphs |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C76 | Graph operations (line graphs, products, etc.) |
References:
| [1] | Anand, BS; Chandran, SVU; Changat, M.; Klavžar, S.; Thomas, EJ, Characterization of general position sets and its applications to cographs and bipartite graphs, Appl. Math. Comput., 359, 84-89 (2019) · Zbl 1428.05078 |
| [2] | Atanassov, KT; Knott, R.; Ozeki, K.; Shannon, AG; Szalay, L., Inequalities among related pairs of Fibonacci numbers, Fibonacci Quart., 41, 20-22 (2003) · Zbl 1028.11009 |
| [3] | Djoković, D., Distance preserving subgraphs of hypercubes, J. Combin. Theory Ser. B, 14, 263-267 (1973) · Zbl 0245.05113 · doi:10.1016/0095-8956(73)90010-5 |
| [4] | Eğecioğlu, Ö.; Saygı, E.; Saygı, Z., The number of short cycles in Fibonacci cubes, Theoret. Comput. Sci., 871, 134-146 (2021) · Zbl 1482.05158 · doi:10.1016/j.tcs.2021.04.019 |
| [5] | Eğecioğlu, Ö.; Saygı, E.; Saygı, Z., The Mostar index of Fibonacci and Lucas cubes, Bull. Malays. Math. Sci. Soc., 44, 3677-3687 (2021) · Zbl 1476.05029 · doi:10.1007/s40840-021-01139-2 |
| [6] | Gravier, S.; Mollard, M.; Špacapan, S.; Zemljič, SS, On disjoint hypercubes in Fibonacci cubes, Discrete Appl. Math., 190, 191, 50-55 (2015) · Zbl 1316.05090 · doi:10.1016/j.dam.2015.03.016 |
| [7] | Hammack, R.; Imrich, W.; Klavžar, S., Handbook of Product Graphs (2011), Boca Raton: CRC Press, Boca Raton · Zbl 1283.05001 · doi:10.1201/b10959 |
| [8] | Hsu, W-J, Fibonacci cubes—a new interconnection topology, IEEE Trans. Parallel Distr. Syst., 4, 3-12 (1993) · doi:10.1109/71.205649 |
| [9] | Ilić, A.; Milošević, M., The parameters of Fibonacci and Lucas cubes, Ars Math. Contemp., 12, 25-29 (2017) · Zbl 1375.05199 · doi:10.26493/1855-3974.915.f48 |
| [10] | Klavžar, S., On median nature and enumerative properties of Fibonacci-like cubes, Discrete Math., 299, 145-153 (2005) · Zbl 1073.05007 · doi:10.1016/j.disc.2004.02.023 |
| [11] | Klavžar, S., Structure of Fibonacci cubes: a survey, J. Comb. Optim., 25, 505-522 (2013) · Zbl 1273.90173 · doi:10.1007/s10878-011-9433-z |
| [12] | Klavžar, S.; Patkós, B.; Rus, G.; Yero, IG, On general position sets in Cartesian products, Results Math., 76, 123 (2021) · Zbl 1468.05249 · doi:10.1007/s00025-021-01438-x |
| [13] | Klavžar, S.; Peterin, I., Edge-counting vectors, Fibonacci cubes, and Fibonacci triangle, Publ. Math. Debrecen, 71, 267-278 (2007) · Zbl 1164.05031 · doi:10.5486/PMD.2007.3623 |
| [14] | Klavžar, S.; Peterin, I.; Zemljič, SS, Hamming dimension of a graph—the case of Sierpiński graphs, Eur. J. Combin., 34, 460-473 (2013) · Zbl 1254.05046 · doi:10.1016/j.ejc.2012.09.006 |
| [15] | Körner, J., On the extremal combinatorics of the Hamming space, J. Comb. Theory Ser. A, 71, 112-126 (1995) · Zbl 0826.05054 · doi:10.1016/0097-3165(95)90019-5 |
| [16] | Manuel, P.; Klavžar, S., A general position problem in graph theory, Bull. Aust. Math. Soc., 98, 177-187 (2018) · Zbl 1396.05033 · doi:10.1017/S0004972718000473 |
| [17] | Manuel, P.; Prabha, R.; Klavžar, S., The edge general position problem, Bull. Malays. Math. Sci. Soc., 45, 2997-3009 (2022) · Zbl 1501.05004 · doi:10.1007/s40840-022-01319-8 |
| [18] | Mollard, M., Edges in Fibonacci cubes, Lucas cubes and complements, Bull. Malays. Math. Sci. Soc., 44, 4425-4437 (2021) · Zbl 1476.05183 · doi:10.1007/s40840-021-01167-y |
| [19] | Mollard, M.: The (non-)existence of perfect codes in Lucas cubes, Ars Math. Contemp. 22, #P3.10 (2022) · Zbl 1502.94050 |
| [20] | Munarini, E.; Perelli Cippo, C.; Zagaglia Salvi, N., On the Lucas cubes, Fibonacci Quart., 39, 12-21 (2001) · Zbl 0987.05048 |
| [21] | Patkós, B., On the general position problem on Kneser graphs, Ars Math. Contemp., 18, 273-280 (2020) · Zbl 1464.05136 · doi:10.26493/1855-3974.1957.a0f |
| [22] | Savitha, KS; Vijayakumar, A., Some diameter notions of Fibonacci cubes, Asian-Eur. J. Math., 13, 2050057 (2020) · Zbl 1441.05066 · doi:10.1142/S1793557120500576 |
| [23] | Saygı, E.; Eğecioğlu, Ö., \(q\)-Counting hypercubes in Lucas cubes, Turk. J. Math., 42, 190-203 (2018) · Zbl 1424.05154 · doi:10.3906/mat-1605-2 |
| [24] | Saygı, E.; Eğecioğlu, Ö., Boundary enumerator polynomial of hypercubes in Fibonacci cubes, Discrete Appl. Math., 266, 191-199 (2019) · Zbl 1464.05203 · doi:10.1016/j.dam.2018.05.015 |
| [25] | Taranenko, A., A new characterization and a recognition algorithm of Lucas cubes, Discrete Math. Theor. Comput. Sci., 15, 31-39 (2013) · Zbl 1283.05195 |
| [26] | Taranenko, A.; Vesel, A., Fast recognition of Fibonacci cubes, Algorithmica, 49, 81-93 (2007) · Zbl 1131.68075 · doi:10.1007/s00453-007-9026-5 |
| [27] | Tian, J.; Xu, K., The general position number of Cartesian products involving a factor with small diameter, Appl. Math. Comp., 403 (2021) · Zbl 1510.05063 · doi:10.1016/j.amc.2021.126206 |
| [28] | Ullas Chandran, SV; Parthasarathy, GJ, The geodesic irredundant sets in graphs, Int. J. Math. Combin., 4, 135-143 (2016) |
| [29] | Vesel, A., Linear recognition and embedding of Fibonacci cubes, Algorithmica, 71, 1021-1034 (2015) · Zbl 1325.68172 · doi:10.1007/s00453-013-9839-3 |
| [30] | Winkler, P., Isometric embeddings in products of complete graphs, Discrete Appl. Math., 7, 221-225 (1984) · Zbl 0529.05055 · doi:10.1016/0166-218X(84)90069-6 |
| [31] | Yao, Y.; He, M.; Ji, S., On the general position number of two classes of graphs, Open Math., 20, 1021-1029 (2022) · Zbl 1496.05044 · doi:10.1515/math-2022-0444 |
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.
