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.

Filter by
Sorted by
Tagged with
1
vote
1answer
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 ...
3
votes
0answers
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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, ...
9
votes
0answers
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 ...
5
votes
1answer
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)?$$ ...
2
votes
1answer
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 ...
6
votes
1answer
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 ...
4
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
5
votes
1answer
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 ...
4
votes
1answer
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 ...
4
votes
0answers
196 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
1answer
52 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
1answer
114 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
0answers
101 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
1answer
203 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
2answers
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 ...
8
votes
2answers
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 ...
1
vote
1answer
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$...
3
votes
1answer
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$...
2
votes
0answers
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 ...
2
votes
1answer
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 ...
7
votes
3answers
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. ...
0
votes
1answer
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 ...
1
vote
0answers
107 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
1answer
272 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
1answer
84 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
0answers
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). ...
-2
votes
2answers
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 ...
3
votes
1answer
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 ...
2
votes
1answer
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 ...
4
votes
1answer
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 ...
3
votes
1answer
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 ...
12
votes
1answer
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 ...
0
votes
1answer
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"...
0
votes
0answers
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 ...
3
votes
2answers
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$...
6
votes
2answers
521 views

A question about (unicity of certain cycles in a Cayley graph of a) symmetric group

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-...
3
votes
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?
0
votes
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 ...
6
votes
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 ...
2
votes
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 < \...
4
votes
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.,...
0
votes
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 $...
4
votes
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 $$...
9
votes
3answers
408 views

Generating (or availability of) large strongly regular graphs

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, ...
8
votes
1answer
380 views

Relationship of Weisfeiler-Lehman algorithm to weak isomorphism of coherent algebras

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