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
5 votes
0 answers
62 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
-1 votes
0 answers
82 views

Burnside's lemma: what am I doing wrong?

First part of my question I want to apply Burnside's lemma to compute the number of isomorphism classes of graphs with $5$ vertices. Let $V=\{1,\ldots ,5\}$. I think I have to apply Burnside's lemma ...
kubo's user avatar
  • 1,752
2 votes
1 answer
138 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 \...
gigggadag's user avatar
0 votes
1 answer
34 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
  • 363
0 votes
1 answer
104 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
1 vote
1 answer
31 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
31 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,465
0 votes
0 answers
21 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,311
0 votes
0 answers
18 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
  • 1,869
1 vote
0 answers
54 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
  • 1,869
0 votes
0 answers
17 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
83 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,311
2 votes
0 answers
53 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
  • 83
0 votes
1 answer
28 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,311
0 votes
1 answer
34 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,311
1 vote
1 answer
54 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,311
0 votes
0 answers
65 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
  • 1,812
3 votes
1 answer
68 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
  • 83
1 vote
1 answer
66 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,311
0 votes
1 answer
54 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,311
0 votes
1 answer
27 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,311
0 votes
1 answer
77 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,311
0 votes
1 answer
57 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,311
2 votes
1 answer
57 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
27 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,988
1 vote
0 answers
63 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
264 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
  • 2,352
1 vote
1 answer
47 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
34 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
0 votes
0 answers
77 views

Allocating one source to each islanded subgraph

Suppose $G$ is a graph. $E(G)$ and $V(G)$ denote the sets of the edges and nodes (vertices) of $G$, respectively. Below is shown a graph with 9 nodes and 12 edges, which I will use as an example. <...
Mahdi Rouholamini's user avatar
2 votes
1 answer
82 views

All DFT of binary numbers subsets of prime length are nonzero

Let $p$ be a prime. Consider a sequence $S$ of $p$ binary numbers $x_n \in \{ 0, 1 \}$, i.e. $S = \{x_1, x_2, \cdots, x_p\}$, where the number of zeroes in $S$ is neither $0$ nor $p$. Then the ...
Andreas's user avatar
  • 15.1k
2 votes
1 answer
64 views

Sum of squares of chromatic roots of a bipartite graph

Given a graph $G = (V, E)$, we can calculate its chromatic polynomial $P(G, k)$, and it has $n$ (complex) roots, also known as chromatic roots. It is a well-known fact that the sum of chromatic roots ...
hedgehog0's user avatar
1 vote
1 answer
96 views

Proving $r_{(k)}(X \cup Y) + r_{(k)}(X \cap Y) \leq r_{(k)}(X) + r_{(k)}(Y).$

Here is the question I am trying to prove the inequality below of part $(a)$ in it: $$r_{(k)}(X \cup Y) + r_{(k)}(X \cap Y) \leq r_{(k)}(X) + r_{(k)}(Y).$$ Let $M$ be a matroid on a set $E$ and $k$ be ...
Brain's user avatar
  • 989
1 vote
1 answer
98 views

why So $C_4 \subseteq C_2$?

Here is the question I am trying to understand its solution: Let $C_1$ and $C_2$ be circuits of a matroid $M$ such that $C_1 \cup C_2 = E(M)$ and $C_1 - C_2 = \{e\}.$ Prove that if $C_3$ is a circuit ...
Emptymind's user avatar
  • 1,869
0 votes
0 answers
110 views

How to show that $M_2[A]$ is graphic but $M_3[A]$ is not?

Here is the question I am trying to solve letter $(b)$ in it: Let $A$ be the matrix $\begin{pmatrix} 1 & 0 & 0 & 1 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 1\\ 0 & 0 &...
Emptymind's user avatar
  • 1,869
0 votes
0 answers
17 views

Relation between complete graph $K_N$ and it's complete subgraph $K_n$

Suppose we have a complete graph $K_N$ with $\{1,\ldots,N\}$ vertices. Consider a complete subgraph $K_n\subseteq K_N$ from the original graph $K_N$. Now I have a subgraph $A$ with $\{1,\ldots,k\}, k&...
Cantor_Set's user avatar
  • 1,048
2 votes
0 answers
192 views

Five new results on Conway's 99-graph problem [closed]

I realize that this editing won't make the question open (since this is against the guidelines to share results and ask to check them). Meanwhile, I'd like to replace a lot of text with a link so ...
Bertrand Haskell's user avatar
2 votes
2 answers
176 views

Ruzsa–Szemerédi problem for regular graphs

