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

learn more… | top users | synonyms

1
vote
1answer
35 views

Find vertices pointing to common vertex

In a directed graph I'm interested in finding pairs of vertices pointing towards a common vertex. More in detail, from an adjacency matrix I want to derive a matrix where a positive entry denotes that ...
3
votes
1answer
33 views

Shortest path between two vertex

How we can find Shortest path between two vertex in a weighted directed acyclic graph that has positive and negative weight. in O(|V|+|E|)? thanks to all.
1
vote
1answer
25 views

Kirchoff Matrix -Tree Theorem

I'm reading a proof of the Kirchoff Matrix -Tree Theorem: If $G$ is a simple connected graph, $D$ the diagonal matrix with the vertices' degrees and $A$ the adjacency matrix, then in $M = -A+D$ ...
1
vote
2answers
43 views

Graph Degree and Some Condition

If $G$ be a Tree with degree $(5,r,s,1,1,1,1,1) $. (I wrote degree in non-increasing order). why all of this condition is True sometimes (I means on some condition)? I try to find an example that ...
0
votes
0answers
51 views

Is this composition of $K_{4,4}$ graphs minor-closed?

Following graph is a composition of $K_{4,4}$ bipartite graphs with all the edges are of same length. How do I know whether it is minor-closed or not? The definition in the Wikipedia is as follows. ...
0
votes
1answer
272 views

proof of a theorem in a paper

I was reading a paper named Decompositions of the Kronecker product of a cycle and a path into long cycles and long paths by P. K. Jha (Indian J. pure appl. Math. 23(8): 585-606, August 1992). In one ...
0
votes
1answer
47 views

Assigning $\pm 1$ values to the edges of a complete graph

I read this sentence in one combinatorics book. In graph $K_{100}$, there is a possible way to assigns number (value) from $\{+1,-1\}$ to each edge, so that the sum of all edge values connected to ...
4
votes
1answer
48 views

Sum of Nonnegative Matrix and Diagonal Matrix

Setup: Let $D = D^T > 0$ be a positive definite and diagonal $n\times n$ matrix, and let $A = A^T \in \mathbb{R}^{n\times n}$ be nonnegative with zero diagonals. That is, $a_{ij} \geq 0$ for $i\neq ...
0
votes
1answer
22 views

Find a projectivity to create a graph.

I have the tetrahedron {xyzt=0} in projective space with homogeneous coordinate (x,y,z,t). I need to create a graph but the tetrahedron in affine coordinate is {xyz=0} and I can't visualize the ...
2
votes
1answer
49 views

Partition Graph Challenging Question

I want to find in which of the following Graph, the edges cannot partitioned to triangles? Km,n,r means 3-Partite Complete Graph with m, n, and r sections. a) K7 b) K12 c) K3,3,3 d) K5,5,5 i ...
0
votes
1answer
53 views

what is the significance of the inverse of an adjacency matrix?

Suppose I have a graph and I calculate the eigenvalues of the adjacency matrix and find that there are some number of zero eigenvalues. Do zero eigenvalues have any significance? Also is there a good ...
1
vote
1answer
30 views

Promises in the hidden subgroup formulation of graph isomorphism problem

In the 3rd slide of the talk, Graph isomorphism, the hidden subgroup problem and identifying quantum states, by Pranab Sen, the promise of the problem is defined as follows. Given: $G$: group, ...
0
votes
1answer
27 views

Constructing an eigenvector for a certain matrix representing a graph with a perfect code

Let $A$ be a symmetric $(0,1)$-matrix whose row sum is $r.$ Suppose I have a $(0,1)$ vector $v$ such that $$Av = \vec{1} - v.$$ By taking the vector $$u = \vec{1} - (r+1)v$$ we see that $$Au = A ...
3
votes
1answer
29 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 ...
0
votes
0answers
13 views

compare magnitude of elements of Perron-Frobenious vector

Consider a nonnegative, primitive matrix $A=(a_{ij})_{n\times n}$ with positive diagonals. From the Perron-Frobenious theorem, the spectral radius $\rho(A)$ is an eigenvalue of $A$ and we have a ...
0
votes
1answer
61 views

Example of non-Abelianness of symmetric group for graphs

I know that for $n \ge 3$, $S_n$ is non-Abelian. I would like to work out an example in terms of graphs so to make it sure that I understand it right. A symmetric group of graphs of four vertices, ...
3
votes
0answers
42 views

maximizing the inverse degree in a graph

