**2**

votes

**0**answers

64 views

### Minimum relay nodes in graph

I have the following problem. I would like to know if this reduces to some standard problem in Graph theory. Any suggestions are much appreciated.
I have a multi-cast network with 1 source (denoted ...

**2**

votes

**0**answers

58 views

### Presentation of tree decompositions (and related concepts) in terms of continuous maps?

A tree decomposition of a graph $G$ is commonly defined in terms of a tree $T$ with the following structure:
Each vertex $t \in V(T)$ is associated to a set $X_t \subseteq V(G)$;
The union ...

**2**

votes

**0**answers

67 views

### Maximizing the minimum outdegree of digraph without $m$ cycle

Let $G$ be a simple digraph on $n$ vertices without a directed cycle of length $m$
(it may have directed cycles of length less than $m$. The cycles need not be simple).
How large the minimum ...

**2**

votes

**0**answers

122 views

### Structure of almost all bipartite graphs

I am studying some properties related to bipartite graphs and it would be useful for me to know if there is anything known about the structure of almost all bipartite graphs. For example, is it true ...

**2**

votes

**0**answers

149 views

### A primal-dual (double) circle packing (coin graph) question

I know that any 3-connected simple planar graph with a designated outside face (outer face) has a primal-dual (double) circle packing (Brightwell-Scheinerman Theorem).
Q1- But I am not sure whether ...

**2**

votes

**0**answers

162 views

### A natural problem on “cartesian union” of set families (hypergraphs). Does anybody know NP-complete problems related to the notion of cartesian product?

I'm curious whether the problem below is NP-complete.
I provide two simple definitions and one example at first.
Definition 1.
Let $\langle {\cal{S}}_i\rangle\substack{i\in I}$ and $\langle ...

**2**

votes

**0**answers

161 views

### What is the genus of a Johnson graph?

The Johnson graph $J(n, k)$ has a known genus when $k=1$, in which case it is the complete graph $K_n$. What can be said about the genus of $J(n, 2)$, or more generally $J(n, k)\ ?$

**2**

votes

**0**answers

93 views

### Perfect P6-free graphs with further properties

Let $G$ be a graph without any hole or antihole of odd length at least 5 (i.e. $G$ is a Berge graph and so by the Strong Perfect Graph Theorem, $G$ is perfect).
Assume further that $G$ has no ...

**2**

votes

**0**answers

137 views

### Polyhedral embeddings of large face-width where all faces have the same length

Where can I find examples of polyhedral embeddings of simple graph with large face-width, such that all the faces have the same length?
By polyhedral embedding I mean an embedding of the graph on a ...

**2**

votes

**0**answers

114 views

### Additional Constraint Baum Welch for HMMs

I'm trying to derive a special form of the Baum Welch algorithm where there is an additional constraint that the sum of emission probabilities over all states sums to one for each output symbol. ...

**2**

votes

**0**answers

378 views

### Matching in regular bipartite graphs

Let $G=(X,Y,E)$ be an $r$-regular bipartite graph where $|X|=|Y|$ . Let $\phi$ an automorphism of $G$ with $\phi(X) = Y$ and $\phi \circ \phi = id$, and let $\psi$ be the mapping induced by $\phi$ on ...

**2**

votes

**0**answers

211 views

### Matrix Operations Preserving Hurwitz Stability

I begin with terminology I use in the question. A real square matrix $A$ is
negative-stable if for every eigenvalue $\lambda$ of $A$, ${\mathrm{Re}}(\lambda) < 0$;
$\ast$-negative-stable ...

**2**

votes

**0**answers

86 views

### Graphs, non-Hausdorfness and Wallman compactifications of non-regular spaces

Given a non-Hausdorff space $X$, one can form a graph $G_X$: vertices the points of $X$, edges indicating point pairs not separated by open sets. Up to graph-theoretically (but not topologically) ...

**2**

votes

**0**answers

69 views

### Subgraphs of bounded tree-width and preserving edges of original graph

Given a graph $G$, I would like to determine a method for randomly generating subgraphs $G'$ with the following properties:
Each edge of $G$ has at least some probability $p$ of going into $G'$
The ...

**2**

votes

**0**answers

72 views

### A non-distinct system of representative edges.

I have the following problem:
Let $ \mathcal{G} = (G_{i})\_{i} $ be a collection of graphs. I would like to find a "system of representative edges" $ f : \mathcal{G} \rightarrow \bigcup_{i} E(G_{i}) ...

**2**

votes

**0**answers

228 views

### Slightly improving bounds on two-color Ramsey numbers by globally pruning edges and counting connected vertices in instances of two-colored complete graphs

The two-color Ramsey number, $R(m, n)$, is the minimum number of vertices, $||V||$, in a complete graph necessary for there to exist a clique of order $m$ or an independent set of order $n$. In terms ...

**2**

votes

**0**answers

174 views

### Maximum number of 4-colorings of planar graphs (precise version)

This is a redo of my earlier question.
I'm trying again with more precision. I ignored one of the dicta in the "how to ask" page.
For a fixed $n$, what is known (references preferred) about the ...

**2**

votes

**0**answers

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

**2**

votes

**0**answers

123 views

### $f$-vector of graph connectivity

For a connected graph $G$, let $N_i$ be the number of connected subgraphs of size $i$. The vector $\langle N_0, N_1, \dots \rangle$ is also known as the $f$-vector for the graph.
As a superset of a ...

**2**

votes

**0**answers

166 views

### Complexity of bipartite graphs and their matchings.

My question concerns a hypothetical family of bipartite graphs, $G_i$.
Each graph $G_i$ has $2^i$ red nodes and $2^i$ blue nodes - so nodes get labelled
by their color and a binary string of ...

**2**

votes

**0**answers

328 views

### Hamiltonian paths in subgraphs of rectangular lattice graphs

Is following decision problem NP-hard / NP-complete:
Having vertex-induced subgraph of rectangular lattice graph determine if any Hamiltonian path exists
Having vertex-induced subgraph of ...

**2**

votes

**0**answers

164 views

### Counting the independent sets of a comparability graph with maximum degree 3. Is it #P−complete ?

This question was first asked here:
cstheory.stackexchange...
Here we want to count the number of independent sets of a comparability graph. For Δ(G)=2 , i.e. the maximum degree of a vertex in G is ...

**2**

votes

**0**answers

271 views

### Bipartite Obstructions to genus $g+1$ Bipartite graph from becoming genus $g$.

Say $B_{n,n}$ is a bipartite graph on $2n$ vertices with each color assigned to $n$ vertices.
Say I know $g \le genus(B_{n,n}) \le g+1$: What obstructions can $B_{n,n}$ have from becoming a genus ...

**2**

votes

**0**answers

184 views

### Complexity of finding disjoint 2-factors with equal cardinality in cubic graphs?

Finding a connected 2-factor that contains every node in cubic graphs is $NP$-complete since it is equivalent to the Hamiltonian cycle problem. I'm interested in the complexity of finding vertex ...

**2**

votes

**0**answers

228 views

### When is polytope compatible with network flow?

A linear program is the problem of optimizing an linear objective function within some polytope $A$ over $\mathbf R^n$. My question is motivated by the question of when a linear programming problem ...

**2**

votes

**0**answers

249 views

### Connectivity in random points on a grid using a rope of fixed length.

This problem is a by product of another problem. I would like to restate this problem as a sort of a puzzle.
Suppose we have a $l \times b$ grid. We select $k$ points on the grid randomly and ...

**2**

votes

**0**answers

219 views

### Group of local complementation as a coxeter group

Can the group generated by local complementations, ${lc_i|i=1,\cdots,n}$ on simple graphs on $n$ vertices, be categorized as a coxeter group? After all these obey:
\begin{equation}
\langle lc_i| ...

**2**

votes

**0**answers

129 views

### finding set of tree decompositions to cover all pairs of vertices

I first asked this on cstheory.SE but got no reply.
Let $P(X_i=x)$ represent probability that randomly chosen proper $q$-coloring of an $L\times L$ square grid contains color $x$ at position $i$. How ...

**2**

votes

**0**answers

156 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: ...

**2**

votes

**0**answers

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

**2**

votes

**0**answers

197 views

**1**

vote

**0**answers

26 views

### Euclidean embedding of a graph based on 1-ring neighborhood distances only

Consider a graph $(V,E)$, $\vert V \vert = n$ and weights $\{l_{ij}\}$, where $l_{ij}>0$ iff there is an edge connecting vertices $v_i$ and $v_j$. Distances beyond the 1-ring neighborhood are not ...

**1**

vote

**0**answers

57 views

### Recovering Spherical Harmonics from Discrete Samples

Consider a collection of $N$ points on the 2-sphere chosen uniformly at random. Let's say that there's an edge between two such vertices if their geodesic distance is less than $r_N$. The resulting ...

**1**

vote

**0**answers

55 views

### Disconnecting a three regular graph

Setting, a random three regular graph. If I start removing edges, what's the probability that I disconnect it? What I know is that if I disconnect a graph I get a subgraph, and that the expected ...

**1**

vote

**0**answers

100 views

### Knight's metric: ellipse and parabola

Knight's metric is a metric on $\mathbb{Z}^2$ as the minimum number of moves a chess knight would take to travel from $x$ to $y\in\mathbb{Z}^2$. What does a parabola (or an ellipse) became with this ...

**1**

vote

**0**answers

49 views

### interpretation of generalized eigenvalue/vectors in spectral graph theory

Let us say I have a symmetric graph adjacency matrix A, a degree matrix D, a laplacian L (D-A). I have a generalized eigenvalue equation $Av=\lambda Lv$. Does the eigenvalue/vectors produced in this ...

**1**

vote

**0**answers

82 views

### Motivations Needed: Paul Erdős Maximal Triangle-free Graphs

Among the collections of the open problems of Paul Erdős on the website of
Professor Fan Chung, there is one called "number of triangle-free graphs".
...

**1**

vote

**0**answers

47 views

### Can we make the weaker TPC tighter when we do the packing steiner trees?

The famous tree packing conjecture (TPC) posed by Gyarfas (see [1]) states:
$\textbf{Conjecture 1}$. Any set of $n − 1$ trees $T_n, T_{n−1}, . . . , T_2$ such that $T_i$ has $i$ vertices pack into ...

**1**

vote

**0**answers

28 views

### Harmonic Bergman spaces on graphs

Harmonic Bergman spaces on Euclidean domains are a set of harmonic functions on a domain that are from $L^{p}$ of that domain. I tried to find something on harmonic Bergman spaces on graphs because we ...

**1**

vote

**0**answers

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

**1**

vote

**0**answers

46 views

### Perfect Matchings in Biclique Decompositions of Multigraphs

Suppose you have the $K_{2n}$ covered by a multigraph consisting of $2n-1$ bicliques, each consisting of a partition of the vertex set into two sets of equal size.
Here is a picture of $K_{6}$ with 5 ...

**1**

vote

**0**answers

80 views

### On 'Very Movable' Geometric Configurations (Configurations with a large degree of freedom)

Let $C$ be an $(n_r, b_k)$ combinatorial configuration that admits a geometric realization in the plane. I'm interested in the maximum number of points/lines $M$ of $C$ we can place in general ...

**1**

vote

**0**answers

125 views

### A connection between nonplanar complete graphs and the alternating group?

I didn't get any response on MSE so I though I'd give this a try here (my question on MSE).
I went to an undergrad's senior honors thesis presentation a while ago. She was discussing crossing numbers ...

**1**

vote

**0**answers

135 views

### Can assigment of Cayley graphs be functorial?

Let $G$ and $G'$ be finitely generated groups and $f:G\to G'$ a homomorphism. First question: for a given $f:G\to G'$ it possible to select generating sets $S\in G, S'\in G'$ so that their would be a ...

**1**

vote

**0**answers

41 views

### complexity of in-dominating set

Is the decision problem In-Dominating Set NP-complete for digraphs of regular out-degree (greater than (n-2)/4, in particular)? I'm mainly looking for the reference.
Thanks for any answer!

**1**

vote

**0**answers

66 views

### How close to platonic can a non-platonic planar graph be?

Direct question:
Is it possible to construct a finite, planar, $k$-regular graph in which all the faces except one have the same degree (are bounded by a cycle with the same number of edges), and the ...

**1**

vote

**0**answers

64 views

### maximum weight k-edge problem

Given positive integer $k$ and an undirected graph $(V,E)$, with nonnegative (non-uniform) weights on the nodes. Find $k$ edges whose spanning nodes have the maximum weight.
Is this in P or NP? I ...

**1**

vote

**0**answers

100 views

### Is the automorphism group of a homogeneous (locally finite) tree unimodular?

I have seen somewhere (that I don't remember now) that the (full) automorphism group of a k-regular tree is unimodular. I assume a k-regular tree is the same thing as the homogeneous tree of degree k ...

**1**

vote

**0**answers

96 views

### A traveling time problem

Given any undirected, connected and simple graph $G(V,E)$,each node of which is considered as a city. We call $j$ a neighbor of $i$ if $(i,j)\in E$. $N_i$ is the set of neighbors of $i$. $|V|=N$
...

**1**

vote

**0**answers

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