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

learn more… | top users | synonyms

1
vote
1answer
30 views

proof that a cycle space is a subspace

I'm looking at the following proof that the cycle space of a graph is indeed a subspace, which I don't believe to be correct. proof: It suffices to prove that $\mathcal{C}$ is closed under $+$ ...
3
votes
1answer
43 views

cycle space in graph theory

I read the following definition of the cycle space in a set of notes. Definition (Cycle space): Let $G=(V,E)$ . The cycle space of $G$ is an element of $2^{E}$ denoted $\mathcal{C}$ and is the ...
0
votes
1answer
22 views

Simple Undirected Graphs: Adjacency matrix and the $(0-1)$ incidence matrix

Are there any relation between the adjacency matrix and the $(0-1)$ incidence matrix of a simple undirected graph? They characterize uniquely the graph, so my intuition says there must be some ...
1
vote
0answers
24 views

'Refinements' of graphs

Introduction. In my (non-mathematical) research I'm regularly encountering graphs, and the need to 'refine' graphs by mapping them to other graphs. Sometimes the mapping is injective on vertices, ...
5
votes
1answer
45 views

Complement of a connected graph

What are the conditions for the complement of a connected graph to be connected? In particular, when is the complement of a connected regular graph connected? I feel that if the regularity of graph ...
0
votes
0answers
15 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 ...
2
votes
2answers
43 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 ...
2
votes
1answer
32 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 ...
2
votes
0answers
37 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
31 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
29 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
74 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 ...
3
votes
0answers
39 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
27 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
50 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
36 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
66 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
53 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
66 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
63 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
64 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
80 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
63 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
68 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
48 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 ...
4
votes
0answers
24 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
29 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
27 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
67 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
36 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$, ...
6
votes
0answers
84 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
45 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
37 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
43 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
42 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
53 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
57 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
278 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
26 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
31 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} ...