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

learn more… | top users | synonyms

1
vote
0answers
22 views

question regarding edge space

Given a graph $G=(V,E)$ and it's edges space $\mathcal{E}(G)$ in the book by Diestel it defines given two edges sets $F,F'$ and their coefficients $\lambda_{1},...,\lambda_{m}$ and ...
1
vote
1answer
33 views

Icosahedral Graph

Let $Γ$ be a graph cospectral with the icosahedral graph having spectrum $\{[5]^1,[\sqrt{5}]^3, [-1]^5,[-\sqrt{5}]^3\}$. I have shown that Γ has 12 vertices, 30 edges, regular with each vertex having ...
1
vote
0answers
18 views

Co ordinate independent linear algebra over graphs

It is frequently said that Linear algebra is not correct until it is coordinate free or something to that effect and indeed, almost all the major results can be stated without picking a basis. ...
1
vote
1answer
26 views

Equivalent definition of cograph

A cograph is simple graph defined by the criteria $K_1$ is a cograph, If X is a cograph, then so is its graph complement, and If X and Y are cographs, then so is their graph union X union Y and ...
0
votes
1answer
33 views

Applications Of Strongly Regular Graphs

I am currently working on a thesis regarding some existence problems on strongly regular graphs. But it is actually my first encounter with them. Though i am done solving my problems, But in order to ...
-2
votes
0answers
32 views

Mathematical proof of the emergence of graph pattern [closed]

If anyone can define a emergence of graph pattern with mathematical notation, please post a response. For example trinagles in social graph. Graph (all nodes, all relationships): A graph is a pair G ...
1
vote
0answers
36 views

Linear Algebra and Graph theory

I haven't done any linear algebra for a long time and currently reading about linear algebra in graph theory and had a few queries. So i'm looking at the definition of a vertex space. Firstly let ...
1
vote
0answers
59 views

When is the direct product of two cores itself a core?

Given graphs $X$ and $Y$, a graph homomorphism $f : X \to Y$ is a function $f : V(X) \to V(Y)$ such that if $uv \in X$, then $f(u)f(v) \in E(Y)$—that is, it is a function of the vertices mapping ...
1
vote
2answers
55 views

Shortest Path on Specific Graph with one Property !?

I stuck in one challenging question, I read on my notes. An undirected, weighted, connected graph $G$, (with no negative weights and with all weights distinct) is given. We know that, in this ...
2
votes
1answer
49 views

About Cayley graphs on finite fields.

