# Questions tagged [algebraic-graph-theory]

Studying graphs using algebra (for example, linear algebra and abstract algebra) as a tool.

530 questions
24 views

### Characterize edge-transitive Cayley Graphs

Let $G$ be a finite group and $S \subseteq G$ a symmetric subset. The Cayley graph $\Gamma(G,S)$ is always vertex-transitive, but it sufficient a simple example to show that it is not always edge-...
44 views

### Number of Triangles in a graph with $n$ vertices and $m$ edges

One can show, that a Graph with at least $n$ vertices and $m$ edges, has at least $\dfrac{4m}{3n}(m-\dfrac{n^2}{4})$. I was wondering, about the best lowest bound of this, and the best upper bound of ...
55 views

### Can we have an infinite tree in this graph?

Suppose that a graph has an infinite number of nodes set up as follows: let $V_n=\{a_{n,1},a_{n,2},\dots,a_{n,n-1}\}\cup\{b_n\}$ be a set of $n$ nodes. Let $V=\bigcup_{n=1}^\infty V_n$. I am ...
32 views

### Connection between sum of Graphs and their automorphism groups

can we say something about the automorphism group of a graph $G$ that has the property: $G \cong A + B$ , if we know the automorphism groups of $A$ and $B$ respectively. The $+$ is the union $\cup$ ...
33 views

### Almost all trees have non-trivial automorphism group

In their paper Asymmetric Graphs Erdős and Rényi proved that almost all trees have non-trivial automorphism group. More specifically they showed that almost all trees contain at least one so-called ...
30 views

29 views

29 views

### Relation between eigenvectors and powers of a matrix for finding out if a graph is disconnected

I'm looking for a quick way to find out whether a graph is disconnected or not. It is if the sum of powers of it's adjacency matrices is a nonzero matrix. To speed up the process of calculating powers,...
26 views