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

learn more… | top users | synonyms

1
vote
0answers
19 views

Describe the following graph clearly [on hold]

Describe the following graph clearly
1
vote
2answers
39 views

How to use spectral graph theory to get a measure for graph symmetry?

I looked at graphs, like $K_{12}$ or Frucht's graph and wondered if their spectrum, more specific the degenercies of their eigenvalues, is a mesaure for the (a)symmetry of the corresponding graph? ...
2
votes
3answers
59 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?
0
votes
0answers
13 views

Extremal eigenvalues & eigenvectors of skew-adjacency matrix

I am looking for ways to obtain the extremal eigenvalues and eigenvectors of the skew-adjacency matrix of a directed graph. The graphs I am interested in are not regular (but they have a maximum ...
0
votes
0answers
23 views

showing that $h$ and $G_v$ generate $Aut(G)$.

Let $G$ be a connected vertex-transitive graph and let $G_v$ denote the stabilizer of the vertex $v$. If $h$ is any automorphism of $G$ for which $d(v,h(v)) = 1$, and $G$ is symmetric, then $h$ and ...
0
votes
0answers
18 views

there is no distance- regular graph with intersection array $\left \{ 3, 2, 1; 1,1, 3 \right \}$.

By finding an appropriate eigenvector, show that there is no distance- regular graph with intersection array $\left \{ 3, 2, 1; 1,1, 3 \right \}$. can you little help me how should I make an ...
0
votes
0answers
27 views

graph is distance-regular if and only if the number of $i,j$ walks of length $k$ depends only on $d(i, j)$.

Show that a connected graph is distance-regular if and only if for each positive integer $k$, the number of $i,j$ walks of length $k$ depends only on $d(i, j)$. I think I must use this relation ...
1
vote
2answers
67 views

Finding an eigenvalue of a special cubic graph

My question is about a cubic graph $G$ that is the edge-disjoint union of subgraphs isomorphic to the graph $H$ that is as below: I want to prove that $0$ is an eigenvalue of the adjacency matrix ...
0
votes
0answers
49 views

Feedback vertex set

May $D=(d_1, d_2, d_3 ... d_n) \in \big\{0, 1, ... ,n-1\big\}^n.$ We build the graph $M_D$: $\forall i \in \big\{1, 2, ...,n\big\} $ we consider the sets $R_i$ and $S_i$: $R_i= \begin{cases} ...
0
votes
0answers
26 views

Asking for some reference for square of a graph Laplacian matrix. ($L^2$ or $L^{\dagger^2}$)

I am looking for some information regarding Laplacian squared of a graph. ($L^2 or L^{\dagger^2}$) I couldn't find anything special. Specially the graphs with positive weights on edges. Any related ...
6
votes
1answer
53 views

Representing Petersen graph in root system $E_6$

It is well-known that Petersen graph is an strongly regular graph with parameters (10,3,0,1) and can be considered as complement graph of $L(K_5)$ and its spectrum is $\{3,1^5,(-2)^4\}$. Also, It is ...
3
votes
2answers
53 views

Prove that a graph which is constructed with matrices is strongly regular

Suppose that $F_q$ is a field with $q$ elements. Consider all $2\times d$ matrices with entries in $F_q$, so we have $q^{2d}$ matrices. Consider each matrix as a vertex, and two vertices $A$ and ...
1
vote
0answers
40 views

suppose $r$ is the second largest eigenvalue of adjacency matrix of $srg(n,k,\lambda ,\mu)$,prove that $r< \frac{k}{2}$

suppose that $G$ is strongly regular graph $srg(n,k,\lambda ,\mu)$,suppose $r$ is the second largest eigenvalue of adjacency matrix,prove that $r< \frac{k}{2}$ ,in addition $r\leq \frac{1}{2}(k-1)$ ...
2
votes
1answer
56 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
1answer
38 views

suppose $G$ is strongly regular graph srg$(n,k,\lambda,\mu)$,prove that $k\geq 2\lambda -\mu +3 $.

suppose $G$ is strongly regular graph srg$(n,k,\lambda,\mu)$,prove that $k\geq 2\lambda -\mu +3 $. I tried to show that $\mu(n-1)\geq k(\lambda+2)$(*) if I can prove that,then I add $-\mu k$ to both ...
5
votes
0answers
78 views

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 ...
1
vote
1answer
46 views

how to construct graph $G$ where $\operatorname{Aut}(G)\simeq \mathbb{Z}_n$

for group $\mathbb{Z}_n$ (arbitrary $n$) I want to make a graph $G$ where $\operatorname{Aut}(G)\simeq \mathbb{Z}_n$, for $n=2$ it is $P_n$ and $K_2$ (if I am not wrong), how should I construct $G$?
1
vote
1answer
26 views

give an example to show it is possible to remove one vertex and the multiplicity of one of eigenvalue rise.

I know that if we consider a graph $G$ with $\lambda$ as one of its eigenvalue of adjacency matrix with multiplicity $n$ ,there is a vertex of $G$ that by removing it ,the multiplicity of $\lambda$ ...
5
votes
2answers
76 views

Vertex-transitive graphs and deletion of vertices

Consider the following graph property: for each $u, v \in V(G)$, we have that $G - u \cong G-v$. This property implies a high "symmetry" of the graph. We can easily see that every vertex-transitive ...
0
votes
0answers
72 views

Complexity of graph radius algorithm

I am a bit new so I hope I don`t break any rules. I have an algorithm: Given H = (V, E) a graph. If v ∈ V and r ∈ N, we will note with SH(v, r) the sphere of radius r with the center in v: SH(v, r) ...
0
votes
0answers
34 views

question about omitting two petersen graph from $K_{10}$ .

prove that if we omit two petersen graph which has no common edges from $K_{10}$ we will get a cycle with 10 vertices which every two vertices which are in front of each other will be adjacent. ...
0
votes
0answers
28 views

characteristic polynomial of adjacency matrix of join of two graph.

suppose that $G$ is a graph with $n$ vertices and $H$ a graph with $m$ vertices,if we consider join of $G$ and $H$ prove that :$$\chi(G \vee H,\lambda)=(-1)^m ...
1
vote
1answer
35 views

What kind of studies are this?

at this link there are quite a number of images reporting different patterns inside a circle: what kind of studies are this and does this belongs to a specific branch of the mathematics ?
1
vote
1answer
65 views

Graph and one Sequence challenge

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
1answer
29 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
27 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
20 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
20 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
31 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
40 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
33 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
32 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
26 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
40 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
95 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
79 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 ...
0
votes
1answer
96 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
33 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 & ...
6
votes
2answers
118 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
28 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
46 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
21 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.
2
votes
1answer
36 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
49 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
54 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
46 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
38 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
32 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
21 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 ...