The inverse degree in the graph $G$ is defined as \begin{align*} r(G) = \sum_{i=1}^N \frac{1}{d_i}, \end{align*} where $d_i$ is the degree of node (vertex) $i$. Is the connected graph with maximum ...
2
votes
1answer
49 views

Automorphisms groups of direct product of graphs

Direct product of graphs $G$ and $H$ is a graph $G\times H$ for which $V(G\times H)=V(G)\times V(H)$ $E(G\times H)=\left\{(g_1,h_1)(g_2,h_2):\ g_1g_2\in E(G),\ h_1h_2\in E(H)\right\}$. Direct ...
0
votes
0answers
58 views

number of symmetries of an arbitrary graph

Given an (undirected) graph G, is there way to (approximately) estimate the order of Aut(G)-- i.e., the number of permutations ...
1
vote
0answers
32 views

Spectrum of an infinite graph independent of labelling

Does there exist an infinite graph whose spectrum does not depend upon the labelling of the graph? While evaluating the spectrum, I am considering adjacency matrix of the infinite graph as a bounded ...
2
votes
1answer
78 views

Eigenvalues of the distance-k graph of a graph

Let $G$ be a (finite, simple, connected) graph. Define the distance-$k$ graph $G_k$ to be the graph with the same vertex set and $x\sim y$ iff $d(x,y)=k$. A graph is integral if all of the eigenvalues ...
0
votes
0answers
86 views

Prove that T is transitive if and only if the score of the $k^{th}$ vertex ($s_k$) = '$k-1$' for $k =1,2,\ldots. n $

There is a transitive tournament (T) with $n > 1$ vertices and the score sequence is defined as $s_1, s_2, \ldots,s_n$ Prove that T is transitive if and only if the score of the $k^{th}$ vertex ...
2
votes
1answer
58 views

Graphs that are vertex transitive but not edge transitive

A graph $G$ is vertex transitive if for any two vertices $x$ and $y$ of $G$ there is an automorphism of $G$ that sends $x$ to $y$. Similarly, $G$ is edge transitive if for any two edges $e$ and $f$ of ...
2
votes
0answers
24 views

Correspondence between cycle covers of the digraph of a matrix and the nonzero terms in its characteristic polynomial expansion using mixed diagonals

Let me start with some definitions and notations. Definition: The graph of a symmetric matrix $A=[a_{ij}]_{i,j=1}^{n}$ is defined to be a simple graph $G$ where, $i\sim j$ in $G$ if $a_{ij}\neq 0$, ...
1
vote
1answer
87 views

Is there a cayley graph for the Klein bottle?

When studying algebraic topology we learned about the fundamental group of the $2$-torus $T^2$ which is isomorphic to $$\langle a, b \mid aba^{-1}b^{-1} \rangle$$ (the free abelian group on two ...
1
vote
2answers
79 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 ...
2
votes
1answer
38 views

Existence of a (19, 6, 1, 2) strongly regular graph

While reading Is there a graph with 99 vertices... I became curious about smaller graphs satisfying the property. According to Wikipedia, strongly regular graphs must satisfy the relation: ...
2
votes
1answer
69 views

Algebraic Combinatorics

Let $K_{r,s}$ denote the complete bipartite graph, defined on $r + s$ vertices $\{v_1,v_2,...,v_r,w_1,...,w_s\}$, with an edge between $v_i$ and $w_j$ for $1 ≤ i ≤ r$ and $1 ≤ j ≤ s$. By ...
3
votes
2answers
82 views

Is 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$ ...
1
vote
0answers
47 views

Automorphism group of a bipartite regular graph

Showing an automorphism group of complete bipartite graph $K_{n,m}$ is easy. I'm wondering if there is an classification of automorphism groups of bipartite regular graphs. Did anyone heard something ...
2
votes
1answer
46 views

the solution of matrix polynomials

In order to get the eigenvalues of \begin{equation} P=\left[ \begin{array}{cc} 0_{n\times n} & I_{n\times n} \\ -A & -B% \end{array} \right], \end{equation} where $A$ and $B$ are both $n\times ...
1
vote
0answers
29 views

automorphisms of the infinite trivalent tree

Let $T$ be the infinite trivalent tree. I want to show that if $\alpha,\beta,\alpha',\beta'$ are vertices of the tree such that the distances $d(\alpha,\beta)$ and $d(\alpha',\beta')$ are equal, then ...
0
votes
1answer
57 views

Find eigenvalues from a given relation.

This is a simple problem of linear algebra. One without knowing graph theory may solve it. I am missing a small easy logic. Description: Let $G$ be a graph with $n$ vertices and $G^c$ is its ...
1
vote
1answer
79 views

The properties of graph and its relation with the largest eigenvalue

When I was solving questions from a graph theory book by Bondy and Murty, I came across this problem: ( Note: $\Delta$ represents the maximum degree. ) Show that: a) no eigenvalue of a graph ...
0
votes
1answer
46 views

