Studying graphs using algebra (for example, linear algebra and abstract algebra) as a tool.
Questions tagged [algebraic-graph-theory]
768 questions
4
votes
1 answer
The Paley Graph with $9$ vertices
I'm working out of Godsil and Royle's Algebraic Graph Theory text, and I'm trying to understand Paley graphs. My book gives as a definition the following:
Let $q$ be a prime power such that $q\equiv 1\pmod{4}$. The Paley graph $P(q)$ has as vertex…
chris
- 2,659
3
votes
0 answers
Non-edge preserving graph homomorphism
Let $G(V,E)$ and $H(V',E')$ be two undirected graphs. Suppose $f : V \to V'$ is a function such that $\forall (u,v) \in V\times V, (u,v)\in E \implies (f(u),f(v))\in E' $ and $\forall (u,v) \in V\times V, (u,v)\notin E \implies (f(u),f(v))\notin E'…
Sajin Koroth
- 131
3
votes
1 answer
Graph theoretic interpretation of a Geometric problem
I am currently reading Godsil's Algebraic graph theory for my thesis . On page 250, he says:
"The geometric problem of finding least integer d such that there are n equiangular lines in $\Bbb{R}^d$ is equivalent to the graph-theoretic problem of…
user160492
- 141
3
votes
1 answer
The relationship between incidence matrix and the number of components of a graph
There is a theorem in Algebraic graph theory which state: "Let X be a graph with n vertices and $c_o$ bipartite connected components. If B is the incidence matrix of X, then its rank is given by rk(B) = n - $c_o$."
This is what I think should be…
Christian Prince
- 1,388
2
votes
1 answer
why do we need odd cycles in this question?
prove that the graph is connected and has odd length cycle if and only if there exist natural number $r$ that all entries of $A^r$ is positive.
$A$ is adjacency matrix of our graph.
I know if all entries are nonzero then we have connected graph…
kpax
- 2,911
2
votes
1 answer
For a graph $G$, $\chi (G) = 1+ \lambda_1$ iff $G$ be a complete or oddcycle connected graph.
For a graph $G$, $\chi (G)$ is the color number. Means minimum colors need to paint vertexes of graph whit out any couple of vertexes whit the same color. $\lambda_1$ Is the greatest eigenvalue of adjacency matrix of graph. I need some idea or an…
Hoseyn Heydari
- 1,517
2
votes
0 answers
A question on Hall's proof that bipartite graphs imply the existence of matchings that saturate all vertices iff $|N(S)|\geq\left|S\right|$
This is a question about the proof of the converse of Theorem 5.2 in
"Graph Theory with Applications" by J.A. Bondy and U.S.R. Murty, 1976,
North-Holland.
Theorem. Let $G$ be a bipartite graph with bipartition $(X,Y)$. Then $G$
contains a matching…
user494733
2
votes
1 answer
Show that $\theta I -A$ is positive semidefinite matrix.
Let $X$ be a graph with a maximum non-zero eigenvalue $\theta$, and let $A=A(X)$ be the adjacency matrix of the graph. Is it true that $\theta I -A$ is a positive semidefinite matrix?
Christian Prince
- 1,388
2
votes
2 answers
The Product of incidence matrix and its Transpose
There is a lemma that states :"Let B be the incidence matrix of the graph X, and let L be the line graph of X. Then $B^T B = 2I + A(L).$"
(Note: $A(L)$ is the adjacency matrix of $L$)
Does anyone know how to verify this? Please do so with love.
Christian Prince
- 1,388
2
votes
0 answers
Unique factorization of integers vs. unique factorization of graphs
As you know, graphs can be factorized in their component subgraphs, factors such as eventually semilattices, and so on. I would like to know about the precise nature of the relation that might hold (if any) between such graph decomposition(s) and…
Javier Arias
- 2,033
2
votes
0 answers
show that any directed cycle graph $C_n$ will be uniquely determined by its spectrum of adjacency matrix for directed graph.
show that any directed cycle graph $C_n$ will be uniquely determined by its spectrum of adjacency matrix for directed graph.
it is easy to see that the eigenvalues for directed cycle is $e^{\frac{2\pi ri}{n}} $for $0\leq r\leq n-1$ .
now suppose we…
kpax
- 2,911
1
vote
1 answer
rank of adjacency matrix of line graph over $\mathbb{Z}_2$.
suppose that $G$ is connected and $A_L$ is adjacency matrix of line graph of $G$,show that the rank of $A_L$ over field $\mathbb{Z}_2$ is :
$$rank_{\mathbb{Z}_2}(A_L)=\left\{\begin{matrix}
n-1 & n \: is \: odd \\
n-2& n \: is \:…
kpax
- 2,911
1
vote
0 answers
what is determinant of adjacency matrix of forest?
suppose $F$ is a forest,prove that the determinant of adjacency matrix of this forest is $-1$ or $0$ or $1$ .
I focused on trees of this forest, say that if I know eigenvalues of trees,I will multiply all together hoping they will be 1 ,-1 or 0.but…
kpax
- 2,911
1
vote
0 answers
Understanding coordinates of vectors of an incidence structure (P,I,L) over a finite field $\mathbb{F}_q$
I am teaching myself from a math paper ("Explicit construction of graphs with an arbitrary large girth and of large size" by Felix Lazebnik, and Vasiliy A. Ustirnenko) and I have questions about the way they they defined the vectors of the incidence…
jcordes74
- 11
1
vote
1 answer
What is the automorphism group of a complete bipartite graph isomorphic to?
I couldn't quite figure out what the automorphism group of a complete bipartite graph $\Gamma (K_{r,s})$ is isomorphic to. I did some back-of-the-envelope calculations and found that $\Gamma (K_{r,s})$ has an order of $(s-1)!$ when $r = 1$ and $s…
Pecfex
- 25