Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [algebraic-graph-theory]

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

1
vote
0answers
19 views

Counting hypermaps with following properties

A $\textit{hypermap}$ of type $(g,n)$ is a graph embedded in an oriented surface of genus $g$ such that 1) the complement of the graph is the disjoint union of $n$ topological disks labelled from 1 ...
0
votes
1answer
48 views

Graph in genus 1

I want to understand the graph on the surface of genus 1. Let $G=(V,E,F)$ be a graph with $V,G,F$ denoting vertex, edge, and face respectively. Then the genus one condition give us that $V-E+F=0$, ...
2
votes
1answer
31 views

How to compute the Second and higher order Betti numbers of a graph?

I know that the zeroth Betti number is the number of connected components of a graph, and the first one is computed using Euler characteristics. However, I am not sure if we can compute the higher ...
0
votes
1answer
19 views

What is the adjugate matrix of the laplacian of a complete graph $K_n$?

In another post, I'm trying to understand the author's logic in a certain line of the accepted answer. "Now one uses that $nI-J=L(K_n)$, i.e. the Laplacian of the complete graph, hence $\text{adj}(...
2
votes
1answer
38 views

How is the Tonnetz grid isomorphic to a torus?

In Western music, there are $12$ notes up to transposition. In other words, music notes can be represented as integers modulo $12$ : $\big\{[0],[1],\dots,[11]\big\}$. In Tonnetz grid, moving one step ...
0
votes
1answer
29 views

Upper bound for largest eigenvalue of non-negative matrix

a) Show that the largest eigenvalue of a non-negative matrix is upper bounded by its largest row sum. b) For a non-negative matrix $M$, show that the largest eigenvalue of $M$ is upper bounded by the ...
0
votes
0answers
40 views

Graph factorisation

I have a graph having 6 vertices and its presentation is $E_{12}^4E_{13}^5E_{14}^6E_{24}^9E_{25}^2E_{35}^9E_{36}L_5^4L_6^{14}$. This means that there are $4$ edges connecting the vertices $1$ and $2$, ...
0
votes
0answers
27 views

Both vertex-transitive and edge-transitive graph is bipartite.

My first question: Let $G$ be a graph that is both vertex-transitive (Then $G$ is regular of degree k, say.) and edge-transitive , prove that $G$ is bipartite and its simple eigenvalue is $k$ and $-k$...
1
vote
1answer
43 views

Euclidean Norm of Adjacency Matrix

