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.
125 questions
1
vote
0
answers
34
views
Regularization of claw-free graphs
Let $G$ be a claw-free graph (containing no induced subgraph isomorphic to $S_4$) with $\Delta(G)) = k$ where $k$ is a constant with respect to $|V(G)|$. Is it always possible to regularize the graph ...
- 11
2
votes
0
answers
123
views
Symmetric matching in special graphs
Let $G$ be a bipartite graph, $L$ ($R$) be the set of vertices in the left (right) part.
Consider a graph $T$ with the set of vertices $R \times L$ ( $L \times R$ ) in the left (right) part. For any $...
12
votes
1
answer
1k
views
Necessary and sufficient conditions for the Cayley graph to be bipartite
Let $G$ be a finite group with identity $1$. If $S$ be an inverse closed generated subset of $G$, then $S$ is called a Cayley subset of $G$.The Cayley graph $\Gamma=\operatorname{Cay}(G, S)$ is a ...
- 173
0
votes
0
answers
64
views
triangle free cubic graphs
Is there any classification of cubic triangle-free graphs? Which structural properties of cubic triangle-free graphs are known? How about their eigenvalues or any other useful properties?
- 105
1
vote
1
answer
36
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
259
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
125
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$ ...
- 61
8
votes
0
answers
155
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_{\...
- 2,339
15
votes
1
answer
518
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 ...
- 2,339
8
votes
1
answer
501
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
132
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 $\...
- 211
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 ...
- 33
2
votes
0
answers
206
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 ...
- 23k
3
votes
0
answers
74
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 ...
- 31
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
171
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
179
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\},\...
- 13.6k
2
votes
1
answer
130
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 ...
- 13.6k
1
vote
1
answer
89
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 ...
- 4,784
3
votes
0
answers
129
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 ...
- 103
1
vote
0
answers
145
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 ...
- 13.6k
0
votes
1
answer
156
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, ...
- 121
11
votes
1
answer
467
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 ...
- 2,339
5
votes
1
answer
151
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)?$$
...
- 1,997
2
votes
1
answer
555
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
505
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 ...
- 1,645
4
votes
1
answer
316
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 ...
- 1,203
0
votes
1
answer
136
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 ...
- 13
3
votes
2
answers
370
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,414
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 ...
- 221
5
votes
1
answer
146
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 ...
- 421
4
votes
1
answer
618
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 ...
- 2,339
4
votes
0
answers
310
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)...
- 2,339
3
votes
1
answer
70
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 ...
- 351
1
vote
1
answer
366
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 ...
- 351
1
vote
0
answers
132
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....
- 792
1
vote
1
answer
286
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(\...
- 81
7
votes
2
answers
422
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 ...
- 81
8
votes
2
answers
622
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 ...
- 165
2
votes
1
answer
127
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$...
- 949
3
votes
1
answer
207
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$...
- 949
3
votes
0
answers
285
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 ...
- 949
2
votes
1
answer
180
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 ...
- 271
8
votes
3
answers
513
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. ...
- 165
0
votes
1
answer
250
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
112
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)$...
- 79
2
votes
1
answer
308
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 ...
- 3,388
0
votes
1
answer
95
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^\...
- 377
2
votes
0
answers
292
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). ...
- 3,388
-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 ...
