# All Questions

Tagged with graph-theory algebraic-graph-theory

73
questions

**0**

votes

**1**answer

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

**7**

votes

**0**answers

135 views

### Correspondence between matrix multiplication and a graph operation of Lovasz

In his book "Large networks and graph limits" (available online here: http://web.cs.elte.hu/~lovasz/bookxx/hombook-almost.final.pdf), Lovasz describes a multiplication operation (he calls it ...

**5**

votes

**1**answer

117 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

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

**5**

votes

**1**answer

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

**0**

votes

**1**answer

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

**1**

vote

**0**answers

34 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

115 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

301 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

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

**1**

vote

**1**answer

76 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

89 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

183 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(\...

**8**

votes

**2**answers

345 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

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