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

learn more… | top users | synonyms

2
votes
1answer
163 views

associativity in graph theory

Can anybody help me in clearing the facts how the associativity was proved in cartesian product of 3 graphs, and thus showing isomorphism. I can easily solve for the case when its two graphs. Taking ...
8
votes
2answers
648 views

Automorphism group and congruences of the cube

I want to prove that the automorphism group of the cube is $\mathbb{Z}_2 \times S_4$, by using information about the congruences of a cube. By the cube, I mean the graph of the platonic solid, i.e. ...
0
votes
1answer
474 views

The number of labelled graphs with all vertices of even degree

I have a graph exam tomorrow, and there is a problem that said number of graph with labeled vertices and all of them of even degree is $ 2^{n-1 \choose 2} $. According to that topic, it means the ...
16
votes
3answers
825 views

Why there are $11$ non-isomorphic graphs of order $4$?

I'm new to graph theory and I don't plan to become a serious student of graph theory either. My book suggests that there are $11$ non-isomorphic graphs of order $4$, but I can't see why. I know that ...
3
votes
2answers
149 views

to clear doubt about basic definition in graph theory

Can anybody help me in clearing the doubt about hierarchical product of graphs. Its quite different from other graph products. Here is the screenshot and link how it is done. I know the rooted graph, ...
3
votes
1answer
78 views

Proof about cubic $t$-transitive graphs

I am reading "Algebraic Graph Theory" by Norman Biggs (1974). On page 119, there is a proposition which says the following: Proposition 18.1: Let $[\alpha]$ be a $t$-arc in a cubic $t$-transitive ...
3
votes
2answers
122 views

Are the eigenvectors of vertex transitive graphs bounded

For a connected and regular graph $G$ with degree $ d $ at each vertex and adjacency matrix $A$, the normalized Laplacian of $G$ is defined as $L = I-\frac{1}{d}M$. Let $\psi$ be an eigenvector of $L$ ...
8
votes
1answer
3k views

Complexity of counting the number of triangles of a graph

The trivial approach of counting the number of triangles in a simple graph $G$ of order $n$ is to check for every triple $(x,y,z) \in {V(G)\choose 3}$ if $x,y,z$ forms a triangle. This procedure ...
4
votes
1answer
210 views

Cayley graphs on small Dihedral and Cyclic group

Consider the following problem Let $n \leq 5$ and let $\Gamma = \mathrm{Cay}(C_{2n},S)$ be the Cayley graph with Cayley set $S$. Show that $\Gamma$ is isomorphic to $\mathrm{Cay}(D_{2n},S')$ ...
3
votes
1answer
36 views

Confusion about the hidden subgroup formulation of graph isomorphism

I am going through Quantum factoring, discrete logarithms and the hidden subgroup problem by Richard Jozsa. On page 13, the author discussed the hidden subgroup problem (HSP) formulation of the graph ...
2
votes
2answers
445 views

A property of incidence matrix of a graph

Let $G$ be an oriented graph with incidence matrix $Q$, and let $B:=[b_{ij}]$ be a $k\times k$ sub-matrix of $Q$ which is non-singular. Can there exist two distinct permutations $\sigma$ and ...
1
vote
2answers
100 views

Chromatic polynomial of a graph - might take a while

I'm currently struggling with graphs that require either adding edges, or removing them. Problem here being that the graphs I'm working on takes forever to complete and I don't really know if adding ...
1
vote
2answers
361 views

Chromatic polynomial of a grid graph

I have the following graph with $nm$ vertices: ...
1
vote
1answer
121 views

doubt over an equation

I am having doubt over an equation. That is my calculation. Can anybody check and find the error, if any. Specially in the last line. I am confused. Thanks a lot. NOTE : please check only last two ...
0
votes
0answers
80 views

Complexity of graph radius algorithm

I am a bit new so I hope I don`t break any rules. I have an algorithm: Given H = (V, E) a graph. If v ∈ V and r ∈ N, we will note with SH(v, r) the sphere of radius r with the center in v: SH(v, r) ...