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

104 questions
Filter by
Sorted by
Tagged with
67 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 ...
82 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 ...
78 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 ...
102 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, ...
258 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 ...
131 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)?$$ ...
231 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 ...
197 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 ...
139 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 ...
101 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 ...
103 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 ...
36 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 ...
118 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 ...
367 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 ...
196 views

369 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 ...
390 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 ...
100 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$...
91 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$...
206 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 ...
145 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 ...
346 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. ...
233 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 ...
107 views

166 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). ...
869 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 ...
98 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 ...
226 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 ...
231 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 ...
356 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 ...
368 views

### A different avatar of the complexity of a graph

Let $G$ be a connected, finite graph. (For me a graph is undirected, and it possibly has multiple edges, although the latter is not really crucial for this question). The complexity $c(G)$ (also known ...
187 views

### Computing canonical forms from orbit partitions

Suppose we know the orbit partition of the vertices of a graph (due to the action of its automorphism group). Is it easy (as in "polynomial time") to generate a canonical form (aka "canonical labeling"...
46 views

### Intersection of ideals corresponding to simplicial complexes at different points?

Suppose I have two simplicial complexies $\triangle_1$ and $\triangle_2$. Consider their Stanley-Reisner ideals $I(\triangle_1)$ and $I(\triangle_2)$. I want to get their intersections when they meet ...
175 views

### Characterizing graphs whose Incidence Matrix has the all ones vector in its row span

Suppose we have a simple connected graph $G=(V,E)$. Then let $A$ be its $|E|\times |V|$ incidence matrix. Here I am considering the unoriented incidence matrix. I want to known when the row span of $A$...
521 views

Let $S=\{(1,2),(1,2,3,\ldots,n),(1,2,3,\ldots,n)^{-1}=(1,n\ldots,2)\}$ be a subset of the symmetric group $S_n$. We know that $(1,2,\ldots,n)(1,2)=(2,3,\ldots,n)$, and thus $$[(1,2,\ldots,n)(1,2)]^{n-... 3answers 221 views ### Graphs cospectral with Cayley graphs Let G be a Cayley graph, and H a graph cospectral with G. Must H be a Cayley graph? Does a counterexample exist? If G is a circulant graph, does a counterexample exist? 0answers 57 views ### normal sets and conjugate generating sets of S_n In this arXiv paper (p. 13), Steinhardt defines a normal set in S_n as follows: Definition: A split set of more than two cycles generating S_n is said to be normal if any element is adjacent to ... 3answers 272 views ### Numerical invariants for a graph or its complement that are bounded by some constant I'm looking for numerical graph invariants that are bounded by a constant either for a graph G or its complement \bar{G}. (The complement graph \bar{G} has the same set of vertices as G but ... 0answers 42 views ### Atomic parts of lexicographic products of vertex-transitive graphs Suppose H_1 and H_2 are connected, vertex-transitive graphs, H_1 is not the complete graph, and |V(H_2)| \ge 2. Then, the lexigraphic product G=H_1 \circ H_2 is vertex-transitive, 0 < \... 1answer 192 views ### Vertex-connectivity of connected, vertex-transitive graphs without K_4 is maximum possible A graph is said to have optimal vertex connectivity if its vertex connectivity equals its minimum degree. According to this arXiv preprint, it was shown by Mader in (Arch. Math., 1970) and (Math. Ann.,... 1answer 52 views ### Number of k-walks containing a vertex in an unweighted multigraph Let G = (V,E,W) be a weighted graph, where each edge e = (v_i,v_j) has weight w_{ij} \in \mathbb Z^+ \cup \{0\}. By replacing e with w_{ij} copies of unweighted multiedges, a weighted graph ... 0answers 271 views ### The degree/diameter problem for even girth graphs starting with upper bound I posted this on stackexchange but due to a lack of response there I am posting here. Let G be a graph with girth g, minimal degree \delta, maximal degree \Delta, and diameter D. Define$$...
Are there collections of already generated large strongly regular graphs available to download? By large I mean $n \geq 200$ where $n$ is the number of vertices. I found Ted Spence's page on srgs, ...
A coherent algebra is a matrix algebra (over $\mathbb{C}$) closed under conjugate transpose and Schur (entrywise) product, and that contains the identity matrix $I$ and all ones matrix $J$. Given ...