Questions tagged [algebraic-graph-theory]
Algebraic methods in Graph Theory; the linear algebra method, graph homomorphisms, group theoretic methods (for example Cayley graphs), and graph invariants. For graph eigenvalue problems use the spectral-graph-theory tag. For strongly regular graphs use the strongly-regular-graph tag. For Kneser graphs use the kneser-graph tag.
121
questions
1
vote
1
answer
30
views
Homomorphisms relationship with Graph Degeneracy
Let $H, G$ be finite undirected graphs. We say that $H$ is $r$-degenerate if there exists an ordering of the vertices of $H$ such that the back degree of every vertex is at most $r$. This is ...
11
votes
5
answers
1k
views
Which directed graphs have a normal adjacency matrix?
I am working on a problem in matrix analysis and I am looking for certain types of normal matrices. I suspect that these "special" normal matrices arise as adjacency matrices of certain graphs. My ...
3
votes
0
answers
210
views
Efficient way to calculate Smith Normal Form of large integer matrices
I am interested in calculating the Smith Normal Form for Laplacian matrices of hypercube graphs. Using the elementary divisors method from SAGE, I was able calculate up to the 11-cube (which has a $2^{...
0
votes
0
answers
122
views
On the absolute difference of the Laplacian eigenvalues of an unbalanced signed graph and its underlying graph
Let $\Sigma=(G,\sigma)$ be an unbalanced signed graph with the underlying connected graph $G=(V,E)$ and $\sigma:E\rightarrow \{-1,1\}$, the signing function. Let the Laplacian eigenvalues of $\Sigma$ ...
11
votes
1
answer
433
views
Correspondence between matrix multiplication and a graph operation of Lovász
In his book "Large networks and graph limits", Lovász describes a multiplication operation (he calls it concatenation) on "bi-labeled graphs". An $(m,n)$ bi-labeled graph is a ...
9
votes
3
answers
560
views
Generating (or availability of) large strongly regular graphs
Are there collections of already generated large strongly regular graphs available to download? By large I mean $n \geq 200$ where $n$ is the number of vertices. I found Ted Spence's page on srgs, ...
8
votes
0
answers
149
views
Partial order on graphs induced by homomorphism counts
For graphs $F$ and $G$, let $\hom(F,G)$ denote the number of homomorphisms (adjacency preserving maps) from $F$ to $G$. Define a relation $\le_{\hom}$ on (isomorphism classes of) graphs as $G \le_{\...
17
votes
1
answer
1k
views
Bicycles and spanning trees of graphs
A spanning tree in a graph is a connected spanning subgraph with no cycles; it is well known that the number of spanning trees can be found by taking the determinant of a certain matrix related to the ...
6
votes
1
answer
437
views
An algebraic view of graph reconstruction
$\DeclareMathOperator\Sym{Sym}\DeclareMathOperator\Coh{Coh}$I have broken my question into a few sections for clarity and to provide sufficient context to the problem. I apologize for the length. The ...
1
vote
1
answer
225
views
Do the cycles containing a fixed edge generate the cycle space of a graph?
Let $G$ be a $2$-connected graph and for $e \in E(G)$ denote by $\mathcal{C_e}$ the set of all cycles of $G$ containing the edge $e$.
For what set of edges does $\mathcal{C_e}$ contain a basis of the ...
15
votes
1
answer
506
views
Reference request: Moore graphs
It is clear that the term Moore graph was coined by Hoffman and Singleton in their paper On Moore graphs with diameters $2$ and $3$, where they write
E. F. Moore has posed the problem of describing ...
5
votes
2
answers
292
views
Characterizing graphs whose incidence matrix has the all ones vector in its row span
Suppose we have a simple connected graph $G=(V,E)$. Then let $A$ be its $|E|\times |V|$ incidence matrix. Here I am considering the unoriented incidence matrix. I want to know when the row span of $A$ ...
3
votes
1
answer
171
views
When is a $k$-distance-transitive graph already distance-transitive?
Call a (finite and connected) graph $k$-distance-transitive if its symmetry group acts transitively on the pairs in each one of the sets
$$D_\delta:=\{(i,j)\in V\times V\mid \mathrm d(i,j)=\delta\},\...
8
votes
3
answers
938
views
Classes of graphs for which isospectrum implies isomorphism?
The spectrum of a graph is the (multi)set of eigenvalues of its adjacency matrix (or Laplacian, depending on what you're interested in). In general, two non-isomorphic graphs might have the same ...
1
vote
0
answers
120
views
halved and folded hypercube duality
Notation. Consider the group $\Gamma=\mathbb{Z}_2^n$. I will denote the group operation aditively and by $\epsilon_i=(0,\dots,0,1,0,\dots,0)$ I denote the canonical generators. Let's define also $\...
1
vote
0
answers
100
views
Varieties determined by a characteristic-type of polynomial with the structure of an underlying graph
While writing my master thesis, following problem came up:
Given a digraph $G$ with edges $e_1,..,e_n$ and a
given a $n\times n$- matrix $A\in\mathbb{C}^{n\times n}$ such that $A_{ij}=0$ if the ending ...
9
votes
2
answers
471
views
Moore graphs and finite projective geometry
In a comment on a blog post from 2009 about the hypothetical Moore graph(s) of degree 57 and girth 5, Gordon Royle offered the following observation (reproduced here in full for the sake of ...
2
votes
0
answers
182
views
The rank of a Laplacian-type matrix
Suppose that $M$ is an integer, symmetric matrix of order $n>2$ with the positive integers $K_1,\dotsc,K_n$ on its main diagonal, and with all the off-diagonal elements equal to $0$ or $1$ so that ...
3
votes
0
answers
70
views
how do I find eigenvalues of Cayley graph for one subset given a different subset
How do I find eigenvalues for the adjacency matrix of Cayley graph $X(S_n,S)$ where $S_n$ is the symmetric group of order $n$ and $S$ is the set of transpositions $(i,i+1)$, if the eigenvalues of the ...
1
vote
0
answers
70
views
Algebraic Formulation of Graph Reconstruction [closed]
Background
Let $G$ be a finite graph on $v$ vertices. The deck, $D(G)$, of $G$ is the multi-set of vertex-deleted subgraphs of $G$. The Graph Reconstruction Conjecture asserts that for finite graphs $...
1
vote
1
answer
158
views
Lower bound for $\vert \det A \vert $ for the adjacency matrix of regular graphs
Assume $G$ is a simple $k$-regular graph of order $n$ with adjacency matrix $A$ which is non-singular.
Does anyone know some lower bounds for $\vert \det (A) \vert$ with respect to $n$, $k$ or both?
...
2
votes
1
answer
118
views
A diameter 2 arc-transitive graph whose complement is not arc-transitive?
A graph $G=(V,E)$ is arc-transitive if its symmetry group acts transitively on ordered pairs of adjacent vertices.
In general, the complement of an arc-transitive graph is not arc-transitive.
But I ...
1
vote
1
answer
87
views
Total behaviour of graph spectrum
Let $\mathcal{G}$ be the set of all finite connected simple graphs minus the complete graphs. For any $G\in \mathcal{G}$, let $\lambda_{\geq0}(G)$ denotes the smallest positive adjacency eigenvalue of ...
3
votes
0
answers
121
views
Vertex in a graph whose stabilizer (in a given group $\Gamma$ of automorphisms) does not fix any neighbour vertex?
I know next to nothing about graph theory, but I did recently use the concept of graphs and groups acting on them to formalize the proof of a statement that has a priori nothing to do with graphs.
I ...
1
vote
0
answers
142
views
Symmetric subgraph configurations
Let $G,H$ be two simple graphs. Let's call a subgraph of $H$ that is isomorphic to $G$ a $G$-subgraph. Consider the following construction:
Construction: Let $\mathcal G=\mathcal G(G,H)$ be a graph ...
0
votes
1
answer
144
views
Elusive groups and vertex-transitive graphs
This question is pertaining to finite connected vertex-transitive graphs.
I recently read "Transitive permutation groups without semiregular subgroup" by Cameron, Giudici, Jones, Kantor, Klin, ...
5
votes
1
answer
148
views
For what graph does the following algebraic property hold?
Let $G=(V,E)$ be a simple graph.
My question:
For what graph $G$, does there exist a permutation $\sigma$ on $V$ such that
$$\prod_{uv\in E}(x_{\sigma(u)}-x_{\sigma(v)})=-\prod_{uv\in E}(x_u-x_v)?$$
...
2
votes
1
answer
497
views
History of algebraic graph theory
I need a source about the history of algebraic graph theory. I mean for solving which problems or responding to what needs it was created?
Indeed, I want to write a note about the history of the ...
8
votes
2
answers
582
views
Does the clique-coclique bound hold for all walk-regular graphs?
The clique-coclique bound is said to hold for a simple graph $G$ on $n$ vertices if $\lvert \omega(G) \rvert \lvert \alpha(G) \lvert \leq n$, letting $\omega(G)$ and $\alpha(G)$ denote its clique and ...
4
votes
1
answer
291
views
Are there graphs with irrational eigenvalues which are all $>1$?
The eigenvalues associated to a graph's adjacency matrix are necessarily algebraic integers, because the adjacency matrix itself is entirely integer. I'm curious as to whether it's possible to have ...
0
votes
1
answer
124
views
Chromatic Polynomials of Circulant Graph With Two Parameters
I have been working with the chromatic polynomials of circulant graphs of prime order $p$ with two distinct parameters, i.e.
$P_{p,i,j}(x):= P(C_{p}(i,j),x)$ with $1 \leq i \neq j \leq \ n/2.$
In ...
2
votes
1
answer
274
views
Bounds on singular values of invertible 0-1 matrices
I'm interested in considering digraphs from an algebraic perspective, which leads me to the following question.
Consider an invertible 0-1 matrix of shape $n \times n$.
What lower and upper bounds ...
1
vote
0
answers
44
views
The number of Laplacian eigenvalues of a graph in interval [k,n]
There are several upper and lower bounds for $m_G[2,n]$ (the number of Laplacian eigenvalues of a graph $G$ with $n$ vertices in the interval $[2,n]$).
I want to know whether there exists any bound ...
6
votes
2
answers
534
views
Do perfect matching(s) have signatures in the graph eigenvalues?
If the edges of a bipartite graph are such that they can be seen as a disjoint union of perfect matchings then will this somehow reflect in the eigenvalues of the Laplacian?
It would be helpful to ...
1
vote
1
answer
117
views
Quantified imbalance in signed graphs
Let $G=(V,E)$ be an $n$-vertex simple undirected graph. A signing of the graph is a function $s:E \to \{1,-1\}$, and $(G,s)$ is a signed graph. That is, we label each edge of the graph with $1$ or $-1$...
5
votes
1
answer
144
views
Inertia of a class of Cayley graphs
Let $H^n_2(d)$ be the Cayley graph with vertex set $\{0,1\}^n$ where two strings form an edge iff they have Hamming distance at least $d$. What is the inertia of these graphs, that is, the numbers of ...
9
votes
1
answer
472
views
Relationship of Weisfeiler-Lehman algorithm to weak isomorphism of coherent algebras
A coherent algebra is a matrix algebra (over $\mathbb{C}$) closed under conjugate transpose and Schur (entrywise) product, and that contains the identity matrix $I$ and all ones matrix $J$. Given ...
4
votes
1
answer
563
views
Smallest pair of non-isomorphic graphs equivalent under the Weisfeiler-Leman algorithm
The (2-dimensional) Weisfeiler-Leman algorithm is a method for partitioning the ordered pairs of vertices of a graph in a canonical way which gives rise to a powerful graph invariant (see for instance ...
4
votes
0
answers
296
views
For what (other) families of graphs does the clique-coclique bound hold?
For a graph $G$, let $\omega(G)$ and $\alpha(G)$ denoted the clique and independence numbers of $G$ respectively. For some families of graphs, e.g. vertex transitive graphs, it is known that $\alpha(G)...
3
votes
1
answer
68
views
Are cospectral signed graphs with identical underlying graph necessarily switching-equivalent?
I'm working with signed graphs and I don't know the answer to the following question. Also, I couldn't find the answer anywhere.
Question: If we have two signed graphs with the same underlying graph ...
1
vote
1
answer
314
views
Determinant of incidence matrix of a unicyclic unbalanced signed graph
While reading a paper on unicyclic unbalanced signed graphs, I met the following fact:
The determinant of the incidence matrix of a unicyclic unbalanced graph (i.e. the cycle of the graph has an ...
7
votes
2
answers
413
views
Automorphism group of a special commuting graph
Suppose $S_6$ is the symmetric group on six letters and let $X$ denote the conjugacy class containing $(12)(34)$. Define a graph $\Gamma$ with vertex set $X$ and edges precisely the 2-element subsets ...
1
vote
0
answers
124
views
graphs with semiregular automorphisms
I need some "well-known" non-regular finite graphs (at least two vertices have different valency) whose automorphism groups contain a non-trivial subgroup that acts on the vertices semi-regularly (i....
1
vote
1
answer
276
views
Automorphism group of a graph
Suppose $\Gamma$ is a simple graph and $G=\mathrm{Aut}(\Gamma)$ is the automorphism group of $\Gamma$. If $G$ stabilizes a subgraph $\Gamma_1$,, and $G_0$ is the point-wise stabiliser of the set $V(\...
3
votes
1
answer
251
views
If L is the laplacian matrix of an undirected graph, and D is a diagonal matrix, what does the cofactor of L+D look like?
We know (e.g. [Godsil, Royle: Algebraic Graph Theory, Lemma 13.2.3]) that any cofactor of the Laplacian matrix of a graph is constant, and is equal to the number of spanning trees of the graph. How do ...
3
votes
1
answer
187
views
Imbalance in a Signed Graph
Let $G=(V,E)$ be an $n$-vertex simple undirected graph. A signing of the graph is a function $s:E \to \{1,-1\}$, and $(G,s)$ is a signed graph. That is, we label each edge of the graph with $1$ or $-1$...
4
votes
1
answer
313
views
Spectra of the quotient of a directed graph
Given a graph $G(V,E)$ and a partition $\{V_1,\dots V_n\}$ of the nodes set $V$, the adjacency and Laplacian spectra of the quotient graph $Q(G)$ interlaces the adjacent and the Laplacian spectra of ...
3
votes
0
answers
279
views
Cayley Graphs and Cyclically reduced words [closed]
Let $G$ be a finite group and $S$ be a symmetric generating set for $G$. (EDIT: Assume $S$ does not contain involutions!) Cyclically reduced words can be thought of as minimal length representatives ...
0
votes
0
answers
50
views
Intersection of ideals corresponding to simplicial complexes at different points?
Suppose I have two simplicial complexies $\triangle_1$ and $\triangle_2$. Consider their Stanley-Reisner ideals $I(\triangle_1)$ and $I(\triangle_2)$. I want to get their intersections when they meet ...
0
votes
1
answer
249
views
Find the minimum distance of some bad binary code
Let $M$ be a $n \times n$ matrix over the finite field of two elements that satisfies the following property$\colon$ the total number of 1's in each row coincides with one in each column. In other ...