Questions tagged [algebraic-graph-theory]

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

Filter by
Sorted by
Tagged with
2
votes
1answer
38 views

Why is the universal covering tree of $G$ unique up to isomorphism and how to obtain the covers of $G$ of quotients thereof?

Let us start from defining the universal covering tree of a graph $G$ to be the infinite tree $\mathcal{T}$ such that any cover $H$ of $G$ is a quotient of $\mathcal{T}$. It is well known that the ...
-1
votes
0answers
19 views

Help finding Equation from difference of 2 different equations with unknown variables

I have the following data Item # Distance Travelled Profit earned 1 31 38.9008 1 19 23.3999 1 18 22.1269 2 19 6.2642 2 23 7.6113 What I'm trying to work out is if this is enough information to ...
0
votes
1answer
53 views

What kind of graph coloring is this?

Assume a very simple graph with 3 points: V0—V1—V2 The following represent all the different possible colorings using 3 colors. I’ve labelled all of the types of colorings that are isomorphic (is that ...
3
votes
0answers
102 views

Visual analysis of adjacency matrices

Given a simple graph $G$ and its adjacency matrix $A$, one may naturally consider the following graph $A_G$: $V(A_G)=\{(i,j):i<j,a_{i,j}=1\}$ $E(A_G)=\{\{(i,j),(k,l)\}\in2^{V(A_G)}:(|i-k|=1\text{ ...
1
vote
0answers
25 views

Graph automorphisms and union of graphs

I have a question, so please allow me to ask here. Thank you. My question is: Let $G$ be a union of directed graphs $G_1, \ldots , G_n$, that is, $G=G_1\cup\cdots\cup G_n$. If $f:G\to G$ is a morphism ...
0
votes
0answers
19 views

Equivalence of two Bayesian Network Structures

Consider two Bayesian networks with binary random variables, whose directed acyclic graphs are shown in the following figure Define $p_G(A,B,C)$ and $q_{G'}(A,B,C,D,E)$ as the joint probability ...
0
votes
0answers
20 views

Maximum vertex+edge weight connected subgraph of an undirected graph

I need to find a connected subgraph (having exactly $k$ vertices) of a given graph $G=(V,E)$ with undirected edges, where the subgraph maximises some objective function of both the edges and vertices. ...
0
votes
0answers
19 views

Mobius Inversion Theorem Proof

Does anyone of you, know the basic approach to understand the Mobius Inversion Theorem? The theorem states that: Let $N_{e}(x)$ ($N$ sub equal to) be a real-valued function defined for all $x$ in a ...
1
vote
1answer
60 views

The Diameter of resulting graph by sum of two unions.

Let's say we have a graph $T$, which is also a spanning tree of a graph $G$, $T$ is connected, now let's say the diameter of $T$ is $x$. Now, what would be the diameter of : $$ (T \cup T^c) + (T \cup ...
1
vote
0answers
29 views

Expand acyclic graphs to acyclic graphs

I am learning about Kruskal Algorithm to find minimal spanning trees. To show that the spanning tree which is constructed with that Algorithm is minimal, I need to prove this statement: Let $G=(V,E)$ ...
1
vote
1answer
66 views

eigenvalues of line graph

Let $G$ be a simple graph with incidence matrix $M$. a) Show that the adjacency matrix of its line graph $L(G)$ is $M^t M − 2I$, where $I$ is the $m × m$ identity matrix. b) Using the fact that $M^t M$...
2
votes
0answers
79 views

what is the purpose and consequences of Eigenvalues in graph theory? [closed]

I am trying to understand Eigenvalues and their repercussions in graph theory. I have read that Eigenvalues help describe certain parameters of graphs which provide information about the general ...
1
vote
0answers
44 views

Graph coloring as a matrix?

Is there anything interesting to be gained from representing a graph coloring as a matrix, where the rows correspond to vertices of the graph and columns to colors, and entry i,j = 1 if vertex i is ...
2
votes
0answers
61 views

Graph Theory Research Questions [closed]

I was just pondering some things about graph theory and I was hoping someone could weigh in or direct me to a good resource. The first is maximal clique polynomials, which would be a polynomial where ...
4
votes
1answer
132 views

Show that if $X\times X \cong Y \times Y$, then $X\cong Y$

This is a question from the book Algebraic Graph Theory, by Godsil and Royle Show that if $X\times X \cong Y \times Y$, then $X\cong Y$ Where $X$ and $Y$ are arbitrary undirected simple graphs. Let $...
-2
votes
1answer
60 views

Show that the entries of the main diagonal of square matrix give the degrees of the vertices of the graph

Let $G$ be a simple graph, and $A$ be its adjacency matrix. Prove that the entries on the main diagonal of $A^2$ (matrix multiplication $A×A =A^2$) give the degrees of the vertices of $G$. Does this ...
1
vote
1answer
72 views

What does "$|i-j|$ is a square" means in graphs

I am reading a pastime from issue 6 of "Le Monde 2" -a) What is the size of the largest set $S\subset\{0,...,x\}$ such that it does not contain two integers $i$, $j$ such that $|i-j|$ is a ...
1
vote
0answers
41 views

Non hamiltonian cubic graphs

It is known that almost all cubic graphs are hamiltonian (see here) However, I did not find any information about non-hamiltonian cubic graphs online. If you know some properties/literature about non-...
0
votes
1answer
42 views

The largest clique in $X\times Y$ is the smallest of the largest cliques in $X$ and $Y$

From the book Algebraic Graph Theory by Godsil and Royle Show that $\omega(X\times Y)$ is the minimum of $\omega(X)$ and $\omega(Y)$. Here $\omega(X)$ denotes the size of the largest clique in $X$. ...
1
vote
1answer
68 views

In a bipartite graph, any cycle of length equal to the girth is a retract.

This is an exercise from the book Algebraic Graph Theory by Godsil and Royle. Show that in a bipartite graph, any cycle of length equal to the girth is a retract. We say that a subgraph $Y$ of $X$ ...
0
votes
0answers
21 views

Size of a path defined on a Hamiltonian cycle

Let $G=(V,E)$ (Such that $\vert V\vert$) be a Hamiltonian cubic graph and $v\in V$. We represent a graph as a cycle with vertices labeled in such a way that $(0,\ldots ,n-1)$ is a Hamiltonian cycle ...
2
votes
1answer
33 views

Requirements for embedding a graph in n-dimensional euclidean space

Given a graph $G = (V, E)$, I want to embed it into a $n$-dimensional space $\mathbb{R}^n$, while respecting the following conditions: Let $x_i$ be the $n$-dimensional embedding of vertex $v_i$. If $...
1
vote
1answer
53 views

Diameter of a Johnson Graph

I'm reading the book Algebraic Graph Theory, by Godsil and Royle, and I am currently doing the first chapter's exercises. In one of them I am tasked with determining the diameter of a Johnson Graph ...
1
vote
1answer
38 views

Can't understand K-Truss Graph properties

Cross-posted on Operations Research SE. I'm trying to understand K-Truss Graphs which are defined as such The k-truss is a subset of the graph with the same number of vertices, where each edge ...
1
vote
1answer
78 views

the disjoint union of complete graphs is ds, with respect to adjacency matrix.

In Which graphs are determined by their spectrum? proposition 6 states "the disjoint union of complete graphs is DS, with respect to adjacency matrix." A graph is said to be DS (determined ...
2
votes
1answer
76 views

spectrum of a regular graph and its girth

How we can find the girth (the shortest cycle) of a regular graph from its adjacency spectrum? I know we can find the number of closed walks of length $k$ by: $$\operatorname{tr}(A^k)= \displaystyle\...
1
vote
0answers
43 views

Measuring cluster-ness in graph by operation on the adhjacency matrix

We have a weighted graph G=(V,E). Each vertex represents a d dimensional node embedding. the feature matrix $H\in \mathbb{R}^{|V|...
0
votes
0answers
16 views

Let $G$ be a graph. Then every locally strong endomorphism of $G$ is metric endomorphism.

Let $G$ be a graph. Then every locally strong endomorphism of $G$ is metric endomorphism. I am giving the definitions. $f\colon G\to G$ is call locally strong if its a homomorphism and for $x,y$ in $...
1
vote
1answer
61 views

Graph states: two equivalent definitions

I know two definitions of graph states: $|G\rangle = K^{a} |G\rangle = \sigma_x^{a} \otimes \sigma_z^{b} |G\rangle$ for all $a \in V$ vertices and for all $b\in Na$ connected to $a$ through an edge. $...
3
votes
1answer
76 views

Graphs on Cylinders

I know that nonplanar graphs can be embedded without self-intersection into a $g$-holed torus, for sufficiently large $g$. In particular, I know that $K_5$ and $K_{3,3}$ can be embedded into the torus....
1
vote
1answer
47 views

What paths between vertices is this method actually counting?

Context From Discrete Mathematics and Its Applications by Kenneth H. Rosen: Let $G$ be a graph with adjacency matrix $A$ with respect to the ordering $v_1, v_2, ..., v_n$ of the vertices of the ...
1
vote
1answer
70 views

Why no line graph has -2 as a main eigenvalue?

The eigenvalue $\lambda$ is said to be a main eigenvalue if $\mathcal{E}(e)\not \subseteq \textbf{j}^{\perp}$, where $\mathcal{E}(e)$ is the eigenspace of $\lambda$ and $\textbf{j}$ is the all-1 ...
0
votes
1answer
35 views

Kernel of a product based on an irreducible, rowstochastic matrix

Let $G$ be a irreducible, rowstochastic $n \times n$ matrix and let $A = (G-I)$ and $B = (G-\lambda I)$, where $|\lambda|\leq 1$ is an arbitrary eigenvalue of $G$. I am interested in learning about ...
2
votes
0answers
38 views

If a product of expander Cayley graphs is connected, is it automatically an expander?

Let $G$ and $H$ be finite groups, generated by $s_1,\dotsc,s_d\in G$ and $t_1,\dotsc,t_d \in H$, respectively ($d\geq 1$). Assume that each of the Cayley graphs $\operatorname{Cay}(G,\{s_1,\dotsc,s_d\}...
0
votes
1answer
84 views

Singular values of incidence matrix of a graph [closed]

Let $\mathcal{G}$ be an undirected graph and $M$ its corresponding oriented incidence matrix. Then, can the singular values of $M$ give an indication of how dense/sparse the graph? Particularly, the ...
2
votes
1answer
62 views

Prove that any 3-regular graph with diameter 2 and order 10 is isomorphic to Petersen graph.

As I was reading this paper [Classification of Regular Planar Graphs with Diameter Two, DOI: 10.1007/s10114-005-0607-4], I noticed a lemma that cites in Algebraic Graph Theory. Case 3: Let $p=10$. ...
0
votes
0answers
37 views

How is this graph decomposable?

I am looking at an exercise regarding decomposable graph. Above is an undirected graph. I know one necessary and sufficient condition for a decomposable graph is that any cycles of lengths $\geq4$ are ...
1
vote
1answer
30 views

Is a cycle composed of two primitive cycles from different equivalent classes also primitive?

Suppose we have two primitive cycles $C_1$ and $C_2$ which belong to two different equivalence classes. Is the cycle $C_1 C_2$ also primitive? My intuition is that this cycle is also primitive, but I ...
5
votes
1answer
72 views

What is the zeta function for a finite graph?

I am getting myself familiar with the background of the non-backtracking operator on a finite graph. The zeta functions of a finite graph is relevant, though not directly related to my project. ...
0
votes
0answers
20 views

Cayley graph over ring structure

I am currently working on algebraic graph theory and would like to know whether Cayley graph over ring structure has been defined in any of the research papers. I tried finding but I could not get any ...
1
vote
1answer
59 views

Algebraic Graph Theory - Bounding Spectral Radius

If $X$ is a graph with maximum valency $a$, show that $\sqrt{a} \leq \rho(A(X)) \leq a$.(From Algebraic Graph Theory by Godsil & Royle.) I think I have to use the Rayleigh quotient to prove the ...
1
vote
1answer
78 views

Interpretation of the Laplacian operator in graphs

I am studying graphs right now, and I have just discovered the definition of Laplacian operator: $\Delta:M(G)\longrightarrow Div(G)$ That is given by the formula: $$\Delta(f)=\sum_{v\in V(G)}\Delta_{v}...
0
votes
0answers
30 views

Importance of studying certain graphs on the dihedral group

I am actually not sure if this is the right platform to ask this, but I hope someone can enlighten me. I am an undergraduate math student, and I recently started reading academic papers on graph ...
0
votes
0answers
63 views

Finding transformation matrix errors using set of (non-)linear equations (or any other method for that matter)

I must preface that I'm not learned in proper mathematical notation, and my training never advanced further than basic calculus in undergrad. But here we go. I seek advice on how to best approach my ...
1
vote
1answer
40 views

Show that if $G$ is 8-edge-connected ; if ${E}'$ is a sub set of $E$ edges of $G$ and $|{E}'|=8$ then $w(G-{E}')\leq 2$

This is an example similar to Bondy and Murty graph theory book. in that exercise $G$ is k-edge-connected and here it's 8 edge connected. Show that if $G$ is 8-edge-connected, and if ${E}'$ is a sub ...
0
votes
0answers
37 views

Norm on graphs & functions with same nodes

I was thinking of the following setting. Image we have a finite graph with nodes $V$, $|V| = n$. Furthermore we look at functions from each node into the real numbers, so $f:V\rightarrow \mathbb{R}$. ...
0
votes
0answers
52 views

First order logic: finding and proving homomorphisms

Let $ \sigma= \{E\}$ be a signature with a 2-arity relation symbol E, let A be an arbitrary σ-structure, and let G be a σ-structure, which is given by the following drawing. (a) Give an endomorphism $...
1
vote
1answer
309 views

What is the automorphism group of a complete bipartite graph isomorphic to?

I couldn't quite figure out what the automorphism group of a complete bipartite graph $\Gamma (K_{r,s})$ is isomorphic to. I did some back-of-the-envelope calculations and found that $\Gamma (K_{r,s})$...
0
votes
1answer
50 views

Conditions for uniqueness of the solution of a linear system of equations

QUESTION Consider the positive integers, $N,\{T_n\}_{n=1}^N,J$, where $N>\max\{T_1,...,T_N\}$, $N>J$. $1_{a}$ denotes the $a\times 1$ vector of ones. Consider the system of equations $$ \begin{...
3
votes
1answer
72 views

Proving that $|\operatorname{Aut}(C_n)|=2n$.

Question: Prove that $|\operatorname{Aut}(C_n)|=2n$. This the question $2$ chapter $2$, in the book Algebraic Graph Theory, Godsil and Royle. I've managed to prove that $\left|\operatorname{Aut}(C_n)\...

1
2 3 4 5
14