1. On the null spaces of quartic circulant graphsIvan Damnjanović, 2025 Abstract: A nut graph is a nontrivial simple graph whose adjacency matrix has a one-dimensionalnull space such that its nonzero vectors contain no zero elements. For circulant graphs, itis known that they are nut if and only if their nullity is one. This fact was recently usedby the author in order to show that there exists ad-regular circulant nut graph of order n if and only if 4|d,2|n, d >0, alongside n ≥d+ 4 if d≡84, and n ≥d+ 6 if 8|d, and (n, d)̸= (16,8). Here, we deal with the quartic circulant graphs and disclose several results regarding their null spaces. First of all, we derive an explicit formula for computing the nullity of any quartic circulant graph. Furthermore, we provide the full nut graph characterization among these graphs. Finally, we determine all such graphs that attain the minimum or maximum nullity with respect to a given order. We also give the extremal null spaces of these graphs.
Keywords: circulant graph, quartic graph, null space, nut graph, singular graph, adjacency matrix
Published in RUP: 27.07.2026; Views: 238; Downloads: 4
 Full text (372,95 KB)
This document has more files! More... |
2. On the uniform structure of bipartite graphs admitting a dual adjacency matrix candidateBlas Fernández, Roghayeh Maleki, Štefko Miklavič, Giusy Monzillo, 2026, original scientific article Abstract: Let Γ denote a finite, bipartite, connected graph with vertex set X. Fix x ∈ X and let ε ≥ 3 denote the eccentricity of x. For mutually distinct scalars {θ ∗ i }ε i=0 define a diagonal matrix A∗ = A∗(θ ∗ 0 , θ ∗ 1 , . . . , θ ∗ ε ) ∈ Mat X (R) as follows: for y ∈ X set (A∗)yy = θ ∗ ∂(x,y), where ∂ denotes the shortest path-length distance function of Γ. We say that A∗ is a dual adjacency matrix candidate of Γ with respect to x if the adjacency matrix A ∈ Mat X (R) of Γ and A∗ satisfy A3 A∗ − A∗ A3 + (β + 1)(A A∗ A2 − A2 A∗ A) = ρ(A A∗ − A∗ A) for some scalars β, ρ ∈ R. In this paper, we investigate when bipartite graphs that admit a dual adjacency matrix candidate also admit a uniform structure (in the sense of Terwilliger [6]). To do that, we first define a weakly uniform structure by slightly relaxing the conditions of uniform structure. The main result of this paper is that Γ admits a dual adjacency matrix candidate with respect to x if and only if Γ admits a weakly uniform structure with respect to x whose parameters satisfy some additional conditions. In particular, for β = 2, the weakly uniform structure is indeed a uniform structure.
Keywords: uniform property, dual adjacency matrix, Q-polynomial property
Published in RUP: 18.06.2026; Views: 449; Downloads: 10
Full text (318,25 KB)
This document has more files! More... |
3. On [plus/minus] 1 eigenvectors of graphsDragan Stevanović, 2016, original scientific article Abstract: While discussing his spectral bound on the independence number of a graph, Herbert Wilf asked back in 1986 what kind of a graph admits an eigenvector consisting solely of ▫$\pm 1$▫ entries? We prove that Wilf's problem is NP-complete, but also that the set of graphs having a ▫$\pm 1$▫ eigenvector is quite rich, being closed under a number of different graph compositions.
Keywords: eigenvector, adjacency matrix, Wilf's problem
Published in RUP: 03.01.2022; Views: 2908; Downloads: 47
Full text (325,02 KB) |
4. |
5. |
6. O ekstremnih grafih z dano stopnjo in premerom/ožino : doktorska disertacijaSlobodan Filipovski, 2018, doctoral dissertation Keywords: adjacency matrix, antipodal graphs, cages, excess, defect, Ramanujan graphs, selfrepeats, degree/diameter problem, spectrum, Moore graphs, asymptotic density, distance matrices, Bermond and Bollobas problem
Published in RUP: 21.01.2019; Views: 6288; Downloads: 9
Full text (913,92 KB) |
7. Adjacency preservers, symmetric matrices, and coresMarko Orel, 2012, original scientific article Abstract: It is shown that the graph ▫$\Gamma_n$▫ that has the set of all ▫$n \times n$▫ symmetric matrices over a finite field as the vertex set, with two matrices being adjacent if and only if the rank of their difference equals one, is a core if ▫$n \ge 3$▫. Eigenvalues of the graph ▫$\Gamma_n$▫ are calculated as well.
Keywords: adjacency preserver, symmetric matrix, finite field, eigenvalue of a graph, coloring, quadratic form
Published in RUP: 15.10.2013; Views: 6539; Downloads: 152
 Link to full text |
8. Q-polynomial distance-regular graphs with a [sub] 1 [equal] 0 and a [sub] 2 [not equal] 0Štefko Miklavič, 2008, original scientific article Abstract: Let ▫$\Gamma$▫ denote a ▫$Q$▫-polynomial distance-regular graph with diameter ▫$D \ge 3$▫ and intersection numbers ▫$a_1=0$▫, ▫$a_2 \ne 0$▫. Let ▫$X$▫ denote the vertex set of ▫$\Gamma$▫ and let ▫$A \in {\mathrm{Mat}}_X ({\mathbb{C}})$▫ denote the adjacency matrix of ▫$\Gamma$▫. Fix ▫$x \in X$▫ and let denote $A^\ast \in {\mathrm{Mat}}_X ({\mathbb{C}})$ the corresponding dual adjacency matrix. Let ▫$T$▫ denote the subalgebra of ▫$A{\mathrm{Mat}}_X ({\mathbb{C}})$▫ generated by ▫$A$▫, ▫$A^\ast$▫. We call ▫$T$▫ the Terwilliger algebra of ▫$\Gamma$▫ with respect to ▫$x$▫. We show that up to isomorphism there exists a unique irreducible ▫$T$▫-module ▫$W$▫ with endpoint 1. We show that ▫$W$▫ has dimension ▫$2D-2$▫. We display a basis for ▫$W$▫ which consists of eigenvectors for ▫$A^\ast$▫. We display the action of ▫$A$▫ on this basis. We show that ▫$W$▫ appears in the standard module of ▫$\Gamma$▫ with multiplicity ▫$k-1$▫, where ▫$k$▫ is the valency of ▫$\Gamma$▫.
Keywords: mathematics, graph theory, adjacency matrix, distance-regular graph, Terwilliger algebra
Published in RUP: 15.10.2013; Views: 16883; Downloads: 38
Link to full text |
