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
0answers
82 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
0answers
61 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
0answers
46 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
0answers
49 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
1answer
103 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? ...
0
votes
0answers
28 views

arc-transitive graphs of valency 3p, p a prime

I am looking for a characterization of arc-transitive graphs of valency $3p$, $p$ a prime. Is there any classification?
2
votes
1answer
128 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
1answer
72 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
1answer
71 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
92 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
90 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
116 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
279 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
143 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
297 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
2answers
338 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
184 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
112 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 ...
2
votes
1answer
122 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
37 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
126 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
407 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
222 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
55 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
142 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
111 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
228 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
379 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
444 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
102 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
116 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
0answers
232 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
150 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
402 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
234 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
280 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
183 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
1k 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
99 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
241 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
241 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
364 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
385 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
193 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
181 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
522 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
229 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?