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

learn more… | top users | synonyms

10
votes
2answers
960 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. ...
2
votes
2answers
764 views

Chromatic polynomial of a grid graph

I have the following graph with $nm$ vertices: ...
2
votes
1answer
239 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 ...
1
vote
1answer
886 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
2k 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
3answers
859 views

Can I find the connected components of a graph using matrix operations on the graph's adjacency matrix?

If I have an adjacency matrix for a graph, can I do a series of matrix operations on the adjacency matrix to find the connected components of the graph?
3
votes
2answers
175 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, ...
2
votes
0answers
139 views

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 ...
2
votes
1answer
139 views

What is the smallest and the largest possible adjacency eigenvalue of a regular graph?

For a $d-$regular graph I think $d$ is always the largest adjacency eigenvalue and if its bipartite then I think $-d$ is the smallest possible.
1
vote
2answers
80 views

Example of non-commutative association scheme

I need an example of non-commutative association scheme of ordered 6. I tried to use the example in the book Handbook of Combinatorial Designs, Second Edition by Charles J. Colbourn‏،Jeffrey H. Dini ...
3
votes
0answers
111 views

Linear Algebra and Graph theory

I haven't done any linear algebra for a long time and currently reading about linear algebra in graph theory and had a few queries. So i'm looking at the definition of a vertex space. Firstly let ...
3
votes
1answer
83 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 ...
2
votes
2answers
81 views

Automorphism group of a graph = Automorphism group of that graph's adjacency matrix?

Is automorphism group (or set) of a graph $G$ equal to the automorphism group (or set) of adjacency matrix of $G$? Example: $G_1, G_2$ are separate graphs where $G_1^{\pi}= G_2$ and $ G= \bar ...
6
votes
2answers
286 views

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 ...
4
votes
1answer
38 views

How to detect automorphism of union of graphs?

On page 1 of Lecture 2, Algebra and Computation , (Course Instructor: V. Arvind), there is a theorem- Theorem 2. With Graph − Iso (graph isomorphism) as an oracle, there is a polynomial time ...
3
votes
2answers
156 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$ ...
11
votes
0answers
302 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 ...
9
votes
1answer
4k 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
114 views

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 ...
4
votes
1answer
285 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
2answers
109 views

On the Usual Orientation of Cubic Graphs in Random Construction of Riemann Surfaces

In "Random Construction of Riemann Surfaces", Robert Brooks and Eran Makover say : Definition 2.1 A left-hand turn path on $(\Gamma, \mathcal O)$ is a closed path on [the cubic graph] $\Gamma$ ...
3
votes
1answer
52 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 ...
1
vote
1answer
55 views

On the eigenvalues of “almost” complete graph ?!

Preliminaries: Let $K_n$ be the complete graph on $n$ vertices. $|E(K_n)|=\frac{n(n-1)}{2}$. It's well known that the eigenvalues of $K_n$ are $n-1$ with multiplicity 1, and -1 with multiplicity ...
4
votes
3answers
159 views

How Graph Isomorphism is used to determine Graph Automorphism?

From Lecture 2, Algebra and Computation by V. Arvind, (page2,3), I understood below passage- For our graph $G$, let $Aut(G) = H ≤ S_n$. We shall use Weilandt’s notation where $i^\pi$ denotes ...
2
votes
2answers
663 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
0answers
57 views

Clustering large biregular graphs

I have a bipartite graph $G=(U,V,E)$ where: Every vertex in $U$ has degree $C$ Every vertex in $V$ has degree $R$ $\left|U\right|=(K\cdot R)$ $\left|V\right|=(K\cdot C)$ More succinctly, its a ...
1
vote
2answers
140 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
1answer
124 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
226 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 ...
0
votes
2answers
194 views

What is a cycle hypergraph?

What is a cycle hypergraph? Could someone give me good reference or illustrate with a few examples?