Skip to main content

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
0 votes
1 answer
70 views

An interesting Hamiltonian path problem concerning the connectivity of subgraphs

Suppose there are $n$ players, $P_1,...,P_n$, requiring any $t<n$ players to be able to talk to each other, each two players can share a telephone line, when there is a logical connection path (...
X.H. Yue's user avatar
3 votes
0 answers
40 views

Exercise 2.2 In Stanley's Algebraic Combinatorics

This is Exercise $2.2$ In Stanley's Algebraic Combinatorics. I don't have much work to show because despite being stuck on this problem for a long time, I haven't got a clue how to start. $\mathcal{C}...
koifish's user avatar
  • 3,100
2 votes
1 answer
28 views

Decomposing complete graphs into edge-disjoint spanning trees

Given a complete graph with $N = 2k$ vertices, is it always possible to decompose it into $k$ edge disjoint spanning trees? If so, then is there a general procedure to find these trees? I would also ...
Dani007's user avatar
  • 314
0 votes
1 answer
34 views

What are the properties of the incidence matrcies of undirected graphs

Here is the definition of incidence matrix I find on Wikipedia https://www.wikiwand.com/en/Incidence_matrix Suppose we have a graph $G$ with $N$ nodes and $e$ edges (we only consider undirected graphs ...
LeoB's user avatar
  • 1
2 votes
0 answers
36 views

Graphs with same number of closed walks

The motivation for the post comes from a pair of cocyclic graphs on 10 vertices. We call a pair of non-isomorphic graphs cocyclic if there is a bijection between the vertex sets defined by the ...
Sajid Bin Mahamud's user avatar
2 votes
0 answers
22 views

Constructing a graph with a given Fiedler vector

Given $\boldsymbol u \in \mathbb{S}^{n-1}$, how could one construct a (weighted, connected) graph whose Fiedler vector $\lambda_{2}(D-A)$ — that is, a unit-norm eigenvector corresponding to the second-...
JakeH's user avatar
  • 21
1 vote
1 answer
74 views

Asymptotic upper bound on nullity of biadjacency matrix of connected bipartite graph of bounded-degree

Let $G$ be a bipartite graph with parts $V$ and $W$ of sizes $m$ and $n$, respectively. The edge-set is $E \subseteq V \times W$. The adjacency matrix of $G$ takes the form $$ A = \begin{pmatrix} 0 &...
Pranay's user avatar
  • 271
2 votes
1 answer
19 views

Question regarding linear resolution of an ideal

Let $R=K[x_1,x_2,\ldots,x_n]$. $I(G_{(x)})$ is edge ideal of $G_{(x)}$. In the proof of theorem 2.13 given in paper uses the fact that $L=xI(G_{(x)})$ has linear resolution if and only if $I(G_{(x)})$ ...
Okky's user avatar
  • 21
1 vote
1 answer
60 views

Is union and intersection of two graphs preserve graph isomorphism?

Suppose $G_1 = (V_1,E_1)$ and $G_2 = (V_2,E_2)$ be two graphs, then union of two graphs is $G_1\cup G_2 = (V_1\cup V_2, E_1\cup E_2)$ and $G_1\cap G_2 = (V_1\cap V_2, E_1\cap E_2)$. Now, it is given ...
ann's user avatar
  • 49
0 votes
1 answer
38 views

On the permutation of vertex set and automorphism of graphs.

I’m novice in graph theory, I greatly appreciate if you find any mistake and edit that mistake. Suppose I have a unlabelled simple, undirected, graph $G$. Vertex set consist of $N$ vertices. Now, we ...
Cantor_Set's user avatar
  • 1,082
1 vote
0 answers
154 views

Using Bass-Serre theory to determine the strucure of a subgroup of a free construction

Suppose that we have $G^* = HNN(G,H,t)$ a HNN-extension. If $K = \langle \bar{G},t \rangle$ where $\bar{G} \leq G$, then is it true that $K = HNN(\bar{G},\bar{G}\cap H,t)$? How to determine the ...
Greg's user avatar
  • 422
1 vote
1 answer
76 views

Question regarding intersection of two graphs

Suppose we have two simple, connected, undirected graphs $G_1 = (V(G_1),E(G_1))$ and $G_2 = (V(G_2),E(G_2))$. Now from book of Diestel (Graph Theory), intersection of two graph is nothing but, \begin{...
Cantor_Set's user avatar
  • 1,082
0 votes
0 answers
12 views

Cospectrality of square grid minors

I'm working on an interesting computational game theory problem. One way to dramatically improve the runtime is to develop a computationally efficient invariant that can characterise the graphs I'm ...
Yi Chen Chong's user avatar
1 vote
0 answers
57 views

Family of graphs characterized by their eigenvalues

Studying the convergence/divergence of certain processes on simple graphs (processes similar to Kostant games on graphs), I'm confronted with the task of characterizing graphs whose spectra must ...
Gianfranco's user avatar
3 votes
2 answers
277 views

Is Johnson Graph J(N, 2) circulant?

I have stumbled upon the problem of diagonalizing the matrix of a Johnson graph $(N,k)$ with $k=2$. From Wikipedia and several other references I found the explicit form for the eigenvalues https://en....
Alessio Catanzaro's user avatar
0 votes
0 answers
48 views

Homomorphic product of graphs

I was looking into how the eigenvectors of graphs change upon taking products. For instance, the cartesian product of two graphs $G_1 \square G_2$ has eigenvalues $\lambda_i + \mu_j$ for $\lambda_i$ ...
Jeff's user avatar
  • 401
0 votes
2 answers
137 views

Show that $1^T(tI-B)^{-1}\mathbb{1}=0$ when $B$ is the adjacency matrix of a regular graph

I want to show that $1^T(tI-B)^{-1}\mathbb{1}=0$ when $B$ is the adjacency matrix of a regular graph on $2m$ vertices, where $1$ denotes the all ones vector. This is part of a bigger problem and it's ...
kubo's user avatar
  • 2,067
0 votes
1 answer
38 views

Operations of walk regular graphs

We have that a walk regular graph is one in which $A^k$ is a constant diagonal matrix for all $k \geq 0$. Given this, do operations on walk regular graphs also result in walk regular graphs? For ...
Jeff's user avatar
  • 401
0 votes
1 answer
24 views

Using Outer Products and Matrix Multiplication to Compute Tour Weight in Traveling Salesman Problems

Set up Let $G$ be a complete, weighted, and directed graph with $N$ vertices as in the asymmetric Traveling Salesman Problem (TSP). Without loss of generality, let the the vertex set $V$ of $G$ be ...
NonDairyNeutrino's user avatar
0 votes
0 answers
23 views

Do graph laplacian eigenvectors/values beyond the second smallest eigenvalue mean anything?

It is my understanding that the multiplicity of the smallest eigenvalue (the zero eigenvalue) of the graph laplacian $L=D-A$ equals the number of connected components of a graph, while the second ...
LYB's user avatar
  • 13
0 votes
0 answers
27 views

Check the linear independency of a set of cycles in a graph?

As I am reading wikipedia and some material: A basis for cycles of a network is a minimal collection of cycles such that any cycle in the network can be written as a sum of cycles in the basis. Some ...
xue's user avatar
  • 175
0 votes
0 answers
25 views

Reconstructing a graph from a subgraph and spectral properties

There's a graph $G$ which is conjectured to exist. We know it's $k$-regular, and we know its spectrum. (I don't think the exact problem is important for this question). $G$ is much too large to ...
Kristaps John Balodis's user avatar
5 votes
0 answers
93 views

On the walk-generating function

While I was reading Norman Biggs' Algebraic Graph Theory I came across the following (Page 12 2g) exercise/additional result: Let $g_{ij}(r)$ denote the number of walks of length $r$ in $\Gamma$ from ...
Tropax's user avatar
  • 373
2 votes
1 answer
156 views

Does there exist $g\in Aut(G)$, but $g^2\neq e$?

Let $G(V,E)$ be a self-complementary graph such that $|V|\geq 2$ Does there exist $g\in \text{Aut}(G)$, but $g^2\neq e$ ? All i know is that : Given that $G$ is self-complementary, we have $G \cong \...
DARK Orn's user avatar
  • 125
0 votes
1 answer
40 views

Graph homomorphism and distance

We consider $f$ a homomorphism between graphs $G$ and $H$, that is a function from the vertex set of $G$ to the vertex set of $H$ that preserves edges. Given $u,v \in V(G)$, is there any sort of ...
Jeff's user avatar
  • 401
0 votes
1 answer
224 views

Polynomial Algorithm for checking if graph is Weisfeiler Leman isomorphism test counterexample

I am currently working on isomorphism tests between graphs, however. Is there a polynomial algorithm for determining whether a graph is a potential 1-WL counterexample? By counterexample I mean graphs ...
Eauriel's user avatar
  • 21
1 vote
1 answer
41 views

From adjacency Matrix can we find the maximum number of disjoint matching pairs of a simple undirected graph?

I came across this problem which boiled down to finding the maximum number of pairs of disjoint edges given a simple undirected graph. After doing some research I came across Edmond's Blossom ...
Chandana Deeksha's user avatar
0 votes
1 answer
33 views

Homomorphically equivalent but not a subgraph of each other

Referring to the definition of homomorphic equivalence here, is it possible that two homomorphically equivalent graphs are not a subgraph of each other?
Easy's user avatar
  • 4,485
0 votes
0 answers
23 views

Affiness, $U_{2,4}$ and $M(K_4).$

I do not know why $M(K_4)$ is not affine over $GF(2)$ or $GF(3)$ but it is affine over all fields with more than 3 elements. I proved that $U_{2,4}$ is $\mathbb F$-representable iff $|\mathbb F| \geq ...
Intuition's user avatar
  • 3,127
0 votes
0 answers
20 views

Lift and frame matroids.

I want to read more about lift matroid and frame matroid and their flats and relations to signed graphs, do you know any basic resources for this?
Emptymind's user avatar
  • 2,087
1 vote
0 answers
63 views

The rank of $X$ in $M^*(G).$

If $X$ is a set of edges in a graph $G,$ how can we know the rank of $X$ in $M^*(G)$ in terms of $G[X].$ Where $M^*(G)$ is the dual of the graphic matroid of $G.$ Some thoughts We know that for all ...
Emptymind's user avatar
  • 2,087
0 votes
0 answers
19 views

Spectrum of a strongly regular graph with a vertex deleted

I want to know if it is possible to calculate the characteristic polynomial of a strongly regular graph denoted $SRG(n,k,\lambda,\mu)$ when one or two of its vertices are deleted. I have found some ...
user401163's user avatar
0 votes
0 answers
90 views

Hyperplane Areangements and contraction.

I am trying to understand an idea presented in McNulty book, matriods a geometric introduction about the new hyperplane arrangement $\mathcal{A}^{''} = \{ H \cap H_x | H \in \mathcal{A}\}$ where $\...
Intuition's user avatar
  • 3,127
2 votes
0 answers
56 views

Some properties in Projective Geometry

I am trying to understand the following two Propositions in James Oxley's book "Matroid Theory" Prop. 6.1.3 Let $M$ be a simple rank-r matroid and $\mathbb F$ be a field. The following ...
Hope's user avatar
  • 95
0 votes
1 answer
49 views

Help undsersanding matroid closure, loops, contraction and duality.

These ideas are being used a lot, but I cannot justify why they are correct: If M is a matroid and $T$ a subset of $E(M).$ Then $$(a)\ cl(T) = T \cup \{e \in E(M) - T: e \text{ is a loop of M/T}\}.$$ ...
Intuition's user avatar
  • 3,127
0 votes
1 answer
46 views

The basis of a regular matroid.

I know that a regular matroid is one that can be represented by a totally unimodular matrix. I also know that a rank r totally unimodular matrix is a matrix over $\mathbb R$ for which every submatrix ...
Intuition's user avatar
  • 3,127
1 vote
1 answer
56 views

affine geometries that are self-dual matroids.

I want to know which of the affine geometries $AG(n,q)$ are self-dual matroids? I have proved before that uniform matroids $U_{n,m}$ that are self duals are those who satisfies that $m = 2n.$ I am ...
Intuition's user avatar
  • 3,127
0 votes
0 answers
86 views

Approximating the trace of the power of a large adjacency matrix

The motivation for this question is counting cycles in directed graphs with millions of vertices. Given a large (not necessarily symmetric) adjacency matrix $A \in \{0, 1\}^{n \times n}$, where $n \...
Vezen BU's user avatar
  • 2,150
3 votes
1 answer
101 views

Understanding how to find the dual of a matroid.

I am trying to understand the following picture of a matroid and its dual but I found myself not understanding exactly what we are doing to find the dual: ]1 Roughly speaking, according to some ...
Hope's user avatar
  • 95
2 votes
1 answer
92 views

Show that $C^*(e,B)$ is the unique cocircuit that is disjoint from $B - e.$

I want to prove the following question: Let $B$ be a basis of a matroid $M.$ If $e \in B,$ denote $C_{M^*}(e, E(M) - B)$ by $C^*(e,B)$ and call it the fundamental cocircuit of $e$ with respect to $B.$\...
Intuition's user avatar
  • 3,127
0 votes
1 answer
68 views

if $X$ is independent and $E(M) - X$ is coindependent, show that $X$ is a basis and $E(M) - X$ is a cobasis.

here is the question I am trying to solve: In a matroid $M,$ if $X$ is independent and $E(M) - X$ is coindependent, show that $X$ is a basis and $E(M) - X$ is a cobasis. I know how to prove that a set ...
Intuition's user avatar
  • 3,127
0 votes
1 answer
36 views

Let $A\subset B$ be flats of a matroid $M$ such that $r(A)=r(B)<\infty$. Then $A = B$.

I want to prove the following lemma: Let $r$ denotes the rank. Lemma. Let $A\subset B$ be any flats of a matroid $M$ such that $r(A)=r(B)<\infty$. Then $A = B$. My thoughts are: I know that $cl(A) =...
Intuition's user avatar
  • 3,127
0 votes
1 answer
82 views

Proving that $ \beta(M) = \beta (M - e) + \beta (M /e).$

Here is the statement I am trying to prove: If $e \in E$ is neither a loop nor an isthmus, then $$ \beta(M) = \beta (M - e) + \beta (M /e).$$ Here are all the properties I know about the Crapo's beta ...
Intuition's user avatar
  • 3,127
0 votes
1 answer
71 views

Why always the Crapo beta invariant value greater than or equal zero?

Here are the definitions of the Crapo beta invariant I know: My definition of the Crapo's beta invariant of a matroid from the book "Combinatorial Geometries" from page 123 and 124 is as ...
Intuition's user avatar
  • 3,127
2 votes
1 answer
68 views

A poset $P$ is series-parallel iff it contains no subset isomorphic to $Z_4$

I'm trying to prove that a finite poset is series-parallel (i.e. it can be built up from a one-element poset using disjoint union and ordinal sum of posets) iff it contains no subset isomorphic to $...
Armando Patrizio's user avatar
2 votes
0 answers
43 views

Cycles of a graph may determine the characteristic polynomial of the adjacency matrix.

I am seeking proof of the following point. Any reference or direct proof would be appreciated. Let $H$ be a directed graph, and denote by $\mathcal{H}_i$ the set of all subgraphs of $H$ with exactly $...
ABB's user avatar
  • 1,996
1 vote
0 answers
65 views

Why is the formula of edges$=$nodes$-$1 for modeling radiality very slow?

Suppose $G$ is a graph. $E(G)$ and $V(G)$ denote the sets of the edges and nodes (vertices) of $G$, respectively. I need a spanning subgraph of $G$ (let’s call the subgraph $g$). The subgraph must be ...
Mahdi Rouholamini's user avatar
1 vote
1 answer
280 views

Number of $r$-colorings of a path graph with a specific color appearing $k$ times: A budgeted graph coloring

How to count proper vertex colorings of a path graph with $n$ vertices using at most $r$ colors with the condition that a specific color is used exactly $k$ times? When the condition is relaxed, the ...
Amir's user avatar
  • 8,414
1 vote
1 answer
51 views

Regular permutation groups and 2-closure

I'm currently working through Dobson, Malnič, Marušič's Symmetry in Graphs (2022), and am trying to prove the following proposition (pp. 208): Exercise 5.2.1 If $G \leqslant \text{Sym}(\Omega)$ is ...
Tom's user avatar
  • 65
0 votes
0 answers
56 views

Adjacency matrix with Periodic boundary condition - Torus

I have a 2-dimensional square lattice of nodes . I need to find the distance between the nodes (adjacency matrix), but I should account for periodic boundary conditions. This means that the 2d sheet ...
user3284182's user avatar

1
2 3 4 5
16