×

Minimum supports of eigenfunctions with the second largest eigenvalue of the star graph. (English) Zbl 1439.05139

Summary: The Star graph \(S_n\), \(n\geq 3\), is the Cayley graph on the symmetric group \(\mathrm{Sym}_n\) generated by the set of transpositions \(\{(12),(13),\dots,(1n)\}\). In this work we study eigenfunctions of \(S_n\) corresponding to the second largest eigenvalue \(n-2\). For \(n\geq 8\) and \(n=3\), we find the minimum cardinality of the support of an eigenfunction of \(S_n\) corresponding to the second largest eigenvalue and obtain a characterization of eigenfunctions with the minimum cardinality of the support.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05E16 Combinatorial aspects of groups and algebras
05B30 Other designs, configurations
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] S. B. Akers, B. Krishnamurthy. A group-theoretic model for symmetric interconnection networks.IEEE Trans. Comput., 38(4):555-566, 1989. · Zbl 0678.94026
[2] S. V. Avgustinovich, E. N. Khomyakova, E. V. Konstantinova. Multiplicities of eigenvalues of the Star graph.Siberian Electronic Mathematical Reports, 13:1258- 1270, 2016. · Zbl 1370.05089
[3] E. A. Bespalov. On the minimum supports of some eigenfunctions in the Doob graphs.Siberian Electronic Mathematical Reports, 15:258-266, 2018. · Zbl 1394.05068
[4] J. Borges, J. Rif‘a, V. A. Zinoviev. On completely regular codes.Problems of Information Transmission, 55(1):1-45, 2019. · Zbl 1452.94133
[5] G. Chapuy, V. Feray. A note on a Cayley graph of Symn.arXiv:1202.4976v2, 1-5, 2012.
[6] C. D. Godsil. Algebraic Combinatorics. Chapman and Hall Mathematics Series, Chapman Hall, New York, 1993. · Zbl 0784.05001
[7] S. Goryainov, V. Kabanov, L. Shalaginov, A. Valyuzhenich. On eigenfunctions and maximal cliques of Paley graphs of square order.Finite Fields and Their Applications, 52:361-369, 2018. · Zbl 1388.05115
[8] S. Goryainov, V. Kabanov, E. Konstantinova, L. Shalaginov, A. Valyuzhenich. PIeigenfunctions of the Star graphs.Linear Algebra and its Applications, 586:7-27, 2020. · Zbl 1429.05125
[9] J. S. Jwo, S. Lakshmivarahan, S. K. Dhall. Embedding of cycles and grids in star graphs.J. Circuits, Syst., Comput., 1(1):43-74, 1991.
[10] E. N. Khomyakova, E. V. Konstantinova. Note on exact values of multiplicities of eigenvalues of the Star graph.Siberian Electronic Mathematical Reports, 12:92-100, 2015. · Zbl 1341.05152
[11] E. N. Khomyakova.On the eigenvalues multiplicity function of the Star graph. Siberian Electronic Mathematical Reports, 15:1416-1425, 2018. · Zbl 1411.05167
[12] R. Krakovski, B. Mohar. Spectrum of Cayley graphs on the symmetric group generated by transpositions.Linear Algebra and its Applications, 437(3):1033-1039, 2012. · Zbl 1243.05149
[13] D. S. Krotov. Trades in the combinatorial configurations.XII International Seminar Discrete Mathematics and its Applications, Moscow, 20-25 June 2016, 84-96 (in Russian).
[14] D. S. Krotov, I. Yu. Mogilnykh, V. N. Potapov. To the theory of q-ary Steiner and other-type trades.Discrete Mathematics, 339(3):1150-1157, 2016. · Zbl 1328.05025
[15] V. N. Potapov. On perfect 2-colorings of the q-ary n-cube.Discrete Mathematics, 312(6):1269-1272, 2012. · Zbl 1245.05051
[16] E. V. Sotnikova. Eigenfunctions supports of minimum cardinality in cubical distanceregular graphs.Siberian Electronic Mathematical Reports, 15:223-245, 2018. · Zbl 1394.05074
[17] E. V. Sotnikova.Minimum supports of eigenfunctions in bilinear forms graphs. Siberian Electronic Mathematical Reports, 16:501-515, 2019. · Zbl 1416.05181
[18] A. Valyuzhenich. Minimum supports of eigenfunctions of Hamming graphs.Discrete Mathematics, 340(5):1064-1068, 2017. · Zbl 1357.05094
[19] A. Valyuzhenich. Eigenfunctions and minimum 1-perfect bitrades in the Hamming graph.arXiv:2003.01571, March 2020. · Zbl 1456.05111
[20] A. Valyuzhenich, K. Vorob’ev. Minimum supports of functions on the Hamming graphs with spectral constraints.Discrete Mathematics, 342(5):1351-1360, 2019. · Zbl 1407.05226
[21] K. V. Vorobev, D. S. Krotov. Bounds for the size of a minimal 1-perfect bitrade in a Hamming graph.Journal of Applied and Industrial Mathematics, 9(1):141-146, 2015. · Zbl 1324.05047
[22] K.
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.