If one is given $n$ vectors of length $n$ $\in \mathbb{F}_{p^k}^n$ for some prime number $p$ and $k \in \mathbb{Z}^+$ then how can one check if they are linearly independent? (the issue is if there ...
1
vote
0answers
24 views

Unique factorization of integers vs. unique factorization of graphs

As you know, graphs can be factorized in their component subgraphs, factors such as eventually semilattices, and so on. I would like to know about the precise nature of the relation that might hold ...
0
votes
1answer
70 views

eigenvectors for hypercube graphs

Consider a set of size $n$ like $\Omega =\lbrace 1,2,\cdots ,n\rbrace $, where $n$ is a positive integer. For every $x\in P(\Omega )$, define the function $f^x:P(\Omega )\rightarrow \lbrace \pm 1 ...
1
vote
0answers
15 views

Orbital dimension of the action of $S_n$ on 2-subsets

I have a question on a proof in a paper on the orbital dimension of a permutation group. Let $G \le S^\Omega$ be a permutation group. A base for $G$ is a subset $\Sigma \subseteq \Omega$ for which ...
0
votes
2answers
49 views

Complete labeled Graph $K_6$ and Spanning Tree

I ran into a nice interview question, anyone could described it for me? from Complete labeled Graph $K_6$, remove one edge, how many spanning tree, the resulted graph has? Mathematician Learn ...
2
votes
3answers
57 views

Nice Isomorphic Question and way of finding Quickly?

I see a question about Isomorphic Graph. the question is: The first line graph is not isomorphic with which one in the second line? How we can find isomorphic graph without knowing some geometry map ...
2
votes
0answers
42 views

A discrete mathematics formulation problem in a robotic system

I am not a mathematician and I have a difficulty to formulate a problem in my work in robotics using rigorous mathematical terms. I have a system which generally consists of $l$ points, $m$ rigid ...
3
votes
0answers
20 views

For which $m,n \in \mathbb N_+$ with $m \leq n$ and $n$ large exist $n$-connected graphs which are not $m$-linked?

The question is only interesting if we search for $n$ as large as possible. Recall: A graph $G$ is $m$-linked iff for every set of $2 m$ distinct vertices $s_1, ..., s_m, t_1,...,t_m$ in $G$ there ...
3
votes
1answer
27 views

$\max(ev(A)) \leq \max(ev(R)) + \max(ev(S))$

While reading "Algebraic Graph Theory", 2nd edition, by N. Biggs (ISBN 0521458978) the author presents a proof of his lemma 8.6 on page 56 and uses a fact which he defers to another publication ...
0
votes
1answer
22 views

Find longer side of a rectangle with respect to another rectangle

So I have two rectangles: Rectangle R1 with width r1w and height r1h Rectangle R2 with width r2w and height r2h I can find the slope/aspect ratio of the two ...
1
vote
1answer
48 views

why does this argument in proof of cheeger's hold?

$$ \lambda \geq \frac{ \sum_{(i,j)\in E} [(u_i-u_j)^2 + (v_i-v_j)^2]}{ \sum_i d_i(u_i+v_i)^2 }$$ And then they say since $$\frac{a+b}{c+d} \geq \min \{\frac{a}{c}, \frac{b}{d}\}$$ it suffices to show ...
4
votes
1answer
49 views

An Example for a Graph with the Quaternion Group as Automorphism Group

I am reading "Graphs of Degree Three with given Abstract Group" (by Robert Frucht) where the author describes (somewhat tedious) algorithms to construct suitable graphs starting from a given group. I ...
0
votes
0answers
28 views

The eigenvalues after a row and a colum has been deleted from a matrix.

Now I have a zero row sum matrix $L$, and a diagonal matrix $H$, where $L$ can be reviewed as a Laplacian matrix of a directed graph. That is, the off-diagonal elements of $L$ are either $0$ or $-1$, ...
5
votes
0answers
76 views

When can an edge subset of a graph be extended to become an element of its cycle space?

Let $F$ be a set of edges in a graph $G$. Show that $F$ extends to an element of the cycle space of $G$ iff $F$ contains no odd cut. The context for this exercise is the following: Let $G = (V,E)$ be ...
1
vote
1answer
41 views

The second smallest eigenvalue of a complete binary tree

Apparently it is true that the second smallest eigenvalue of a complete binary tree is $\theta(\frac{1}{n})$. Can someone point out a reference which proves this?
4
votes
0answers
34 views

Linear Algebraic Proof of Eulerian Circuits

A standard proof of the existence of Eulerian circuits proves the following are equivalent for a connected graph $G$: (i) Every vertex in $G$ has even degree (ii) The edges of $G$ can be ...
4
votes
1answer
64 views

Is this graph and its spectrum understood?

Consider the graph whose vertices are labelled by the binary representation of the integers from $0$ to $2^{d}-1$ for some $d \in \mathbb{N}$. So its a graph with $2^d$ vertices. An edge exists ...
1
vote
1answer
36 views

What are $r(\Lambda)$ and $s(\Lambda)$?

Proposition 7.2 in Biggs Algebraic Graph Theory book says that $$\det A=\sum (-1)^{r(\Lambda)} 2^{s(\Lambda)},$$ where $A$ is the adjacency matrix of a graph $\Gamma$ and the summation is over all ...
0
votes
1answer
29 views

Randomized Algorithm for finding perfect matchings

I'm stuck on some of the theory in these notes, i'm trying to learn about randomized algorithms in general and am currently stuck on some notes regarding perfect matchings. Here is a link to the ...
0
votes
1answer
37 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
46 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 ...
2
votes
2answers
51 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
127 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
21 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
25 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
25 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
28 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
72 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
50 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
36 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
57 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 ...
4
votes
2answers
61 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
42 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
89 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
56 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 ...
6
votes
0answers
90 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
49 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
30 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
81 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
80 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
37 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. ...