# 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.

124
questions

2
votes

0
answers

86
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 ...

0
votes

0
answers

52
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?

1
vote

1
answer

34
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

230
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$ ...

8
votes

0
answers

151
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

514
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 ...

7
votes

1
answer

477
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

125
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

201
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

73
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

164
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

174
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

123
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

88
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

126
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

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 ...

0
votes

1
answer

154
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

449
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

149
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

534
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

484
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

308
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

132
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 ...

3
votes

2
answers

340
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

145
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

586
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

306
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

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 ...

1
vote

1
answer

352
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

130
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

283
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

417
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

602
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 ...

2
votes

1
answer

125
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

200
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

283
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

175
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

496
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

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)...

2
votes

1
answer

305
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

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^\...

1
vote

0
answers

282
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

118
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 ...