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.

2
votes
0answers
24 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
44 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
55 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
32 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
33 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
30 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
35 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
32 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
23 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
63 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
14 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
32 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
35 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
35 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
14 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
29 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
34 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
10 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
29 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
26 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
40 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
25 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
17 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
34 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
121 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
52 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
90 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
44 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
78 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
206 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
30 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
121 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
48 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
16 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 ...
0
votes
0answers
18 views

Decomposition of a block matrix related to graph Laplacians

I'm working on graph networks in a communications problem and I have trouble understanding how to work with this $3 \times 3$ block matrix related to graph Laplacians: D = \begin{bmatrix} \rho ...
0
votes
1answer
28 views

Show that each point in $V$ has the same out valency in $\Omega$

Here is a statement from the book: Let G be a group of permutations that acts transitively on $V$, a set of vertices. Let $\Omega$ be an orbit of $G$ on $V\times V$ that is not symmetric (so $\...
0
votes
0answers
10 views

Number of different sparsity patterns which are obtained by taking successive powers of a matrix

Let $M \in \mathbb{R}^{n \times n}$ be any matrix. Let $\text{bin}(M)$ be the binary matrix describing the sparsity pattern of $M$, that is $\text{bin}(M)_{ij}=0$ if and only if $M_{ij}=0$ and $\text{...
0
votes
2answers
478 views

Let G = (V, E) be a simple undirected graph with n = |V | ≥ 1 vertices…

Let G = (V, E) be a simple undirected graph with n = |V | ≥ 1 vertices. A subset U ⊆ V of the vertices is called a vc-set if for every edge {i, j} ∈ E either i ∈ U or j ∈ U (or both). Let $U^∗$ be a ...
1
vote
0answers
33 views

Intepretation of a statement in Algebraic Graph Theory book

Currently reading Algebraic Graph Theory by Godsil and Royle, and I came across the following statement: If $X$ has no triangles (cliques of size three), then any vertex of $L(X)$ with at least two ...
3
votes
1answer
63 views

Bruhat-Tits Building of $PGL_3$: What does it look like?

I am very new to this topic, and my background is mostly in graph theory and basic algebra. What I want for now is to understand the structure of the dimension $2$ complex $\mathcal{B}(PGL_3(K))$ ...
2
votes
0answers
39 views

Does the Laplacian of a path graph have the smallest eigenvalues for any tree graph of equal number of vertices?

Suppose there are two connected graphs with $|V|=n$. One is a path graph $P$ and the other is an arbitrary tree graph $T\neq P$. If $L(G)$ is the Laplacian of the graph $G$, is it true that $$L(T) - L(...
1
vote
1answer
27 views

Clique number of a generalized Johnson graph $J(n, k, k/2)$

The generalized Johnson graph $J(n,k,r)$ is defined to be the graph whose vertex set is the set of all k-element subsets of ${1,2,…,n}$, and with two vertices adjacent iff their intersection has ...
5
votes
1answer
65 views

Writing cycles of a graph as a linear combination of fundamental cycles

It is folklore that the fundamental cycles (corresponding to aparticular spanning tree) of a graph constitute a basis for its cycle space, while the proof uses the linear indepence of fundamental ...
0
votes
1answer
59 views

geodesic distance

Let $G(V,E)$ be a graph , suppose that $\vert N_{i,r} \vert $ be number of vertices whose geodesic distance from vertex $i$ is exactly $r$ edges.if $d_i$ the degree of vertex $i$ and $d_{max} := \...
0
votes
1answer
53 views

Is the 2-norm of the consensus part of a primitive row-stochastic matrix less than 1?

Let $A$ be a primitive row-stochastic matrix. By Perron-Frobenius theorem, $A$ has an eigenvalue 1 and corresponding left eigenvector and right eigenvector $\pi$ and $\mathbb{1}$, i.e., $A\mathbb{1}=1,...
1
vote
1answer
29 views

What can be said about the coherent algebra of an asymmetric graph?

Maybe as a follow-up to my last question : What can be said about the coherent algebra of an asymmetric graph? I.e. the smallest unital *-subalgebra of $M_n(\mathbb{C})$ closed under Schur (entrywise) ...
0
votes
0answers
19 views

Suppose that G is a graph and D is an orientation of G that is strongly connected. [duplicate]

Prove that if G has an odd cycle then D has an odd (directed) cycle. (Hint: Consider each pair ${ v_i , v_{i +1} } $in an odd cycle $( v_1 , . . . , v_k ) $ in G .) How tackle this question? It ...
1
vote
1answer
39 views

Adjacency algebra of asymmetric graph

What can be said about the adjacency algebra (or coherent algebra) of an asymmetric graph? Is it always $M_n(\mathbb{C})$? If not, what's a counterexample?
3
votes
1answer
139 views

The Fifth Power of a Special $8 \times 8$ Binary Matrix

My Question: We want to find an $8 \times 8$ binary matrix $\bf A$ such that $\bf A$ holds on the next three conditions: 1) The number of non-zero entries of $\bf A$ is $13$. 2) The matrix $\...