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

learn more… | top users | synonyms

0
votes
0answers
3 views

The random graph quantity $S(n: K, L)$

I am going through Degree sequences of random graphs by Béla Bollobás. On page $3$ the author introduces the quantity $S(n: K, L)$ without any explanation. Could anyone please help me in ...
1
vote
1answer
57 views

The set of isomorphisms from a right coset of the automorphism group $Aut(X)$ in $S_n$.

From "Lecture Notes in Computer Science" by Christoph M. Hoffmann , on page 22- Theorem 4 Let $X$ and $X'$ be two isomorphic graphs with vertex set $V = \{1 ..... n\}$ , Then the set of ...
2
votes
3answers
125 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 ...
0
votes
0answers
14 views

Hamioltonian Circuit of Planar Graph of Order $2^n$

$G$ is a planar graph of order(= number of vertices) $2^n$. Questions: When $G$ has a Hamiltonian Circuit? Is there a polynomial or quasi polynomial time algorithm to decide whether $G$ has a ...
0
votes
0answers
33 views

Characterization of non-isomorphic graphs but isomorphic total graphs?

Given a graph $G$, the total graph of $G$, denoted $T(G)$, is the graph with vertex set $V(G) \cup E(G)$, where $a$ and $b$ are adjacent in $T(G)$ if and only if they are adjacent or incident in $G$. ...
0
votes
0answers
15 views

My question is about Cayley graphs where the Cayley set is any set of transpositions.

I want to show that if $S$ is any subset of $Sym(n)$ such that $S$ contains only transpositions, then the Cayley graph $X=Cay(Sym(n), S)$ is bipartite. I have figured out that the vertices in $X$ ...
2
votes
0answers
108 views
+50

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 ...
0
votes
0answers
18 views

Chromatic polynomial of simple graph

Suppose I know the chromatic polynomial $P(G, \lambda)$ of the graph $G$. Can we express the chromatic polynomial of the graph $G'$ in terms of $P(G, \lambda)$ and $\lambda$? I have tried to ...
1
vote
0answers
22 views

Pseudo vertex-transitive graphs

I'm investigating finite, simple graphs with the following property: For each degree $d$ of $G$, the subgraph induced on all vertices of degree $d$ is vertex transitive. In particular, I'm ...
0
votes
1answer
21 views

girth of Cayley graphs on abelian groups

I am trying to prove that if $X(G,S) $ is a Cayley graph where $G$ is abelian and $|S|>2$, then $X(G, S)$ contains a $4$-cycle. I found an example proof at the following link: ...
3
votes
2answers
96 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$ ...
0
votes
0answers
26 views

Minimize matrix product by changing rows

Consider having a matrix relation like this $$\begin{bmatrix}1&0&0\\-1&1&0\\0&-1&1\\0&0&-1\end{bmatrix}^T\begin{bmatrix}x_1\\x_2\\x_3\\x_4\end{bmatrix} = ...
0
votes
1answer
97 views

Bound on the size of Permutation Set for Isomorphism

$\textbf{Claim :}$ $G, H $ are partitioned into sub-graphs $\{ G_1,G_2 \cdots G_x \}$ and $\{ H_1,H_2 \cdots H_x \} $ . For each $G_i$ we constructed a set permutation, $\beta_i$ such ...
0
votes
0answers
7 views

How to prove the relation between the directed Laplacian and the number of strongly connected components?

Let be a weighted digraph G (without loops) and its Laplacian L. How to prove that the multiplicity of the zero eigenvalue associated to L is equal the number of strongly connected components of G?
1
vote
2answers
74 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 ...
1
vote
0answers
38 views

What is the meaning of adjacency algebra?

What is the meaning of adjacency algebra? and Which basic information should I have to know adjacency algebra?
0
votes
0answers
18 views

Regarding self complementary trees if such exist. [duplicate]

Can anybody please tell me whether there are any self complementary trees and if so, how many and what are the conditions and the properties it holds? Thank You.
3
votes
1answer
46 views

Trace of hadamard product of adjacency matrices based on eigenvalues

Let $A$ be the adjacency matrix of the simple graph $G_n$. Is there any formula for $\text{trace}(A^3 \circ A^2)$ based on eigenvalues of $A$?
3
votes
1answer
25 views

On generators of automorphism group of symmetric graph

