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

learn more… | top users | synonyms

2
votes
1answer
168 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
672 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
539 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
933 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
150 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
127 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$ ...
9
votes
0answers
254 views

“Semidirect product” of graphs?

The first subquestion is "has a standard notion of semidirect product been defined in graph theory"? If yes, i'd like to know if the definition i'm gonna give is equivalent to the standard one. I'd ...
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
217 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
37 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
456 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
103 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
372 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 ...
1
vote
1answer
123 views

Eccentricity in corona product

I was studying about graph operation on wiki. Corona product of graphs $G_1$ and $G_2$, is the graph which is the disjoint union of one copy of $G_1$ and $|V_1|$ copies of $G_2$ ($|V_1|$ is the number ...