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
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: ...
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_{(...
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 ...
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?
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 ...
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 ...
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 ...
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_{\...
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 ...
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 ...
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$, ...
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 ...
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$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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)$ ...
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....
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 ...
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 ...
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\...
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 ...
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 ...
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 ...
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 ...
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 ...
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} \...
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 ...
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 $\...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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': ...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
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 ...
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 ...