How can one show that the Euclidean norm of adjacency matrix $A$ of a Tree graph of order $n$ is given by $\sqrt{2} \sqrt{n-1}$? I think the following hint can work: $\Vert A \Vert = \sqrt{ \...
1
vote
0answers
122 views

Calculating the Distance Matrix from Adjacency Matrix

How would I calculate the distance matrix of a connected, simple and undirected graph from the adjacency matrix? I have 56 nodes, if that is helpful, and would need to the answer to return an array. ...
1
vote
0answers
15 views

Question regarding removal of a perfect matching in bridgeless graphs

Suppose a connected bridgeless graph has a perfect matching. If we delete the edges forming the perfect matching, then will the graph be still connected? Will the graph be still bridgeless too? ...
1
vote
1answer
52 views

Show that the largest eigenvalue of a graph is strictly larger than the largest eigenvalue of any subgraph

Let G be a connected graph and H be any proper subgraph of G (obtained from removing at least one edge or at least one vertex of G). Show that the largest eigenvalue of A(G) is strictly larger than ...
0
votes
1answer
29 views

Let G be a graph with largest eigenvalue λ and largest degree ∆. Prove that λ ≥ √ ∆.

The eigenvalue is for the adjacency matrix. I think there must be some clever inequality chain using the product of the matrix $A^2$ by an eigenvector, but i couldn't get it to work.
1
vote
0answers
33 views

Change to spectral radius due to removal of a single vertex from graph

Say we have a graph $G$ on $n$ vertices, with eigenvalues $\lambda_1 \leq \dots \leq \lambda_n$ and spectral radius $\rho_G$. Let $H$ be the induced subgraph where we remove a single vertex from $G$, ...
1
vote
1answer
33 views

Algorithmic Graph Theory - perfect matching in bipartite graph when det(A) is not 0

While learning about graphs, I came across theorem that I don't quite understand, and can't find a proof. If G is bipartite, and $\det(A) \neq 0,$ then G has a perfect matching. (Given that matrix ...
2
votes
0answers
33 views

Characterize edge-transitive Cayley Graphs

Let $G$ be a finite group and $S \subseteq G$ a symmetric subset. The Cayley graph $\Gamma(G,S)$ is always vertex-transitive, but it sufficient a simple example to show that it is not always edge-...
0
votes
1answer
112 views

Number of Triangles in a graph with $n$ vertices and $m$ edges

One can show, that a Graph with at least $n$ vertices and $m$ edges, has at least $\dfrac{4m}{3n}(m-\dfrac{n^2}{4})$. I was wondering, about the best lowest bound of this, and the best upper bound of ...
2
votes
2answers
61 views

Can we have an infinite tree in this graph?

Suppose that a graph has an infinite number of nodes set up as follows: let $V_n=\{a_{n,1},a_{n,2},\dots,a_{n,n-1}\}\cup\{b_n\}$ be a set of $n$ nodes. Let $V=\bigcup_{n=1}^\infty V_n$. I am ...
0
votes
1answer
33 views

Connection between sum of Graphs and their automorphism groups

can we say something about the automorphism group of a graph $G$ that has the property: $ G \cong A + B $ , if we know the automorphism groups of $A$ and $B$ respectively. The $+$ is the union $ \cup$ ...
1
vote
0answers
41 views

Almost all trees have non-trivial automorphism group

In their paper Asymmetric Graphs Erdős and Rényi proved that almost all trees have non-trivial automorphism group. More specifically they showed that almost all trees contain at least one so-called ...
1
vote
1answer
35 views

Adding nodes to graphs while preserving harmonic solution

I have a graph and I'm interested in adding node to my graph such that it preserve the harmonic solution (page 2). Concretely, given a graph $G = (V,E)$ with $|V| ...
0
votes
0answers
36 views

Calculate x y coordinates for a graph/digraph

I need to calculate the x y coordinates of a digraph. I have my structure as below. ...
3
votes
0answers
34 views

Largest eigenvalue of a graph is non-decreasing

I am quite new to Algebraic Graph Theory. Can anyone give me a proof of the following fact: If $G$ is a simple undirected graph and $H$ is a subgraph of $G$, then the largest eigenvalue of $H$ is at ...
2
votes
0answers
30 views

Algebraic Connectivity of Trees

Question: In a paper I'm reading it makes the following statement: "It is known that among all trees on $n$ vertices the algebraic connectivity is maximized for a star". I've searched around and I can'...
2
votes
0answers
79 views

Graph coloring and eigenvalues

I hit a stone wall with this particular problem as graph coloring was not a topic covered in any of my courses. I would appreciate any help: Let G = (V, E) be a d-regular n-vertex graph that is 3-...
0
votes
0answers
16 views

Approximate graph

Let $L_{G}$ be the Laplacian of a graph $G$ with irrational eigenvalues. I am curious to know: Is there any efficient way to find an approximate graph $\hat{G}$ such that all the eigenvalues of this ...
-1
votes
1answer
37 views

Is line graph $ L(C_n) $ of cycle graph $ C_n $ isomorphic to $ C_n $ itself? [closed]

I guess the answer is true. How can it be proved if it is true?
0
votes
1answer
38 views

Reflexive graph, meaning of the reflection

Here on the page 1 there is a definition of reflexive graph. I need an intuition how it works the morphism $e:X_0\to X_1.$ What is it and to what edge in $X_1$ it sends a vertex from $X_0$?
0
votes
1answer
38 views

The size of the stabilizer of the nth power of the Frobenius Map on a field

Fix a prime $p$. Let $F$ be a field of order $p^k$ and with characteristic $p$. Let $\phi$ be the Frobenius map, which maps $a$ to $a^p$; one can check that, for a field of characteristic $p$, it is a ...
0
votes
0answers
15 views

How to reduce the diameter of a connected triangle-free cubelike graph?

Define $X = X(G, C)$ to be a Cayley Graph (excluding any loops). Call X "cubelike" iff $G$ is equal to $V(n, 2)$ (a n-dimensional vector space on a field of order 2, or you can assume that field is $...
0
votes
1answer
33 views

Number of non-isomorphic 2-factors of $K_n$

Let $f(n,k)$ be the number of non-isomorphic 2-factors of $K_n$ containing exactly k components. Explain why the recurrence relation $$ f(n,k) =f(n-3,k-1)+f(n-k,k)$$ holds for $n \geq 4 $ and $1 \...
1
vote
1answer
36 views

Efficient algorithm for calculating flag products

This concerns flag algebras. I am wondering if there exists an efficient algorithm for calculating the below quantity. Before we can use semidefinite programming to find bounds on Turan densities, we ...
1
vote
0answers
13 views

Do strongly regular graphs maximize spectral gaps?

Across the set of d-regular n-vertex graphs, if there is a strongly regular graph in that set, it often (always, as far as I was able to check) seems to maximize the spectral gap: $\lambda_1 - \...
1
vote
1answer
38 views

Relation between eigenvectors and powers of a matrix for finding out if a graph is disconnected

I'm looking for a quick way to find out whether a graph is disconnected or not. It is if the sum of powers of it's adjacency matrices is a nonzero matrix. To speed up the process of calculating powers,...
2
votes
1answer
27 views

Eigenvectors of regular graph are annihilated by matrix of $1$s

Take a simple $k-$regular graph (every vertex has degree $k$) $G$ and its adyacency matrix $A$. Then it's known that $k$ is one eigenvalue of $A$ with associated eigenvector $u=\begin{bmatrix}1 & ...
0
votes
2answers
43 views

The Effect of Adding an Edge on the Laplacian of a Weighted Digraph

Let $G$ be a weighted digraph with Laplacian $L:=D-A$, where $D$ is the degree matrix and $A$ is the incidence matrix. Is there any result on the behavior of the eigenvalues of $L$ when we add an edge ...
0
votes
0answers
34 views

Eigenvalues of normalized vs unnormalized Laplacian of weighted digraph

Let $G$ be a weighted digraph. What is the connection between the eigenvalues of the normalized and unnormalized Laplacians of $G$. I think there is no explicit connection. We can at most find some ...
1
vote
0answers
20 views

It is possible for the nodes of a network to have a different total cost. If they have the same value in degree centrality?

I do same simulations with randoms networks and for each network and calculates different measures such degree centrality. In the network is likely more than one node to have the highest degree value. ...
0
votes
0answers
41 views

Subgraph Centrality Interpretation

I have a conceptual doubt. I have calculated the sub-graph centrality for a graph based on its adjacency matrix. However, the surprise for me, was that just two nodes have equals values, while the ...
4
votes
0answers
127 views

Count the number of sets of subsets of (Steiner?) triples

Given a set of $v$ numbers. Fix $v$. How many sets of $v$ sorted triples can be created, matching the following conditions: two triples shall have at most one number in common over all triples each ...
1
vote
1answer
55 views

Given a graph G: how to find a formula to determine the number of squares in which a vertex participates?

I should find a formula that, given a certain vertex v1 of a graph G, it returns the number of squares in which v1 participates. I managed to find a solution for triangles, but in the case of squares,...
2
votes
0answers
92 views

A problem in proving isomorphism classes of cores forming a lattice

I am reading the book "Algebraic Graph Theory" by Chris Godsil and Gordon Royle and I got confused with Lemma 6.3.3: The set of isomorphism classes of cores, partially ordered by "$\rightarrow$", ...
1
vote
1answer
47 views

Are Cayley Graphs weakly or strongly connected?

I'm working my way through Meier's Groups, Graphs and Trees and I'm confused by the proof he gives for one of Cayley's Theorems, namely Every finitely generated group can be represented as a ...
0
votes
0answers
27 views

Show that the set of Endormorphism of a given graph is equal to the set of Automorphism.

Let $A$ be the $10 \times 10 = [a_{ij}]$, where $a_{ij} = (i, j)$. Let $G$ be a graph whose vertex set is the eateries of the matrix $A$ and the two distinct vertex $(i, j)$ and $(k, l)$ are adjacent ...
2
votes
1answer
81 views

We have a connected graph with $2n$ nodes. Prove that exist spanning subgraph each node with odd degree.

We have a connected graph with $2n$ nodes. Prove that exsist spanning subgraph each node with odd degree. Idea: Let $M$ be an adjacency matrix and work all over field $\mathbb{Z}_2$. Then if $M$ ...
1
vote
2answers
296 views

Tournament bracket for a 4-players game

for Christmas a friend is trying to organize a tournament for 13 players. Each game will be played by 4 persons, each player will play 4 games and must play against everybody else. I can find a ...
2
votes
0answers
33 views

Chromatic Polynomial of Circulant Graph with Two Parameters

It is easy to get the Chromatic-Polynomial of a Circulant-Graph of size $n$ with one parameter $P[C_{n}(i),x]$. Is there a way to get an explicit formula for the chromatic polynomial of a circulant ...
1
vote
0answers
131 views

What is the mixing time of a random walk of a rook

Let $G(V,E)$ be the following graph: The vertex set $V$ is a $n\times n$ grid, and two vertices are connected $(E)$ if they lie on either the same row or the same column. This is the rook's graph: It ...
2
votes
1answer
54 views

Show that no asymmetric graph $G$ exists with $1 < \big|V(G)\big| \leq 5.$

Show that no asymmetric graph $G$ exists with $$1 < \big|V(G)\big| \leq 5\,.$$ I tried listing all the possibilities for $\big|V(G)\big| \leq 5$ to prove this statement. I did all for $2$ and $3$,...
0
votes
0answers
17 views

Endomorphism of a graph and a maximal clique

Let $G= (V, E)$ be a simple graph satisfy the following: Independence number is $3$, Clique number is $\frac{n^2}{4}$, Number of vertices is $n^2$, where $n$ is even. Let $f \in$ End$(G)$, where ...