Questions tagged [graph-theory]

Questions about the branch of combinatorics called graph theory (not to be used for questions concerning the graph of a function). This tag can be further specialized via using it in combination with more specialized tags such as extremal-graph-theory, spectral-graph-theory, algebraic-graph-theory, topological-graph-theory, random-graphs, graph-colorings and several others.

1,486 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
3 votes
0 answers
280 views

Semantics of neural network-like structures

Background Language (of mathematicians and most other people) has a sequential surface structure and a tree-like deep structure. So semantics usually is the semantics of such syntactical structures: ...
Hans-Peter Stricker's user avatar
3 votes
0 answers
227 views

For Ising models on finite graphs, is the gradient of Z (w/r/t coupling and field) easier to compute than Z?

Suppose we have a graph $G$ with $n$ vertices, edgeset $E$, $\mathcal{X}=\{1,-1\}^n$. The partition function of the spin-1/2 Ising model on $G$ is $$Z(J,h)=\sum_{x\in \mathcal{X}} \exp\left(J \sum_{(...
Yaroslav Bulatov's user avatar
3 votes
0 answers
142 views

Dimension of convex arrangements for hypergraphs

Suppose you have a hypergraph H on n vertices. Let d be the smallest integer such that we can find an arrangement A of convex subsets in Rd so that H represent the intersections of sets in A. Has ...
Thierry Zell's user avatar
  • 4,536
3 votes
0 answers
619 views

Graph recognition software

ISGCI lists a lot of graph classes, many of which are recognizable in polynomial time. Is anyone here aware of actual implementations of these algorithms?
Anthony Labarre's user avatar
3 votes
0 answers
315 views

Drawing a combinatorial 3-configuration of points and lines with pseudolines

This question is related to the question of drawing a combinatorial 3-configuration of points and lines with straight lines. We only relax the condition and admit drawings with pseudolines. Let us ...
Tomaž Pisanski's user avatar
3 votes
1 answer
3k views

Fast algorithm for counting the number of acyclic paths on a directed graph

In short, I need a fast algorithm to count how many acyclic paths are there in a simple directed graph. By simple graph I mean one without self loops or multiple edges. A path can start from any node ...
Szabolcs Horvát's user avatar
2 votes
0 answers
77 views

"separators" for nonplanar graphs embedded in the plane

Given a nonplanar graph $G$ drawn in the plane with crossings. Does there exist a small subset $S$ of edges of $G$ such that after the removal of all edges that intersect or share an endpoint of an ...
Hao S's user avatar
  • 181
2 votes
0 answers
72 views

Bound on the magnitude of the entries of the Laplacian pseudo-inverse

Let $L$ be the laplacian matrix of a connected graph $G$ with real positive weights and $N$ vertices, or that can be assumed to have binary weights for simplicity.My goal is to bound $\Vert L^+\Vert_{\...
sd24's user avatar
  • 21
2 votes
0 answers
83 views

Computationally decomposing a complete geometric graph into forests of stars

I'm working on the following problem: I would like to see if it possible to decompose a complete geometric graph on $8$ vertices into $5$ planar star-forests. As doing this by hand was hopeless, I ...
Jeja's user avatar
  • 21
2 votes
0 answers
41 views

Regularize a graph while embedding the spectrum of adjacency matrix

Given an irregular graph $G$ whose maximum degree is $d$, I am interested in producing a new graph $G'$ which is regular and has the spectrum of the adjacency spectrum of $G$ embedded in the spectrum ...
Chaithanya's user avatar
2 votes
0 answers
56 views

Some version of graph removal lemma

I found the following statement in 'A proof of the stability of extremal graphs, Simonovits’ stability from Szemerédi’s regularity' by Zoltán Füredi: Lemma: For any $\alpha>0$ and a graph $F$, ...
Isomorphism's user avatar
2 votes
0 answers
62 views

What is the range of connectivity for maximal IC-planar graphs?

A graph is IC-planar if it admits a drawing in the plane with at most one crossing per edge and such that two pairs of crossing edges share no common end vertex. A graph $G$ is maximal in a graph ...
L.C. Zhang's user avatar
  • 1,605
2 votes
0 answers
135 views

Generalizing Hall's marriage theorem to non-perfect matchings

Let $G = (X, Y, E)$ be bipartite graph such that $|X|=|Y|=n$. A matching $M \subseteq E$ is a subset of disjoint edges (i.e., there does not exist a pair of edges $(x, y) \in M$ and $(x', y') \in M$ ...
errorist's user avatar
  • 121
2 votes
0 answers
229 views

Injection of Catalan objects into 3-connected planar graphs

Let $C_n = \frac{1}{n+1}\binom{2n}{n}$ be the $n$-th Catalan number, counting, for example, the number of (rooted) triangulations of the $(n+2)$-gon. Let $P_n$ be the number of three-connected planar ...
Martin Rubey's user avatar
  • 5,533
2 votes
0 answers
84 views

Constructing Hamiltonian circuits in acyclic digraphs

Any directed graph $G$ lacking cycles can acquire a Hamiltonian circuit through the addition of a sufficient number of edges. Q. Is there a method to minimize the addition of edges to achieve a ...
ABB's user avatar
  • 3,898
2 votes
0 answers
73 views

Minimum cost k-edge connected subgraph

The problem of finding a k-edge connected spanning subgraph with the minimum number of edges is $ \mathcal{NP} $-hard in general. Is it the case for positive weighted graphs with "fractional ...
Bence's user avatar
  • 21
2 votes
0 answers
119 views

Graph Laplacians, Riemannian manifolds, and object collisions

To preface this question, I am a part-time game developer and full-time optimization fiend. I am working on object collisions at the moment and many resources I have found online are more-or-less just ...
HeyoItsMateo's user avatar
2 votes
0 answers
81 views

The space of immersions of a loop in a surface

Let $\Sigma$ be a compact oriented surface with boundary and $L = \mathrm{Imm}(\bigsqcup_{i=1}^n S^1,\Sigma)$ the space of all generic (i.e. transversally and at most doubly intersecting) immersions ...
Qwert Otto's user avatar
2 votes
0 answers
74 views

Clique-coclique and uncertainty

The clique-coclique inequality states that for a graph $G$ on $n$ vertices that is either distance-regular or vertex-transitive, the independence number $\alpha(G)$ and the clique number $\omega(G)$ ...
Seva's user avatar
  • 22.8k
2 votes
1 answer
78 views

"Balanced" separator which is independent set

I am looking for existence results on separators of $r$-regular graphs $G=(V,E)$, which have the property that $S\subset V$ is a separator for all $v,w\in S$ the edge $\langle v,w\rangle\not\in E$ (i....
Jens Fischer's user avatar
2 votes
0 answers
98 views

Regarding rigid graphs in the plane

Quoting from the book (page 272) Graphs and Geometry by Lovasz, we have the following theorems regarding the characterization of rigid graphs in the pane. Theorem 1: A graph $G$ is rigid in the plane ...
Pritam Majumder's user avatar
2 votes
0 answers
129 views

Permutation similarity of matrices with many distinct entries

This is related to graph isomorphism. Here matrices are square $n \times n$ with non-negative integer entries. Two matrices $A,B$ are permutation similar if there exist permutation matrix $P$ such ...
joro's user avatar
  • 24.2k
2 votes
0 answers
46 views

Maximal cliques in neighborhood graphs of partial $k$-trees (bounded treewidth)

Background My question is about a generalization of the following situation: Let $M$ be a finite metric space. Given $r>0$, the $r$-neighborhood graph $N(M)_r$ has vertex set $M$ and an edge $\{x,y\...
pyridoxal_trigeminus's user avatar
2 votes
0 answers
90 views

Counting number of perfect matchings

Counting perfect matchings in bipartite graphs is $\# P$ complete. Let $G(V,E)$ be a graph known to have $d$ number of perfect matchings. Bipartite it the obvious way by adding $E$ vertices with one ...
Turbo's user avatar
  • 13.7k
2 votes
0 answers
88 views

Number of ways to decompose a full binary tree

Given a full binary tree $T$, we decompose it into multiple sub-trees which are also required to be full binary trees. Our question is: how many different ways of decomposition are there? This figure ...
lchen's user avatar
  • 459
2 votes
0 answers
112 views

Checking existence of a non-crossing Hamiltonian path in geometric graphs

I am interested in the following computational problem. Given a geometric graph (i.e, a graph drawn in the plane so that its vertices are represented by points in general position and its edges are ...
Pritam Majumder's user avatar
2 votes
0 answers
61 views

Structure Theory for Tree Decompositions

I that $G=(V,E,W)$ is a weighted graph with positive edge weights and a finite set of vertices $K$. Let $0\le k,M\le K$ be a fixed integer. Is is known when $G$ admits the following type of ...
Timothy_G's user avatar
2 votes
0 answers
115 views

What is the analogue of a Block-Cut Tree Decomposition in directed graphs?

Let $G$ be a connected, undirected graph. We define a block $B$ to be a maximal $2$-connected induced subgraph in $G$. It is easy to see that any two distinct blocks are either disjoint or overlap at ...
Naysh's user avatar
  • 455
2 votes
1 answer
224 views

Union closed family of sets with at most a certain number of couples of sets with non-empty intersection

Is it possible to find a union closed family $\mathcal{F}$, $\emptyset \notin \mathcal{F}$, with $|\mathcal{F}| = n$ sets, such that there are at most: $$\left(1-\frac{1}{\left\lfloor \frac{n-1}{2} \...
Fabius Wiesner's user avatar
2 votes
0 answers
204 views

Chess pieces metrics in higher dimensions

A couple of days ago, I was thinking about applying the knight (the well-known piece of chess) metric to any cubic lattice $\mathbb{N}^k$, $k \in \mathbb{N}-\{0,1\}$. I suddenly realized that, from $k ...
Marco Ripà's user avatar
  • 1,119
2 votes
0 answers
41 views

Proportion of edges within a fraction of the diameter

Let $G = (V,E)$ be a finite, connected $k$-regular graph of diameter $D$. Fixing some $\epsilon>0$ and letting $v$ be a (random) element of $V$, what proportion of the other edges are at most $\...
ILoveIsos's user avatar
2 votes
0 answers
98 views

When do two path algebras share an underlying graph?

Suppose $Q$ and $Q'$ are two quivers. I am curious as to what relation $\mathbb{C}Q$ bears to $\mathbb{C}Q'$ when $Q$ and $Q'$ share the same underlying graph and only differ by direction. Since ...
tox123's user avatar
  • 416
2 votes
0 answers
53 views

A variant of the regularity lemma that depends on the number of vertices

Suppose $G = (U \cup V,E)$ is a bipartite graph with $n$ vertices on each side. For sets $X \subseteq U$ and $Y \subseteq V$, let $d(X,Y) = |(X \times Y) \cap E| / (|X||Y|)$ denote the edge density ...
Or Meir's user avatar
  • 419
2 votes
0 answers
238 views

Largest eigenvalue of a Laplacian matrix to lower bound the prime counting function?

Let $L_n$ be the Laplacian matrix of the undirected graph $G_n = (V_n, E_n)$ (which is defined here: Why is this bipartite graph a partial cube, if it is? ) with sorted spectrum: $$\lambda_1 (G_n) \ge ...
mathoverflowUser's user avatar
2 votes
0 answers
189 views

An approach to the prime number theorem with Rademacher variables and a recursive formula for the prime pi function?

Consider the bipartite graphs defined here: Why is this bipartite graph a partial cube, if it is? We do random walks on them with equal propability and since the graphs are finite and connected the ...
mathoverflowUser's user avatar
2 votes
0 answers
116 views

Average of least number of vertices to delete to obtain a caterpillar tree

Let $t=(V,E)$ be an $n$-vertex (free) tree ($n=|V|$); $V$ is the vertex set, $E$ is the edge set. There are many types of trees, among which we find caterpillar trees. As a friendly reminder, when the ...
Lluís Alemany-Puig's user avatar
2 votes
0 answers
129 views

Maximal independent set of size exactly k in interval graphs

I am interested in the following decision problem. Given an interval graph $G$ and a $k\in\mathbb{N}$, is there a maximal independent set (independent dominating set) of size exactly $k$ ? Interval ...
Hyperion's user avatar
  • 193
2 votes
0 answers
51 views

Regular graphs of tangent spheres

Problem 1. Let several non-overlapping spheres in $\mathbb{R^3}$ are given. For which $n$ it is possible that each sphere is tangent to exactly $n$ other spheres? Consider the smallest sphere. Since ...
Fedor Nilov's user avatar
2 votes
0 answers
160 views

Has Mac Lane's article "When can a graph be mapped on a torus?" been published anywhere?

I came across the following abstract of an article: Mac Lane, S., When can a graph be mapped on a torus?, Bull. Amer. Math. Soc. 42(9), 629 (1936). Abstract #341. MR1563375, JFM 62.0694.07. Q. Does ...
The Amplitwist's user avatar
2 votes
0 answers
137 views

Chromatic numbers of Cayley graphs induced by Hamming balls

The motivation for this question is to find, for a fixed odd $p$ and large $n$, sets $A\subset (\mathbb Z/p\mathbb Z)^n$ with $|A|> cp^n$ for some fixed $c$, where the difference set $A-A:=\{a-a': ...
John Griesmer's user avatar
2 votes
0 answers
288 views

Perfect matching decomposition algorithm for bipartite regular graphs

It is a well-known result that a bipartite graph can be decomposed into edge-disjoint perfect matchings if and only if it is regular. Now here comes the question. Given a bipartite regular graph, is ...
CCC's user avatar
  • 41
2 votes
0 answers
83 views

G graph connections for finite groups G

In my research, I have seen G graph connections usually when G is a Lie group and the graph is the fatgraph of a (punctured) surface. This is usually in a physics context. However, I am curious to ...
Andrea B.'s user avatar
  • 315
2 votes
0 answers
62 views

Maximize connectivity probability with a number of edges

We are given a graph $G$, whose edges are either open or closed. Initially all the edges are closed. For each edge $e$, if we choose to activate it, then after the activation, it becomes open with ...
lchen's user avatar
  • 459
2 votes
1 answer
113 views

Convergence of the average weight of an infinite path through a weighted directed graph

Consider a directed graph $G = (V, E, w)$, where $V$ is the set of vertices, $E \subseteq V \times V$ is the set of directed edges (with self-loops allowed), and $w : E \to \mathbb{R}_+$ is a weight ...
David's user avatar
  • 21
2 votes
0 answers
88 views

Odd $k$-cycle counts in graph with adjacency matrix $A$ is leading term in $\operatorname{tr} A^k$?

In a recent paper of Neeman, Radin, and Sadun, Moderate Deviations in Cycle Count, in the first line of section 7.3 they wrote $\tau_k(A)=\frac{\operatorname{tr}A^k}{n^k}+O(\frac 1n)$, but I don't ...
MikeG's user avatar
  • 665
2 votes
0 answers
38 views

Estimating the largest radius making each ball in a finite metric space into a tree

Motivation: Let $n$ be a positive integer and $(X,d)$ be an $n$-point metric space. Clearly, $(X,d)$ need not be a metric tree (e.g. take for example the discrete metric on $\{0,1,2\}$. Conversely, ...
ABIM's user avatar
  • 5,019
2 votes
0 answers
105 views

Mutual benefits of coding theory and the reconstruction conjecture

Let $G_n$ denotes all graphs with $n$ nodes. For any graph $G$ in $G_n$, the adjacency matrix $A(G)$ can be viewed as a codeword of length $n^2$. Also, the codes arises from $G_n$ is a linear binary ...
Shahrooz's user avatar
  • 4,746
2 votes
0 answers
90 views

Blind construction of planar graph with additive spanning tree count

Suppose we have two planar graphs $G_1$ and $G_2$ with number of spanning tree count $P_1$ and $P_2$ respectively then there is an easy construction which gives a planar graph with spanning tree count ...
Turbo's user avatar
  • 13.7k
2 votes
0 answers
105 views

What classes of graphs result from $\overline{T}$?

I need help in characterizing the classes of graphs that results from taking the complementary of a tree, i.e., the graph that results from removing the edges of a tree from a complete graph. More ...
Lluís Alemany-Puig's user avatar
2 votes
0 answers
105 views

Generate graphs of n nodes with 4 edges at each node

I'd like to generate and count, $C_n$, connected graphs up to isomorphism with the property that each node has 4 edges and the number of nodes is $n$. Examples for small $n$ $n=1, C_1 = 1$: there is ...
Fetchinson0234's user avatar

1
10 11
12
13 14
30