Explicit expression of eigenvalue and eigenvector of a graph

Could any one tell me what kind of graph has the explicit expression of its eigenvalue and eigenvector? Thanks!
0
votes
2answers
57 views

Proof matrices and their eigenvalues

Let $C=A-B$ where $A=\begin{bmatrix}I &0\\ 0&0\end{bmatrix}$ and $B$ is a Laplacian matrix of a connected graph, so sum for rows is null and it doesn't have any zero row(or column). ...
1
vote
0answers
44 views

How can I prove that a particular family of graphs is integral?

I'm working with an infinite family of graphs that seem to always have all integral eigenvalues, and I'd like to find some way to prove that (if it's true). Call the graphs $G_{n,k}$ and define them ...
1
vote
2answers
42 views

Chromatic Polynomial for a Graph

I have The chromatic polynomial for this is given as $P(G_e,\lambda)=\lambda(\lambda-1)^3$. How is this calculated?
3
votes
0answers
102 views

Chromatic Number and Chromatic Polynomial of a Graph

I'm studying chromatic numbers and chromatic polynomials of graphs at the moment and I know the subtle connection between the two: Let $G$ be a graph, $\chi(G)$ be it's chromatic number and $p_G(x)$ ...
0
votes
0answers
12 views

Quasiprimitive almost simple

Let $\Gamma$ be a graph, $G<X\leq\operatorname{Aut}(\Gamma)$, and $X$ has a maximal normal subgroup $N$ which is intransitive on $V\Gamma$. It is obvious that $\dfrac{X}{N}$ is quasiprimitive on ...
1
vote
0answers
40 views

Eigenvalue gap of a graph

How to compute the eigenvalue gap of a graph. For example how does it work for the star graph? Let us assume that every node has a self-loop. Since this should make the eigenvalues positive, I would ...
0
votes
0answers
56 views

Quotient group and graphs

what is the Quotient group and how we can compute it for Petersen graph? what properties of graphs are incurred in the quotient groups of graphs? for example suppose G=(V,E) , D is the free abelian ...
2
votes
1answer
51 views

A question about the interlacing of symmetric matrices (graph interlacing)

Reading the paper of Haemers on graph interlacing I came across the following question. Let $A$ be a real symmetric matrix partitioned into $m \times m$ blocks and suppose $B$ is a $m \times m$ ...
1
vote
0answers
65 views

clique number of generalized Johnson graph $J(4n-1,2n-1,n-1)$

The generalized Johnson graph $J(v,k,r)$ is defined to be the graph whose vertex set is the set of all $k$-element subsets of $\{1,2,\ldots,v\}$, and with two vertices adjacent iff their intersection ...
1
vote
2answers
315 views

Chromatic polynomial of a grid graph

I have the following graph with $nm$ vertices: ...
0
votes
0answers
30 views

What is a quotient of a building by a lattice?

For an algebraic group $G$, we may defined a building associated to $G$. Let $B = B(G)$ be the corresponding building. I don't understand much about the concept quotient $B/\Gamma$ of a building $B$ ...
1
vote
0answers
118 views

characteristic polynomial of graph

I have 2 questions about how to find the characteristic polynomial of some graphs. If G is a simple cycle with n vertices and n edges, $C_n$, I need to find the characteristic polynomial of $C_n$ ...
0
votes
1answer
41 views

Undirected Graph Partitioning

Given an undirected Graph G(V,E) and provided we can remove edges from the graph. I have to tell is it possible to partition the graph so that each component contains exactly 2 vertices with one edge. ...
1
vote
1answer
91 views

what is the maximum number of faces with n vertex in planar graphs?

what is the maximum number of faces with n vertex in planar graphs? v=number of vertices f= number of faces for example if v=3 -> max(f)=2 v=4 -> max(f)=4 (a triangle with a point in inner face of ...
9
votes
0answers
123 views

How many arrays with crossed cells, order of rows/columns irrelevant

I've been struggling with this simple problem for months though as I am a newbie to… well, maths, there's high chance someone more educated than myself may get it right! Let's consider an array or a ...