Minimum supports of eigenfunctions of graphs: a survey
In this work we present a survey of results on the problem of finding the minimum cardinality of the support of eigenfunctions of graphs.
Source author record
Alexandr Valyuzhenich
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
ResearcherUnclaimed source record
Catalog footprint
Research overview
7works
2topics
4close collaborators
Published work
7 publications
preprint2020arXiv
Eigenfunctions and minimum 1-perfect bitrades in the Hamming graph
The Hamming graph H(n,q) is the graph whose vertices are the words of length n over the alphabet {0,1,…,q−1}, where two vertices are adjacent if they differ in exactly one coordinate. The adjacency matrix of H(n,q) has n+1 distinct eigenvalues n(q−1)−q⋅i with corresponding eigenspaces Ui(n,q) for 0≤i≤n. In this work we study functions belonging to a direct sum Ui(n,q)⊕Ui+1(n,q)⊕…⊕Uj(n,q) for 0≤i≤j≤n. We find the minimum cardinality of the support of such functions for q=2 and for q=3, i+j>n. In particular, we find the minimum cardinality of the support of eigenfunctions from the eigenspace Ui(n,3) for i>2n. Using the correspondence between 1-perfect bitrades and eigenfunctions with eigenvalue −1, we find the minimum size of a 1-perfect bitrade in the Hamming graph H(n,3).
Open access
preprint2018arXiv
PI-eigenfunctions of the Star graphs
We consider the symmetric group Symn,n⩾2, generated by the set S of transpositions (1 i),2⩽i⩽n, and the Cayley graph Sn=Cay(Symn,S) called the Star graph. For any positive integers n⩾3 and m with n>2m, we present a family of PI-eigenfunctions of Sn with eigenvalue n−m−1. We establish a connection of these functions with the standard basis of a Specht module. In the case of largest non-principal eigenvalue n−2 we prove that any eigenfunction of Sn can be reconstructed by its values on the second neighbourhood of a vertex.
Open access
preprint2018arXiv
On eigenfunctions and maximal cliques of Paley graphs of square order
In this paper we find new maximal cliques of size 2q+1 or 2q+3, accordingly as q≡1(4) or q≡3(4), in Paley graphs of order q2, where q is an odd prime power. After that we use new cliques to define a family of eigenfunctions corresponding to both non-principal eigenvalues and having the cardinality of support q+1, which is the minimum by the weight-distribution bound.
Open access
preprint2015arXiv
Minimal supports of eigenfunctions of Hamming graphs
We find minimal supports of eigenfunctions of Hamming graphs for eigenvalue n(q-1)-q and describe eigenfunctions with minimal support.
Open access
preprint2013arXiv
Universal graphs and universal permutations
Let X be a family of graphs and Xn the set of n-vertex graphs in X. A graph U(n) containing all graphs from Xn as induced subgraphs is called n-universal for X. Moreover, we say that U(n) is a proper n-universal graph for X if it belongs to X. In the present paper, we construct a proper n-universal graph for the class of split permutation graphs. Our solution includes two ingredients: a proper universal 321-avoiding permutation and a bijection between 321-avoiding permutations and symmetric split permutation graphs. The n-universal split permutation graph constructed in this paper has 4n3 vertices, which means that this construction is order-optimal.
Open access
preprint2012arXiv
Crucial and bicrucial permutations with respect to arithmetic monotone patterns
A pattern τ is a permutation, and an arithmetic occurrence of τ in (another) permutation π=π1π2...πn is a subsequence πi1πi2...πim of π that is order isomorphic to τ where the numbers i1<i2<...<im form an arithmetic progression. A permutation is (k,ℓ)-crucial if it avoids arithmetically the patterns 12...k and ℓ(ℓ−1)...1 but its extension to the right by any element does not avoid arithmetically these patterns. A (k,ℓ)-crucial permutation that cannot be extended to the left without creating an arithmetic occurrence of 12...k or ℓ(ℓ−1)...1 is called (k,ℓ)-bicrucial. In this paper we prove that arbitrary long (k,ℓ)-crucial and (k,ℓ)-bicrucial permutations exist for any k,ℓ≥3. Moreover, we show that the minimal length of a (k,ℓ)-crucial permutation is max(k,ℓ)(min(k,ℓ)−1), while the minimal length of a (k,ℓ)-bicrucial permutation is at most 2max(k,ℓ)(min(k,ℓ)−1), again for k,ℓ≥3.
Open access
Research graph
See the researcher in context
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.