# Tagged Questions

**3**

votes

**0**answers

157 views

### Generalised de Bruijn Graph

I have encountered sets of the following type, consisting of words over a finite aphabet $A$.
If $S$ is such a set, then
$S$ is finite,
No word in $S$ is part of another element of $S$, and
every ...

**3**

votes

**0**answers

128 views

### The mean number of vertices in small connected components of random geometric graphs

I place $N$ points on a circular plane of radius $R$, and draw edges to connect points that are less than or equal to some distance $D$ to form a set of graphs or cliques $G_i$. As a function of $N$, ...

**3**

votes

**0**answers

116 views

### On the faces of the multicommodity flow polytope

Consider the multicommodity flow problem on an undirected graph with k source-destination pairs and specified capacity constraints on the edges. The set of concurrently achievable flows ...

**3**

votes

**0**answers

183 views

### Bounds on number of small minimal cut-sets in graph?

David Karger developed an algorithm for estimating graph reliability; a key lemma in this algorithm is that if a graph has minimal cut-set size $c$, then the number of cut-sets of size
$\alpha c$ is ...

**3**

votes

**0**answers

174 views

### Minimum sum of distances of G for spanning tree of G

Let $G=(V,E)$ be a undirected simple graph, and $\Omega(G)$ denote the set of spanning trees of G. Does the next funcion
$$l(G) = \min_{T \in \Omega(G)}\quad \sum_{uv \in E} \mbox{dist}_T(u,v)$$
have ...

**3**

votes

**0**answers

118 views

### Polynomials in graphs

I have part of a physical simulation which I've realised can be modelled using a directed graph where each node is a polynomial. I then calculate this graph by functional composition and summing to ...

**3**

votes

**0**answers

235 views

### Minimal-edge graph with diameter 2 and bounded max degree

Consider all connected simple graphs with diameter $d = 2$ and maximal vertex degree $\Delta$. In my particular practical case $\Delta = 4$, but general problem is much more interesting — probably ...

**3**

votes

**0**answers

237 views

### Domination number of hamming graphs

The problem of finding the domination number of Hamming graph $H(3, 2n)$ ($n$ is an integer) was given as a homework for my discrete math class. I didn't manage to solve the question. But later the ...

**3**

votes

**0**answers

297 views

### Computing Quantum Dimensions

Hi,
in "Jaeger’s Higman-Sims state model and the B2 spider" by Greg Kuperberg
(arxiv:math9601221v1, 1996) there are some quantum dimensions listed in the
"Discussion" part. Evidently quantum groups ...

**3**

votes

**0**answers

203 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 ...

**3**

votes

**0**answers

126 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

396 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

402 views

### cell complexes and higher graph theory

Suppose that, on an intuitive basis, one defines a "2-graph" $(V,E,F,\partial)$ as a collection of vertices, oriented edges and oriented faces, all of which should be considered as abstract objects ...

**2**

votes

**0**answers

40 views

### Approximating a max-cut's intersection with other cuts

(This is a cross-post from the Theoretical Computer Science Stack Exchange.)
For the purposes of this question, a cut in a graph $G$ is the edge-set $\delta (S)\subseteq E(G)$ between some vertex-set ...

**2**

votes

**0**answers

49 views

### lower bound on A(k,4,floor(k/2))

A(k,4,r) is the independence number of the Johnson graph J(k,r).
What is the best known asymptotic lower bound on A(k,4,floor(k/2)) ?
I only obtained ...

**2**

votes

**0**answers

55 views

### Edge-disjoint path-systems in infinite digraphs

Let $ D=(V,A) $ be a directed graph without backward-infinite paths and let $ \{ s_i \}_{i<\lambda},U \subset V $ where $
\lambda $ is some cardinal. Assume that for all $ u\in U $ there is a ...

**2**

votes

**0**answers

37 views

### Is the size of maximum matching in vertex transitive 3-uniform hyper-graph on $n$ vertices always $\Omega(n)$?

What is the best known lower bound on the size of the maximum matching in a vertex transitive $3$-uniform hyper-graph?

**2**

votes

**0**answers

102 views

### About the small set expansion conjecture

