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 ...
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$ ...
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_{\...
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 ...
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
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 ...
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?
...
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\},\...
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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(\...
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 ...
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 ...
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$...
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$...
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 ...
2
votes
1
answer
169
views
Graph algebras a la Lovasz
In the article (Lovasz, section 1.3) mentions graph algebra structures on the set of formal linear combinations (over a field?) of a collection of graphs. He also mentioned quantum graphs as an ...
7
votes
3
answers
489
views
Are there only finitely many distinct cubic walk-regular graphs that are neither vertex-transitive nor distance-regular?
The class of walk-regular graphs contains the vertex-transitive graphs and the distance-regular graphs. However, there are walk-regular graphs that are neither vertex-transitive nor distance-regular. ...
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 ...
1
vote
0
answers
111
views
We know $A_5$ as a non-CI-group. Now, is $A_5$ a BI-group?
We call a group satisfying the following property for all $\nu \in cd(G)$ (Irreducible character degrees of $G$) a BI-group (Babai Invariant group)
Let $G$ be a finite group, let $\Gamma=Cay(G,S)...
2
votes
1
answer
303
views
How many line graphs are there?
I am thinking of a quantitative (possibly based on random graph theory) or qualitative (say, based on topological ideas, e.g. Baire's theorem in the Gromov-Hausdorff metric space) information about ...
0
votes
1
answer
94
views
DCI-properties of Cayley graphs
A Cayley graph (resp. digraph) $Cay(G,S)$ is called a $CI$-graph (resp. $DCI$-graph) of $G$ if, for any Cayley graph (resp. digraph) $Cay(G, T)$, whenever $Cay(G,S) \cong Cay(G, T)$ we have $S = T^\...
1
vote
0
answers
267
views
incidence matrix
It is known that the rank of the (unsigned) incidence matrix of a connected graph $G$ is $n-c_0$, where $n$ is the number of nodes and $c_0$ is either 1 (if the graph is bipartite) or 0 (otherwise). ...
-2
votes
2
answers
2k
views
Is connected k-regular graphs are always vertex-transitive? [closed]
A $k$-regular graph is a graph with all vertices having degree k.
A graph $X$ is called vertex-transitive if it's automorphism group acts transitively on the vertex set.
We know that all the ...
3
votes
1
answer
116
views
Inertia of the cone graph
Let $\widehat{G}$ be the graph obtained by adding a vertex to a graph $G$ and joining it to all vertices in $V(G)$. Let $\sigma(G)$ be the number of non-positive eigenvalues of the adjacency matrix of ...
2
votes
1
answer
315
views
Laplacian spectrum of directed network (digraph) and its complement
There is a well-known relation between the spectrum of graph laplacian and its complement's laplacian, namely
$$λ_j (G^c) + λ_{n+2−j} (G) = n\;,$$
where the eigenvalues $λ_j$ are sorted in ...
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
1
answer
400
views
Counting graphs according to recursion depth
Consider the set $S$ of multigraphs defined recursively as follows:
Example Graph Class
A graph $G$ is in $S$ if(f)
$G$ is a loop on a single vertex, or
$G$ may be obtained by ...