Suppose I have a connected graph $G$ that is vertex-transitive. Fix a vertex $v$ in $G$ and let $h$ be an automorphism of graph $G$. If $v$ is adjacent with $h(v)$ and $G$ is symmetric, I need to show ...
4
votes
0answers
28 views

Multiplicity of 0 eigenvalue of directed graph Laplacian matrix

I am looking for a result (if it exists) for directed graphs relating the multiplicity of 0 eigenvalues of the directed Laplacian matrix. Consider a directed graph ...
0
votes
0answers
32 views

Graph Automorphisms and Induced Subgraphs

Let $G=(V,E)$ be a finite simple graph, $\Gamma=Aut(G)$ be the automorphism group of $G$, and $G_v=G-\{v\}$ be a vertex-deleted induced subgraph of $G$. We define the following equivalence relation on ...
0
votes
1answer
21 views

Standard Laplacian matrix of a connected graph with N vertices

Can any body help me to proof the expression Lk *Lg=N Lg Lk=Laplacian matrix of a complete graph on N vertices. Lg=Laplacian matrix of any connected graph with N vertices. Laplacian matrix is standard ...
4
votes
0answers
38 views

Automorphisms of Graphs

This is a questions I've been playing with the last few days: Let $G=(V,E)$ be a simple graph with vertex set $V$ and edge set $E$. We will denote the vertex-deleted induced subgraph obtained by ...
0
votes
0answers
41 views

Representation of the automorphism group of a graph is reducible

We can define a representation of the automorphism group $H$ of a $n$-vertex graph $\Gamma$ as the map $\rho : H \to M$ where $M$ is the set of all $n \times n$ binary matrices. What is the ...
2
votes
1answer
31 views

Resources on algebraic graph theory of edge contractions

I am a neuroscientist involved in some research which requires understanding how edge contractions affect the properties of graph-theoretic representations of large-scale networks. I have been looking ...
1
vote
0answers
16 views

Eccentricity of vertex in a permutation cycle graph

The permutation cycle graph is defined as follows. Permutation Cycle Graph: A permutation cycle graph for a given permutation $\pi$ of a finite set $V$, is its cycle graph $\Gamma$ such that ...
1
vote
0answers
57 views

Finding all eigenvalues of the adjacency matrix of a simple graph

I want to find all eigenvalues of the adjacency matrix of the following graph(Graph spectrum), where $G$ and $H$ are complete graphs with $n$ and $m$ vertices, respectively, for positive integers $n,m ...
0
votes
0answers
11 views

Spectral properties of certain weighted adjacency matrices

I would like to know if anyone has ever studied the spectral properties of the weighted adjacency matrix of a digraph where if $w(u,v)$ is the weight of edge $(u,v)$, then $w(v,u) = w(u,v)^{-1}$. ...
1
vote
1answer
21 views

homology of a specific complex

Consider the complex $\lbrace 1, 2, 3, 4, 12, 23, 34, 41, 13, 123 \rbrace$. Visually, it's a square with a diagonal edge, with one hole and one face. In computing the homologies, I ended up getting ...
2
votes
0answers
50 views

Longest paths in a graph via adjacency matrix?

