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

learn more… | top users | synonyms

0
votes
0answers
16 views

Size of the connected components

Assume that we have a disconnected graph with a random number of connected components. Is there any bounds/distribution on the size of these connected components (the number of vertices). The degree ...
0
votes
0answers
10 views

Cardinality of maximum independent set for a given degree distribution

Consider undirected graph $G(V,E)$. Assume that $f_n(k)$ be the probability mass function of degree of a vertex in $G$. Further, assume that $f_n(k)$ is an strictly decreasing function of $k$ with ...
1
vote
1answer
24 views

Matrix irreducibility. Strongly connected graph

I have this theorem from Combinatorial Matrix Theory written by Richard A. Brualdi and others. Let $A$ be a matrix of order $n$. Then $A$ is irreducible if and only if its digraph $D$ is strongly ...
0
votes
0answers
11 views

relation between regular and distance-regular graphs [on hold]

What is the relationship between regular and distance-regular graphs?
2
votes
1answer
22 views

The generating set of Cayley graphs over $Z_n$

Say we have a undirected and connected Cayley graph over $\mathbb{Z}_n$, with generating set $S=\{\pm x_0,\pm x_1,\ldots,\pm x_k\}$. Is it true that we can assume without the loss of generality that ...
1
vote
0answers
29 views

When do a Regular graph has an odd eigenvalue?

Merely looking at adjacency matrix of a regular graph, without explicit calculation, can we decide that graph will have an odd eigenvalue or not? If regularity is odd, we are sure that it will be an ...
1
vote
0answers
18 views

Interpretations of a weighted adjacency matrix's eigenvectors and eigenvalues?

Suppose that I have weighted undirected graph $G$, and the corresponding adjacency matrix which is a symmetric matrix $A$. Suppose that the edge between node $i$ and $j$ has weight $w_{ij}$, then $$ ...
0
votes
1answer
28 views

Graph and language/automaton equivalence

I'm looking for a reference rather than an answer. I think I'm just not Googling the right combination of terms. I imagine that there is a class of graphs which is equivalent to some class of ...
1
vote
1answer
70 views

Eigen value and Regular Graph (not Strongly Regular graph).

$A,B$ are 2 adjacency matrices of $d$ Regular graphs(not Strongly Regular graphs). I would like to know- 1.Results/ information related to Eigen values of A,B. There is a formula for ...
2
votes
0answers
31 views

Is there an easy way to realize a graph (i.e. get adjacency matrix) from a fundamental cut-set or loop matrix?

I am looking to realize a graph (i.e. write down its adjacency or incidence matrix) given a fundamental cut-set matrix or loop matrix (with respect to an arbitrary spanning tree). Is there some ...
1
vote
0answers
26 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
49 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
19 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
30 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
61 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 ...
1
vote
0answers
47 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
65 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
59 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
58 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 ...
-1
votes
1answer
77 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
16 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
55 views

Complete labeled Graph $K_6$ and Spanning Tree [closed]

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
61 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
45 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
23 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
28 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
26 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
49 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
56 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
33 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
78 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
42 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
35 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
69 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
37 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
40 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
50 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
54 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
203 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
24 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
29 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
29 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
77 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
38 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
60 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
65 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 ...