A. Valyuzhenich

activity

20092025

most citedMinimum supports of functions on the Hamming graphs with spectral constraints

14 citations · 34 across the 14 of their papers we have counts for

collaborators

Showing math.COShow all

16 papers · 1 filter

math.CO2025

On strong nodal domains for eigenfunctions of Hamming graphs

Alexandr Valyuzhenich, Konstantin Vorob'ev

The Laplacian matrix of the $n$ -dimensional hypercube has $n + 1$ distinct eigenvalues $2 i$ , where $0 \leq i \leq n$ . In 2004, Bıyıkoğlu, Hordijk, Leydold, Pisanski and Stadler initiat…

math.CO2024

An upper bound on the number of relevant variables for Boolean functions on the Hamming graph

Alexandr Valyuzhenich

The spectrum of a complex-valued function $f$ on $Z_{q}^{n}$ is the set ${∣ u ∣ : u \in Z_{q}^{n} and f (u) \neq = 0}$ , where $∣ u ∣$ is the Hamming weight of…

math.CO2023

On reduction for eigenfunctions of graphs

Alexandr Valyuzhenich

In this work, we prove a general version of the reduction lemmas for eigenfunctions of graphs admitting involutive automorphisms of a special type.

math.CO2023

Optimal functions with spectral constraints in hypercubes

Alexandr Valyuzhenich

The $n$ -dimensional hypercube has $n + 1$ distinct eigenvalues $n - 2 i$ , $0 \leq i \leq n$ , with corresponding eigenspaces $U_{i} (n)$ . In 2021 it was proved by the author that if a functio…

math.CO2021

Minimum supports of eigenfunctions of graphs: a survey

Ev Sotnikova, Alexandr Valyuzhenich

In this work we present a survey of results on the problem of finding the minimum cardinality of the support of eigenfunctions of graphs.

math.CO2020

Eigenfunctions and minimum 1-perfect bitrades in the Hamming graph

Alexandr Valyuzhenich

The Hamming graph $H (n, q)$ is the graph whose vertices are the words of length $n$ over the alphabet ${0, 1, \dots, q - 1}$ , where two vertices are adjacent if they differ in exactly…

math.CO2019★ 1 cited

Minimum supports of eigenfunctions with the second largest eigenvalue of the Star graph

Vladislav Kabanov, Elena V. Konstantinova, Leonid Shalaginov +1

The Star graph $S_{n}$ , $n \geq 3$ , is the Cayley graph on the symmetric group $S y m_{n}$ generated by the set of transpositions ${(12), (13), \dots, (1 n)}$ . In this work we study eigenfu…

math.CO2019

Equitable 2-partitions of the Hamming graphs with the second eigenvalue

Ivan Mogilnykh, Alexandr Valyuzhenich

The eigenvalues of the Hamming graph $H (n, q)$ are known to be $λ_{i} (n, q) = (q - 1) n - q i$ , $0 \leq i \leq n$ . The characterization of equitable 2-partitions of the Hamming graphs $H (n, q)$ …

math.CO2018★ 14 cited

Minimum supports of functions on the Hamming graphs with spectral constraints

Alexandr Valyuzhenich, Konstantin Vorob'ev

We study functions defined on the vertices of the Hamming graphs $H (n, q)$ . The adjacency matrix of $H (n, q)$ has $n + 1$ distinct eigenvalues $n (q - 1) - q \cdot i$ with corresponding eige…

math.CO2018★ 6 cited

$P I$ -eigenfunctions of the Star graphs

Sergey Goryainov, Vladislav Kabanov, Elena Konstantinova +2

We consider the symmetric group $Sym_{n}, n ⩾ 2$ , generated by the set $S$ of transpositions $(1 i), 2 ⩽ i ⩽ n$ , and the Cayley graph $S_n=Cay(\math…

math.CO2018★ 10 cited

On eigenfunctions and maximal cliques of Paley graphs of square order

Sergey Goryainov, Vladislav V. Kabanov, Leonid Shalaginov +1

In this paper we find new maximal cliques of size $\frac{q + 1}{2}$ or $\frac{q + 3}{2}$ , accordingly as $q \equiv 1 (4)$ or $q \equiv 3 (4)$ , in Paley graphs of order $q^{2}$ , where $q$ is…

math.CO2017★ 2 cited

Minimum supports of eigenfunctions of Johnson graphs

Konstantin Vorob'ev, Ivan Mogilnykh, Alexandr Valyuzhenich

We study the weights of eigenvectors of the Johnson graphs $J (n, w)$ . For any $i \in {1, \dots, w}$ and sufficiently large $n, n \geq n (i, w)$ we show that an eigenvector of $J (n, w)$ …

math.CO2015

Minimal supports of eigenfunctions of Hamming graphs

Alexandr Valyuzhenich

We find minimal supports of eigenfunctions of Hamming graphs for eigenvalue n(q-1)-q and describe eigenfunctions with minimal support.

math.CO2013

Universal graphs and universal permutations

Aistis Atminas, Sergey Kitaev, Vadim V. Lozin +1

Let $X$ be a family of graphs and $X_{n}$ the set of $n$ -vertex graphs in $X$ . A graph $U^{(n)}$ containing all graphs from $X_{n}$ as induced subgraphs is called $n$ -universal for $X$ …

math.CO2012★ 1 cited

Crucial and bicrucial permutations with respect to arithmetic monotone patterns

Sergey Avgustinovich, Sergey Kitaev, Alexandr Valyuzhenich

A pattern $τ$ is a permutation, and an arithmetic occurrence of $τ$ in (another) permutation $π = π_{1} π_{2} ... π_{n}$ is a subsequence $π_{i_{1}} π_{i_{2}} ... π_{i_{m}}$ of $π$ that is order isomo…

math.CO2009

Two bijections for sets of words with forbidden factors

Alexander Valyuzhenich

In a recent paper by Kitaev and Remmel, several formulas for the number of words of length n avoiding some generalized patterns were established. Each time the obtained function of…

On strong nodal domains for eigenfunctions of Hamming graphs

An upper bound on the number of relevant variables for Boolean functions on the Hamming graph

On reduction for eigenfunctions of graphs

Optimal functions with spectral constraints in hypercubes

Minimum supports of eigenfunctions of graphs: a survey

Eigenfunctions and minimum 1-perfect bitrades in the Hamming graph

Minimum supports of eigenfunctions with the second largest eigenvalue of the Star graph

Equitable 2-partitions of the Hamming graphs with the second eigenvalue

Minimum supports of functions on the Hamming graphs with spectral constraints

PI-eigenfunctions of the Star graphs

On eigenfunctions and maximal cliques of Paley graphs of square order

Minimum supports of eigenfunctions of Johnson graphs

Minimal supports of eigenfunctions of Hamming graphs

Universal graphs and universal permutations

Crucial and bicrucial permutations with respect to arithmetic monotone patterns

Two bijections for sets of words with forbidden factors

$P I$ -eigenfunctions of the Star graphs