Let $G=(V,E)$ be a connected simple graph and $A_G$ its adjacency matrix. Is there an effective way to encode the information of longest paths of $G$ via $A_G$? (Or maybe using some kind of Laplacian ...
2
votes
0answers
18 views

Is there a homology theory for graphs which counts complete graph minors?

I have a strong feeling that complete graph minors ($K^i$ minors) are like a sort of cycles in a simplicial complex. Is there a homology theory (for graphs) counting complete graph minors?
1
vote
1answer
43 views

Which informations should I need to know about adjacency algebra or Bose-Mesner algebra?

Does anyone know about adjacency algebra or Bose-Mesner algebra? I have read about that, but I don't know what it says. I want to know the basic information I need to know the basis ...
0
votes
0answers
9 views

lower bound Tutte polynomial for planar graphs

The Tutte Polynomial $T(G, x, y)$ s a #P-Hard problem except for the hyperbola (x-1)(y-1)=1 and some other specific points. For the case of planar graphs, Dell $\textit{et. al.}$ mention (in the ...
1
vote
0answers
51 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
0answers
44 views

Is Doobs theorem of binary rank really true?

The theorem states that any adjacent matrix of the line graph of a connected graph has a binary rank n-1 if the order, n, of the graph is odd. I have pondered about this and found that it doesn't ...
5
votes
1answer
107 views

Expository articles on Cayley Graphs?

Does anyone know of any expository articles on Cayley graphs? I have some background in both group theory and graph theory, and know a little bit of algebraic topology. In particular, I am hoping to ...
0
votes
1answer
29 views

Show that Aut $(C_n)=D_n$

Problem statement: I need to find out Aut $(C_n)$ is isomorphic to $D_n$. I already know that it is isomorphic, so now all I need to do is to prove it. Any help is appreciated. I was hoping for a ...
0
votes
0answers
37 views

Relation between automorphism group of a permutation cycle graph and the cyclic group of its adjacency matrix over multiplication

I define the permutation cycle graphs first. Permutation Cycle Graph: A permutation cycle graph for a given permutation $\pi$ of a finite set $V$, is its cycle graph $\Gamma$ such that the ...
2
votes
1answer
31 views

How to verify that $rk(L)+rk(J)=1+rk(L)$?

I know that it has been proved on this site that $\operatorname{rank}(A + B) ≤ \operatorname{rank}(A) + \operatorname{rank}(B)$. What I still want now is an application of this theorem or the method ...
0
votes
0answers
9 views

Relationship between the determinant of D(R, S) and the number of uncyclic components of a graph.

Let $M(R,S) $ denote the matrix indexed by the sets $R$ and $S$. Let $ D $ be an incidence matrix of the graph $ \langle V_0, S \rangle $ I want to prove the following lemma Let G be a graph and $ ...
3
votes
0answers
72 views

Class of all graphs with invertible adjacency matrices

This question is a generalization of the question asked here. From the answers of the questions, I can list four classes of graphs which have invertible adjacency matrices. The class of graphs ...
2
votes
1answer
58 views

Computing limits and colimits in the Category of Graphs and Morphisms

I would like to compute limits (e.g., pullbacks, etc.) and colimits (e.g., pushouts, etc) of the finite diagrams in the category of finite Graphs and Morphisms. Question: Is there any algorithm ...
0
votes
0answers
18 views

Inverse function of a function of Laplacian Matrix

I have a function $f:\mathbb R^n \rightarrow \mathbb R^n$ defined by $f(\mathbf{X})=L(\mathbf{X})\mathbf{X}$ where $L(\mathbf{X})$ is a (nonlinear) Laplacian matrix of an undirected but of-course ...
1
vote
1answer
85 views

How can prove that inverse of transition matrix shows path equations between digraph's nodes?

If matrix T represents transitions between all nodes in digraph G, how can prove that the inverse of T represents path equation of digraph G? For example, consider following transition matrix: $$ T= ...
0
votes
0answers
21 views

Spectral partitioning of graphs with multiplicity in second Laplacian eigenvalue

The eigenvector corresponding to the second eigenvalue of Laplacian matrix, $\lambda_2(L)$, called the Fiedler vector. We can bisects the graph into two communities based on the sign of the ...
1
vote
0answers
45 views

Degree/diameter problem for the even girth case

Let $G$ be a graph with girth $g$, minimal degree $\delta$, maximal degree $\Delta$, and diameter $D$. Define $$n_0(g,\delta) := \begin{cases} 1 + \delta + \delta(\delta-1) + \cdots + ...
0
votes
1answer
54 views

How to find a dead end in a graph?

For a project about GPS systems, I'm trying to understand how can we see that there is a dead end thanks to an adjacency matrix. I know that the adjacency matrix definition is Assumed that ...
0
votes
0answers
25 views

Perron vector of the distance matrix of a tree

Increasing properties of perron vector of distance matrix from the vertex corresponding to which row sum is minimum
4
votes
1answer
52 views

Counting $K_4$'s in a Paley Graph

Let $p \equiv 1 \pmod{4}$ be prime, and let $G$ be a graph such that $|V(G)| = p$ and $\{u,v\} \in E(G) \Longleftrightarrow u-v \equiv x^2 \pmod{p}$ for some integer $x$. How many times does $G$ ...
1
vote
0answers
39 views

Graph isomorphism in terms of permutation matrix elements

The graph isomorphism problem is defined as follows. If $\Gamma_1$ and $\Gamma_2$ are two graphs with adjacency matrices $A_1$ and $A_2$ respectively, is there a permutation $\pi$ such that ...