Questions tagged [algebraic-graph-theory]

Question 1

This might be a very stupid question, but I was wondering if the following is true: Let $G=A\cup B$ be a (not complete) vertex transitive bipartite graph. Is there $f \in Aut(G)$ such that $f(A)=B , f(...

Question 2

I'v been going through the book "Large networks and graph limits" by Laszlo Lovasz. A contractor for a graph parameter $f$ is defined as a $2$-labelled quantum graph $z$ which is a proper ...

Question 3

Given a simple undirected graph $G$, let $A$ be its adjacency matrix. Let $\nu_N(G)$ be the number of vectors $x$ that satisfy $Ax = 0$ over $\mathbb Z_N$. I want to find an upper bound on $\log_N \...

Question 4

Let $G$ and $H$ be two completely positive graphs i.e. graphs without having an odd cycle of length greater than $4$. Suppose $G\times H$ denotes their tensor product defined by the vertex set $V(G)\...

Question 5

Setup: Vanishing determinants in matrix families Let $Q \in \{0,1\}^{d \times d}$ be a binary matrix with zero diagonal. We define a family of $d \times d$ real matrices: $$ \mathcal{A}(Q) := \left\{ (...

Question 6

Prove that the zig-zag product of $G$ and $H$ (where $H$ is the smaller of the two) lifts $H^2$. I was reading Expander Graphs and their Applications (Lecture notes for a course by Nati Linial and ...

Question 7

TLDR: Can we express char. poly. of Mohar's Hermitian adjacency matrix of an oriented graph $G$ in terms of that of the skew-symmetric adjacency matrix of $G$ and the adjacency matrix of the ...

Question 8

Let $F = \{0,1,2\}$ be the ternary finite field. A vector $b \in F^n$ is balanced if $0,1,2$ appears in $b$ the same number of times ($n$ must be a multiple of $3$). Let $B \subset F^n$ be the set of ...

Question 9

Is it possible to transform a graph (which contains K5 or K3,3) by only adding edges or vertices, i.e. by arbitrarily expanding its structure?

Question 10

What is the set of requirements that a graph must meet so that a rectangular dual can be constructed for it? A rectangular dual is understood as a representation of a graph in which each node ...

Question 11

I understand that a symmetric adjacency matrix typically represents an undirected graph, while strong connectivity is a property of directed graphs where there exists a directed path between every ...

Question 12

I am trying to compute the center of the mapping class group of a surface of genus greater than 3. For that reason we build an alexander system of curves. The alexander system of curves is isomorphic ...

Question 13

The 'traveling salesman problem' (TSP) is a well-known NP-hard problem in combinatorial optimization, theoretical computer science and operations research with multiple variations and related ...

Question 14

Let $G = (V, E)$ be a connected graph with $n$ vertices and $m$ edges. Define a weighted adjacency matrix $A_w$, where the entry in row $i$ and column $j$ is given by: $A_w(i, j)$ = $w_{ij}$ if $(i, j)...

Question 15

I have seen that a lower bound for the second largest eigenvalue $\lambda_2$ of a d- regular graph $G$ is given by $2\sqrt{d-1}$ for large vertex graphs. This then should provide an upper bound for ...

Stack Exchange Network

Questions tagged [algebraic-graph-theory]

Vertex Transitive Bipartite graphs have a "non edges automorphism"

Why isn't every graph parameter contractible?

Upper bound on the "nullity" of a graph over $\mathbb Z_N$

Tensor product of completely positive graphs

Characterize a rational map with vanishing minors?

Prove that the zig-zag product of $G$ and $H$ (where $H$ is the smaller of the two) lifts $H^2$

On Mohar's Hermitian adjacency matrix of oriented graph

Which codimension $1$ space contains the smallest number of balanced vectors?

Is it possible to planarize a graph without deleting vertices and edges? [closed]

Necessary and sufficient requirements for a graph to possess a rectangular dualization

Can a strongly connected directed graph have a symmetric adjacency matrix?

Graph arising due to Alexander Method [duplicate]

Is this 'TSP polynomial for simple graphs' known or a variation of a known polynomial/ graph invariant?

Weighted Graph structures and approximate solutions

Smallest eigenvalue of a d-regular graph, Hoffman bound

Hot Network Questions