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

learn more… | top users | synonyms

0
votes
0answers
10 views

if $G$ is bipartite and regular graph,prove that we can calculate the length of smallest even cycle from its spectrum of adjacency matrix.

if $G$ is bipartite and k-regular graph,prove that we can calculate the length of smallest even cycle from its spectrum of adjacency matrix. because it is bipartite it doesn't have any odd cycle,also ...
1
vote
1answer
22 views

how we can understand from spectrum of laplacian matrix of a graph that this graph is regular or not .

how we can understand from spectrum of laplacian matrix of a graph that this graph is regular or not . if we consider $0=\mu_1 \leq \mu_2 \leq ...\leq \mu_n$ as the eigenvalue of laplacian matrix ,we ...
0
votes
0answers
16 views

orbits/canonical labelling of colored graphs

Consider the following setting. We are given a simple undirected graph $G$ and a coloring $c:V(G) \mapsto \{0,1\}.$ We can compute the canonical labelling and $\rm{Aut}(G)$ efficiently. What I ...
0
votes
0answers
16 views

show that any directed cycle graph $C_n$ will be uniquely determined by its spectrum of adjacency matrix for directed graph.

show that any directed cycle graph $C_n$ will be uniquely determined by its spectrum of adjacency matrix for directed graph. it is easy to see that the eigenvalues for directed cycle is ...
0
votes
1answer
24 views

prove that we can calculate $\sum^n_{i=1} d^{2}_{i}$ from the spectrum of laplacian matrix of graph.

prove that we can calculate $\sum^n_{i=1} d^{2}_{i}$ from the spectrum of laplacian matrix of graph.$d_i $are the degree of vertex $i$. I consider bipartite graph and try to prove this result for all ...
1
vote
1answer
36 views

prove that the only solution for the equation $L(G)=H \square K$ is $K=K_n$ ,$H=K_m$ and $G=K_{m,n}$.

suppose that $G$,$H$,$K$ are connected graphs with at least two vertices,prove that the only solution of the equation $L(G)=H \square K$ is $K=K_n$ ,$H=K_m$ and $G=K_{m,n}$. because the eigenvalue of ...
0
votes
1answer
28 views

difference of maximum eigenvalue of adjacency matrix of two graph is fewer than 1.

suppose that the difference of edges of two graph $G$ and $G^{'}$ is 1,show that $|\lambda_{max}(G)-\lambda_{max}(G^{'})|\leq1$. $\lambda_{max}$ is the biggest eigenvalue of adjacency matrix of ...
1
vote
0answers
27 views

prove this beautiful relation $ det(A^{*}_{m,n})=per(A_{m,n})$ .

suppose $P_n$ and $P_m$ are paths with $n$ and $m$ edges respectively.consider $A_n$ and $A_m$ as adjacency matrix of them.now I want to calculate the number of perfect matching of $P_n \square P_m$ ...
0
votes
0answers
24 views

How to find a legal flow in a network with upper and lower bounds?

I am trying to understand Ford-Fulkerson algorithm. How can I use Ford-Fulkerson algorithm to find legal flow and NOT MAX flow.
3
votes
2answers
39 views

how many walks go through a given edge

Assume a symmetric matrix g of $0$'s and $1$'s that represents a non-directed graph with N nodes and assume there is an edge between nodes $i$ and $j$ (i.e. $g_{ij} = 1$). I am trying to count how ...
2
votes
0answers
74 views

Is there an infinite graph that corresponds to a group which has precisely all finite groups as subgroups?

This is a followup question to Pavel C's question here . It's fairly obvious from the axiom of choice that taking the direct sum of all finite groups produces the desired group. At the associated ...
3
votes
1answer
68 views

spring representation of graphs