The Ruzsa–Szemerédi problem asks for the maximum number of edges in a locally linear graph, i. e. a graph in which every edge belongs to a unique triangle (equivalently, any two adjacent vertices have ...
Bertrand Haskell's user avatar
2 votes
0 answers
37 views

What is the percentage of Cayley graphs in the family of vertex-transitive graphs?

Cayley graphs are necessarily vertex transitive, but the converse is not true in general. Is there any general/asymptotic result that discusses the percentage of Cayley graphs in vertex-transitive ...
Easy's user avatar
  • 4,465
1 vote
1 answer
26 views

Event-token graph, how do you obtain this first step?

In https://writings.stephenwolfram.com/2022/03/the-physicalization-of-metamathematics-and-its-implications-for-the-foundations-of-mathematics/#mathematics-and-physics-have-the-same-foundations, ...
kiriloff's user avatar
  • 169
0 votes
0 answers
23 views

Eigenvalue corresponding to the highest eigenvalue multiplicity of normalized Laplacian spectrum

Suppose we have an undirected weighted graph (more specifically, a scale-free network). When I plot its normalized graph Laplacian spectrum, I get something like this: Normalized Laplacian Spectrum, ...
KAMYAR M. ROUDAKIAN's user avatar
1 vote
1 answer
83 views

How to compile an installation of Nauty traces?

I'm installing a program called nauty using cygwin. It starts asking to run using "configure", so far everything has been fine. However, it asks to perform a "make" to compile the ...
Diego J's user avatar
  • 41
0 votes
1 answer
143 views

Prove that $\det(A A^T) = 0$ where $A$ is the incidence matrix of a directed graph

I would like to prove the following result about graphs: Given a node-incidence matrix $A$ of a directed graph, the determinant of $A A^T$ is $0$. The element $a_{ij}$ of the incidence matrix $A$ is ...
JayDew's user avatar
  • 13
1 vote
1 answer
64 views

About the regularity of a pair of vertex subset when the density between them is less than epsilon

Given a graph $G=(V,E)$. Let $X, Y\subset V$. Recall that the density of a pair of vertex subsets $(X, Y)$ is defined as $$ d(X,Y)=\frac{e(X,Y)}{|X|Y|}, $$ where $e(X,Y)$ counts the number of edges ...
Thinkpad's user avatar
  • 383
1 vote
0 answers
45 views

On the smallest eigenvalue of the complement of a regular graph

While reading on graph theory and its applications, I came across a problem which stated if $\bar{G}$ is the complement of a regular graph then its eigenvalues are $-\lambda_i-1$ and $n-1-k$ where $G$ ...
Amir Mg's user avatar
  • 41
1 vote
1 answer
58 views

The Nordhaus-Gaddum problem over domination number of a graph and its complement

In about 1970s, Jaeger and Payan had proved the Nordhaus-Gaddum-type inequalities for domination numbers $\gamma(G)$ and $\gamma(\overline{G})$ of a graph $G$ and its complement $\overline{G}$ as: For ...
Supakorn Srisawat's user avatar
-1 votes
1 answer
140 views

Intersecting solutions

The following problem is one of those I give to my students as a homework trying to test their combinatorial skills. It is one of those technically routine "intermediate" statements one has ...
Bertrand Haskell's user avatar
0 votes
0 answers
74 views

How to minimize this set function?

I'm considering a very interesting problem. For a graph $G=(V,E)$, either directed or undirected, if we define \begin{equation} \rho(G)=\max\{|\lambda|\;|\;\lambda\text{ eigenvalue of $G$'s adjacency ...
Duber's user avatar
  • 41
0 votes
0 answers
125 views

Homomorphism from directed graph to complete graph property

A homomorphism between directed graphs is a function that maps vertices and edges from a source graph to a target graph, preserving the directionality and structure of the edges. Formally, let $G$ and ...
Zbigniew's user avatar
  • 795
0 votes
1 answer
30 views

why $\frac{1}{2} \sum_{i, j} \mathbf{A}^{(t)}(i, j)\left\|\mathbf{y}_i-\mathbf{y}_j\right\|_2^2$ can boils down to a generalized eigen-problem [closed]

I'm reading a paper, it writes "$\frac{1}{2} \sum_{i, j} \mathbf{A}^{(t)}(i, j)\left\|\mathbf{y}_i-\mathbf{y}_j\right\|_2^2$ can boils down to a generalized eigen-problem" (snapshot: part1 ...
esang's user avatar
  • 3

1
2 3 4 5
16