# All Questions

Tagged with graph-theory algebraic-graph-theory

75
questions

**3**

votes

**0**answers

76 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

64 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

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

**9**

votes

**0**answers

243 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

125 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

170 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

162 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

99 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

35 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

117 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

314 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

170 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

83 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

91 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

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