Questions tagged [algebraic-graph-theory]

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

681 questions
Filter by
Sorted by
Tagged with
38 views

Why is the universal covering tree of $G$ unique up to isomorphism and how to obtain the covers of $G$ of quotients thereof?

Let us start from defining the universal covering tree of a graph $G$ to be the infinite tree $\mathcal{T}$ such that any cover $H$ of $G$ is a quotient of $\mathcal{T}$. It is well known that the ...
19 views

Help finding Equation from difference of 2 different equations with unknown variables

I have the following data Item # Distance Travelled Profit earned 1 31 38.9008 1 19 23.3999 1 18 22.1269 2 19 6.2642 2 23 7.6113 What I'm trying to work out is if this is enough information to ...
53 views

What kind of graph coloring is this?

Assume a very simple graph with 3 points: V0—V1—V2 The following represent all the different possible colorings using 3 colors. I’ve labelled all of the types of colorings that are isomorphic (is that ...
102 views

16 views

76 views

Graphs on Cylinders

I know that nonplanar graphs can be embedded without self-intersection into a $g$-holed torus, for sufficiently large $g$. In particular, I know that $K_5$ and $K_{3,3}$ can be embedded into the torus....
47 views

What paths between vertices is this method actually counting?

Context From Discrete Mathematics and Its Applications by Kenneth H. Rosen: Let $G$ be a graph with adjacency matrix $A$ with respect to the ordering $v_1, v_2, ..., v_n$ of the vertices of the ...
70 views

Why no line graph has -2 as a main eigenvalue?

The eigenvalue $\lambda$ is said to be a main eigenvalue if $\mathcal{E}(e)\not \subseteq \textbf{j}^{\perp}$, where $\mathcal{E}(e)$ is the eigenspace of $\lambda$ and $\textbf{j}$ is the all-1 ...
Let $G$ be a irreducible, rowstochastic $n \times n$ matrix and let $A = (G-I)$ and $B = (G-\lambda I)$, where $|\lambda|\leq 1$ is an arbitrary eigenvalue of $G$. I am interested in learning about ...