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

learn more… | top users | synonyms

0
votes
0answers
12 views

Independence number of Cayley graph

Pick a prime number $P$. Denote $M=\Big\lfloor (P-1)^{\frac{r-1}{r}}\Big\rfloor$. Pick $M$ numbers $g_1,\dots,g_M$ each less than $P-1$. Denote $G_{P}[S]$ to be Cayley graph on $P$ vertices ...
0
votes
1answer
18 views

Eigenvectors of a large Graph

Please i am working on a graph with a huge number of vertices, and i have a particular eigenvalue having and eigen space of dimension 19, What is the best way to find the eigen vectors. Here is what i ...
1
vote
0answers
31 views

Is there such a notion of “expansion” in groups?

Given a subset of elements of a finite group $G$, I would like it to be such that the set of all distinct words (as elements of $G$) that can be formed from this set is exponentially large in the size ...
1
vote
0answers
19 views

Describe the following graph clearly [closed]

Describe the following graph clearly
1
vote
2answers
40 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
61 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
14 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
28 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
57 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
73 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
21 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
34 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
41 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
98 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
80 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
97 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
34 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
50 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
39 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 ...