Suppose we have a finite graph $G$ which we want to embed in ${\bf R}^d$; fix the positions of some nodes and connect all the nodes of the graphs with ideal springs of varying strength; (i.e. there is ...
5
votes
1answer
61 views

Graph DFS, BFS and some inference

Suppose G is a connected, undirected graph with at least 3 vertexes. we know the order or visiting the vertexes in DFS and ...
1
vote
1answer
27 views

rank of adjacency matrix of line graph over $\mathbb{Z}_2$.

suppose that $G$ is connected and $A_L$ is adjacency matrix of line graph of $G$,show that the rank of $A_L$ over field $\mathbb{Z}_2$ is : $$rank_{\mathbb{Z}_2}(A_L)=\left\{\begin{matrix} n-1 & ...
7
votes
2answers
108 views

Graph and in-Degree and Drawing

We have in and out degree of a directed graph G. if G does not includes loop (edge from one vertex to itself) and does not include multiple edge (from each vertex to another vertex at most one ...
1
vote
0answers
23 views

Non-edge preserving graph homomorphism

Let $G(V,E)$ and $H(V',E')$ be two undirected graphs. Suppose $f : V \to V'$ is a function such that $\forall (u,v) \in V\times V, (u,v)\in E \implies (f(u),f(v))\in E' $ and $\forall (u,v) \in ...
1
vote
1answer
33 views

First book on algebraic graph theory?

I really like abstract algebra and I have come to appreciate graph theory more and more. I would like to check out algebraic graph theory to see what it's all about and get a feeling if it might be ...
1
vote
1answer
19 views

Minimal polynomial of adjacency graph

I would like to know why the minimal polynomial of a graph G is m(x) = Π(x-λi) where the product is taken over all distinct eigenvalues λi.
4
votes
1answer
26 views

Bipartite Graph and Matches of Graph

We know that one match from $G=(V,E)$ be a subset of edges $M \subset_= E $ in such a way non two edges of M hasn't a common vertex. Matches M is Maximal if M not a proper subset of any other matches ...
0
votes
0answers
46 views

show that there is one eigenvalue which is zero.

suppose $G$ is 3-regular graph,we cover its vertices by $T$ (that is drawn below) which every vertices of $G$ covered once by $T$,consider The adjacency matrix of $G$,show that there is one eigenvalue ...
1
vote
1answer
49 views

prove that $G$ is complete graph.

suppose that $G$ is connected graph and for every eigenvalue of its adjacency matrix we have $\lambda \geq -1$. prove that $G$ is complete graph. I think that the easiest way is to show that we have ...
3
votes
1answer
37 views

Automorphism groups of vertex transitive graphs

Does there exist a finite nonoriented graph whose automorphism group is transitive but not generously transitive (that is, it is not true that each pair $(x,y)$ of vertices can be interchanged by some ...
1
vote
2answers
28 views

Matching polynomial of a complete bipartite graph is a generalized Laguerre polynomial.

Consider a graph $G$ with $n$ vertices. Let $m_k$ be the number of $k$-edge matchings. (A matching in a graph is a set of edges without common vertices.) Several different types of matching ...
0
votes
0answers
23 views

what is determinant of adjacency matrix of forest?

suppose $F$ is a forest,prove that the determinant of adjacency matrix of this forest is $-1$ or $0$ or $1$ . I focused on trees of this forest, say that if I know eigenvalues of trees,I will ...
0
votes
0answers
36 views

A question about similarity transformation.

Say $A$ is an $n\times n$ symmetric matrix such that every row (and hence column) has exactly $d<n$ non-zero entries. Does there exist similarity transformations on $A$ which will maintain these ...
2
votes
1answer
18 views

why do we need odd cycles in this question?

prove that the graph is connected and has odd length cycle if and only if there exist natural number $r$ that all entries of $A^r$ is positive. $A$ is adjacency matrix of our graph. I know if all ...
0
votes
1answer
15 views

characterize all connected graph with the rank of its adjacency matrix is 2.

characterize all connected graph which the rank of its adjacency matrix is 2. I know that when a graph is connected,the power of adjacency matrix has no zero entry. it seems that won't help! I ...
2
votes
1answer
21 views

Round table arrrangement for 13 people using graph theory

13 Members of a new club ,meet each day for lunch at a round table. They decide to sit such that every memher has different neighbours at each lunch.How many days can this arrangement last? ...
1
vote
1answer
37 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
52 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
42 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
48 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
275 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
48 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
49 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
24 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
55 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
65 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
33 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
29 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
31 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
14 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
64 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
71 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
85 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
100 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 ...