Articles of algebraic graph theory

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 isomorphism (GI) problem. I would like to make it sure that I get the development of the concept right. Here both $A$ and $B$ […]

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’)$ for a suitable $S’.$ Recall that $\Gamma = \mathrm{Cay}(G,S)$ is a Cayley graph with vertex set $G$ if $G$ is a group, $S$ is a subset of […]

suppose $n$ people are in a party and every two of them have exactly one common friends,prove that there is one who is friend to all.

suppose $n$ people are in a party and every two of them have exactly one common friends,prove that there is one who is friend to all. I suppose there is no one who is friend to all,I want to show that the graph with this assumption is strongly regular graph and then show that two […]

“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 also like to know if there’s some litterature about it. If the answer was “no”, would you accept my definition […]

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 gives us the algorithmic complexity of $O(n^3)$. It is well known that if $A$ is the adjacency matrix of $G$ then […]

An Example for a Graph with the Quaternion Group as Automorphism Group

I am reading “Graphs of Degree Three with given Abstract Group” (by Robert Frucht) where the author describes (somewhat tedious) algorithms to construct suitable graphs starting from a given group. I would like to see a graph associated with the quaternion group as its automorphism group. Following the given algorithm the graph should have 32 […]

Can any finite group be realized as the automorphism group of a directed acyclic graph?

We are given a finite group $G$ and wish to find a DAG (directed acyclic graph) $(V,E)$ whose automorphism group is exactly G (a graph automorphism of a graph is a bijective function $f:V\to V$ such that $(u,v)\in E \iff (f(u),f(v))\in E$). A similar (positive) result for undirected graph is known: Frucht’s theorem. My uneducated […]

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 graph $X$. Then an automorphism of $X$ which fixes $[\alpha]$ must be the identity automorphism. To understand the Proposition, and the proof, some […]

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, but its applied here by using 0 in definition and in adjacency relation is out of my mind. I will […]

Is there matrix representation of the line graph operator?

I had the need to calculate the adjacency matrix $L$ of the line graph of a certain planar $k$-regular graphs $G(n,e)$ ( $n$ vertices and $e=\frac k2 n$ edges) given its adjacency matrix $A_G$. Here I went: Let $N_k$ an “outer-diagonal” indexing matrix, e.g. $N_4=\pmatrix{0&1&2&3\\1&0&4&5\\2&4&0&6\\3&5&6&0}$. Calculate the Hadamard Dot product $B=N_k\odot A$. I found that […]