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
1 answer
30 views

Homomorphisms relationship with Graph Degeneracy

Let $H, G$ be finite undirected graphs. We say that $H$ is $r$-degenerate if there exists an ordering of the vertices of $H$ such that the back degree of every vertex is at most $r$. This is ...
Sean Longbrake's user avatar
3 votes
0 answers
210 views

Efficient way to calculate Smith Normal Form of large integer matrices

I am interested in calculating the Smith Normal Form for Laplacian matrices of hypercube graphs. Using the elementary divisors method from SAGE, I was able calculate up to the 11-cube (which has a $2^{...
presidentediniente's user avatar
0 votes
0 answers
122 views

On the absolute difference of the Laplacian eigenvalues of an unbalanced signed graph and its underlying graph

Let $\Sigma=(G,\sigma)$ be an unbalanced signed graph with the underlying connected graph $G=(V,E)$ and $\sigma:E\rightarrow \{-1,1\}$, the signing function. Let the Laplacian eigenvalues of $\Sigma$ ...
shahulhameed's user avatar
8 votes
0 answers
149 views

Partial order on graphs induced by homomorphism counts

For graphs $F$ and $G$, let $\hom(F,G)$ denote the number of homomorphisms (adjacency preserving maps) from $F$ to $G$. Define a relation $\le_{\hom}$ on (isomorphism classes of) graphs as $G \le_{\...
David Roberson's user avatar
15 votes
1 answer
506 views

Reference request: Moore graphs

It is clear that the term Moore graph was coined by Hoffman and Singleton in their paper On Moore graphs with diameters $2$ and $3$, where they write E. F. Moore has posed the problem of describing ...
Vince Vatter's user avatar
  • 2,329
6 votes
1 answer
437 views

An algebraic view of graph reconstruction

$\DeclareMathOperator\Sym{Sym}\DeclareMathOperator\Coh{Coh}$I have broken my question into a few sections for clarity and to provide sufficient context to the problem. I apologize for the length. The ...
Joseph Zambrano's user avatar
1 vote
0 answers
120 views

halved and folded hypercube duality

Notation. Consider the group $\Gamma=\mathbb{Z}_2^n$. I will denote the group operation aditively and by $\epsilon_i=(0,\dots,0,1,0,\dots,0)$ I denote the canonical generators. Let's define also $\...
Daniel's user avatar
  • 211
1 vote
0 answers
100 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 ...
pizzalberto's user avatar
2 votes
0 answers
182 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 ...
Seva's user avatar
  • 22.8k
3 votes
0 answers
70 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 ...
user625452's user avatar
1 vote
0 answers
70 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 $...
Joseph Zambrano's user avatar
1 vote
1 answer
158 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? ...
Mohammad Ali Nematollahi's user avatar
3 votes
1 answer
171 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\},\...
M. Winter's user avatar
  • 12.5k
2 votes
1 answer
118 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 ...
M. Winter's user avatar
  • 12.5k
1 vote
1 answer
87 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 ...
Shahrooz's user avatar
  • 4,746
3 votes
0 answers
121 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 ...
DGrimm's user avatar
  • 103
1 vote
0 answers
142 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 ...
M. Winter's user avatar
  • 12.5k
0 votes
1 answer
144 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, ...
user52949's user avatar
  • 121
11 votes
1 answer
433 views

Correspondence between matrix multiplication and a graph operation of Lovász

In his book "Large networks and graph limits", Lovász describes a multiplication operation (he calls it concatenation) on "bi-labeled graphs". An $(m,n)$ bi-labeled graph is a ...
David Roberson's user avatar
5 votes
1 answer
148 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)?$$ ...
user173856's user avatar
  • 1,987
2 votes
1 answer
497 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 ...
Mohammad Ali Nematollahi's user avatar
9 votes
2 answers
471 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 ...
mhum's user avatar
  • 1,625
4 votes
1 answer
291 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 ...
Alex Meiburg's user avatar
  • 1,193
0 votes
1 answer
124 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 ...
Abraham G's user avatar
2 votes
1 answer
274 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 ...
Niel de Beaudrap's user avatar
1 vote
0 answers
44 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 ...
MH.Fakharan's user avatar
5 votes
1 answer
144 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 ...
Clive elphick's user avatar
4 votes
1 answer
563 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 ...
David Roberson's user avatar
4 votes
0 answers
296 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)...
David Roberson's user avatar
3 votes
1 answer
68 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 ...
A. Mpi's user avatar
  • 351
1 vote
1 answer
314 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 ...
A. Mpi's user avatar
  • 351
1 vote
0 answers
124 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....
majid arezoomand's user avatar
1 vote
1 answer
276 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(\...
maryam's user avatar
  • 81
7 votes
2 answers
413 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 ...
maryam's user avatar
  • 81
8 votes
2 answers
582 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 ...
m4farrel's user avatar
  • 155
1 vote
1 answer
117 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$...
BharatRam's user avatar
  • 939
3 votes
1 answer
187 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$...
BharatRam's user avatar
  • 939
3 votes
0 answers
279 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 ...
BharatRam's user avatar
  • 939
2 votes
1 answer
169 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 ...
mukhujje's user avatar
  • 281
7 votes
3 answers
489 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. ...
m4farrel's user avatar
  • 155
0 votes
1 answer
249 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 ...
Ivan Pogildiakov's user avatar
1 vote
0 answers
111 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)...
M. Zallaghi's user avatar
2 votes
1 answer
303 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 ...
Delio Mugnolo's user avatar
0 votes
1 answer
94 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^\...
Xueyi Huang's user avatar
1 vote
0 answers
267 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). ...
Delio Mugnolo's user avatar
-2 votes
2 answers
2k 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 ...
Ashwin Koodathil's user avatar
3 votes
1 answer
116 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 ...
Jernej's user avatar
  • 3,433
2 votes
1 answer
315 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 ...
Yuanzhao's user avatar
  • 155
4 votes
1 answer
313 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 ...
emcozzo's user avatar
  • 41
3 votes
1 answer
400 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 ...
JosephSlote's user avatar