Given a graph $G=(V,E)$ and a $\delta > 0$ one wants to calculate $h(G,\delta)=min_{\vert S\vert \leq \delta \vert V \vert } \phi(S)$. ($\phi(S) = \frac{ E(S,\bar{S}) }{d min \{\vert S \vert , n - ...

**2**

votes

**0**answers

82 views

### the choosing of an independent set in a specific $k$-partite graph

Let $k\geq2$ be an integer, a graph $G=(V,E)$ is called $k$-partite if $V$ admits a partition into $k$ classes such that every edge of $G$ has its ends in different classes: vertices in the same class ...

**2**

votes

**0**answers

94 views

### Isomorphic subcategories of directed graphs and presets

For the purposes of this post, a digraph (directed graph) has neither loops nor multiple parallel edges, and a preset is an ordered pair consisting of a set $S$ and a preorder (viz., a reflexive and ...

**2**

votes

**0**answers

44 views

### Counting labelled graphs according to sets of size 3

In this question we are counting labelled simple graphs. No concept of isomorphism is involved.
Let $G(n,e,t)$ be the number of labelled simple graphs with $n$ vertices, $e$ edges, and $t$ sets of ...

**2**

votes

**0**answers

48 views

### finding dominating cycles in $2K_2$-free graphs

A cycle $C$ in a connected graph $G$ is called dominating if its complement $V(G)-V(C)$ is an independent set. H.J. Veldman proved in 1983 (Disc. Math. v.43, 281-96) a general result that in ...

**2**

votes

**0**answers

66 views

### Total number of spanning trees of a set of graphs

Given an undirected graph G with $n$ nodes, we can compute its number of spanning trees in polynomial time using Kirchhoff's matrix-tree theorem. Now consider a more complicated setting, in which each ...

**2**

votes

**0**answers

60 views

### relationship of max-sat and min-cut in theory and practice

I have been using MAX-SAT solver to obtain the exact ground state of ising spin glass model:
For 1D periodic model, for systems with 50 binary variables and interaction range of 15th nearest ...

**2**

votes

**0**answers

71 views

### Are there two-sided $\varepsilon$-expanders with independent sets of size $(1-\varepsilon)n$?

Terry Tao's notes on expander graphs has the following exercise:
Exercise 13 Let $G$ be a $k$-regular graph on $n$ vertices that is a two-sided $\epsilon$-expander for some $n > k \geq 1$ and ...

**2**

votes

**0**answers

53 views

### Fixing (non)-independency of a the subfamilies of finitely many events.

I'm would be interesting in any construction of a probability space with n events (n is given), where for every subset of these events, it is also given whether or not, the family is mutually ...

**2**

votes

**0**answers

79 views

### What is the significance of the median eigenvalue?

When I look at the spectral density plots of my (usual) laplacian graphs, they spike at the median eigenvalue. But what significance for the graph/matrix (which originates from a network) does the ...

**2**

votes

**0**answers

129 views

### Connected graph as connected space

Let $G$ be locally finite graph. By $|G|$, we mean the Freudenthal compactification of the 1-complex $G$, see chapter 8 of "Graph Theory" by Diestel. It is followed from Lemma 8.5.4 of Diestel's book:
...

**2**

votes

**0**answers

84 views

### Minimum number of perfect matchings in a regular bipartite graph

Is there a lower bound on the number of perfect matchings in a $k$-regular bipartite graph?
One can use Hall's marriage theorem and induction on $k$ to derive the lower bound of $k$. I can't come up ...

**2**

votes

**0**answers

34 views

### “drift” of a random graph $G(n,p)$ with $p=\alpha\ln{n}/n$

Suppose $G\sim G(n,p)$ with $p=\alpha\ln{n}/n$ for some large constant $\alpha$. I wish to show a certain "drift" property of $G$, which can roughly be phrased as follows: if $u$ is "not that far" ...

**2**

votes

**0**answers

52 views

### Weighted graph similarity

I have the following problem. Consider an undirected biconnected graph with $n$ vertices and $m$ edges ($n \leq m \leq n(n-1)/2$). The $m$ edges of the graph are then "populated" by integer weights ...

**2**

votes

**0**answers

72 views

### Problems Solvable/Decidable by Counting Shortest Paths in Graphs

This questions is based on a dispute, whether it would be possible to calculate 'nice' routes in Manhattan, if the road network is assumed to be a rectangular grid and, that 'nice' means that there is ...

**2**

votes

**0**answers

90 views

### second smallest eigenvalue Laplacian - submodular set function

Let $G$ be a connected unweighted undirected graph. In addition, let $\lambda_2(L(G))$ be the second smallest eigenvalue of the Laplacian matrix of graph $G$. Is $\lambda_2(L(G))$ a submodular set ...

**2**

votes

**0**answers

71 views

### When polynomial GI implies polynomial (edge) colored GI?

(edge) colored graph isomorphism is GI which
preserves the colors (of edges if it is edge colored).
There are several reductions using transformations/gadgets
of (edge) colored GI to GI. For edge ...

**2**

votes

**0**answers

56 views

### Looking for similar centrality measurement on graph

I'm working on a graph problem somehow related to centrality measurement. Given an undirected, unweighted tree $T$ and a vertex $v$, let $D_i(v)$ be the set of vertices in $T$ that are i hops from ...

**2**

votes

**0**answers

73 views

### Properties of a smallest tournament with domination number $k$

For some tournament $T$, let $\gamma(T)$ denote the cardinality of a smallest dominating set of $T$.
Denote by $f(k)$ the minimum number of vertices of a tournament $T$ having $\gamma(T) = k$.
From ...

**2**

votes

**0**answers

202 views

### Computing the chromatic polynomial of graph modulo $x-3$

The chromatic polynomial of graph $P(G,x)$ is univariate
polynomial which counts the number of colorings of $G$
with $x$ colors for natural $x$.
Graph is not $k$ colorable iff $P(G,k)=0$.
The ...

**2**

votes

**0**answers

52 views

### Regular graphs with unimodal subdegrees that are not distance-regular

Distance regular graphs are known to exhibit the following property: starting from an arbitrary vertex $\alpha$, let $k_i$ denote the number of vertices at distance $i$ from $\alpha$ (in terms of ...

**2**

votes

**0**answers

79 views

### Characterize the equivalence class of bipartite graphs obtained from each other by elementary row operations on their adjacency matrices

Let $M$ be an $m\times n$ matrix real matrix. Let $G$ be a bipartite graph, with partitions $A$ and $B$, such that $|A|=m$ and $|B|=n$. A node $i\in A$ is linked to a node $j\in B$ if and only if ...

**2**

votes

**0**answers

91 views

### What is the projective dual of a planar graph?

Everybody learns the usual definition of the dual of a planar graph when edges are preserved and faces are mapped to vertices. Everybody learns the projective duality. What if we apply it to a ...

**2**

votes

**0**answers

59 views

### Smallest distribution of points with genuinely different clusterings

An hierarchical clustering algorithm for (finite) sets of points in a given metric space is essentially determined by its linkage criterion, which defines the distance between arbitrary (finite) sets ...

**2**

votes

**0**answers

94 views

### Proofs about Forbidden Minors

I am working on a problem which involves proving that a particular graph is a forbidden minor of the class of graphs that i am working on.
Now i read kuratowskis theorem for planarity but i still ...

**2**

votes

**0**answers

114 views

### Is there an universal (dis)similarity measure between two structures?

I'm always wondering is there an universal (dis)similarity measure
between two structures (let's say between two undirected simple
graphs)? I mean, not "the measure with universal parameter that we
...

**2**

votes

**0**answers

55 views

### Minimal set of 2-2 Pachner move null sequences on a (nonplanar) trivalent graph?

A "null sequence" is of course a sequence of Pachner moves (inside a closed
area) that doesn't change the trivalent graph. E.g. doing the same Pachner move
twice (leads to orthogonality of 6j symbols) ...

**2**

votes

**0**answers

90 views

### Counting regular Hypergraphs

The problem of counting regular graphs on $n$ vertices is notoriously hard. It seems like counting regular hypergraphs on $n$ vertices should be much easier (I am placing no uniformity condition). ...

**2**

votes

**0**answers

103 views

### Hamiltonian Matroids

Similar to graphs, a Matroid $M$ is said to be Hamiltonian if there is a base $B$ of $M$ and $e \in M-B$ such that $B + e$ is a cycle of $M$. Is there any literature on this?
EDIT: Actually my ...

**2**

votes

**0**answers

89 views

### Size of b-matching constructed from b maximal matchings

The Question: Let $G$ be a (simple) graph and let $b\in\mathbb{N}$. Suppose that we have $b$ disjoint edge-subsets $M_1,\ldots , M_b$ satisfying the following condition: The set $M_1$ is a maximal ...

**2**

votes

**0**answers

148 views

### The Turán problem for graphs with given chromatic number

The ordinary Turán problem for graphs asks, "Given a graph $H$, if $G$ is an $H$-free graph on $n$ vertices, what is the largest number of edges that $G$ can have?" As is well known, if $\chi(H) = r ...

**2**

votes

**0**answers

238 views

### On the existence of Graph Monomorphism

A graph monomorphism is an injective graph homomorphism. Determining existence of Graph monomorphism between graph pairs is computationally hard.
Assume we talk only about classes of undirected ...

**2**

votes

**0**answers

118 views

### Bipartite independence number

Consider a balanced bipartite graph $G=(U,V,E)$, i.e., a bipartite graph with $|U|=|V|$. An independent set $I$ of $G$ is balanced if $|I \cap U| = |I \cap V|$.
The bipartite independence number of ...