# Tagged Questions

**2**

votes

**0**answers

96 views

### A surjective graph homomorphism between 4-valent graphs

Let $K$ and $L$ be $4$-valent planar graphs with Euler circuits (where the choice of the next edge in the circuit consists of the edge which does not share a face with the edge before), with $|V(K)| = ...

**2**

votes

**0**answers

92 views

### Reachability in dynamic random graphs

There has been some advice on how to ask questions. So I reask my question.I have a problem related to graph theory, random graphs or random geometric graphs in special that really confuses me. ...

**2**

votes

**0**answers

75 views

### Effect of removing a Hamiltonian cycle on the Laplacian spectrum

Notation: $\lambda_{\max}(G)$ is the largest eigenvalue of the Laplacian matrix of the graph $G$ (aka the Laplacian index of $G$).
Now suppose $G$ is a Hamiltonian graph with Hamiltonian cycle $C$.
...

**2**

votes

**0**answers

55 views

### Is the $d$-dimensional Arrangement of Trees still $NP$-hard?

The $d$-dimensional Arrangement Problem for general graphs is known to be $NP$-hard since the special case $d=1$ (OLA) already is (Garey et al, [1976]). For Trees however, the one dimensional case can ...

**2**

votes

**0**answers

118 views

### Optimization over Spectral Laplacian in cycles and trees

Is there any idea on how one can deal with an optimization problem of sum of k largest eigenvalues(min) of Laplacian matrix of a simple cycle or tree?
I would like to use semidefinite programming for ...

**2**

votes

**0**answers

472 views

### Is there a name for this graph?

I'm trying to find out whether the following graph has a name: Let $W$ be an $n$-dimensional vector space over $GF(q)$. The vertices of the graph are all the subspaces of $W$. Two subspaces $W_1$ and ...

**2**

votes

**0**answers

282 views

### Incremental minimum spanning tree

Given a connected graph $G=(V,E)$ with a weight function $w:E\to\mathbb{R}$ and a subset $E_0\subseteq E$ such that the subgraph $(V,E_0)$ is connected, I am looking for a sequence $E_0\subseteq ...

**2**

votes

**0**answers

89 views

### Shortest loop containing 0 in continuum percolation

I am interersted in continuum percolation with intensity $\lambda>0$. Formally, let $X$ be a Poisson point process in $\mathbb{R}^d$ with intensity $\lambda$ and $G$ the graph obtained by ...

**2**

votes

**0**answers

150 views

### Clique number of a $k$th power of a graph in terms of maximum degree?

Let $G$ be a graph of maximum degree $d$. Are there any known/easy bounds on the clique number of $G^k$, in terms of $d$ and $k$? I would like something at least epsilon better than the bound on the ...

**2**

votes

**0**answers

304 views

### Partitioning the vertex set of a graph with a large independent set

Let $G$ be a graph on an even number of vertices, say $2M$. Assume that the largest independent set in $G$ has at most $M$ elements. Is it true that there exists a set of $2m$ vertices (for some ...

**2**

votes

**0**answers

72 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

143 views

### Geodesics in polyhedral graphs

Let $e = \lbrace u,v\rbrace$, $e' = \lbrace v,u'\rbrace$ be edges of an undirected graph $G$ and $ee'$ be the path from $u$ through $v$ to $u'$. The following defintions make sense for every graph ...

**2**

votes

**0**answers

62 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

73 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

157 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

161 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

167 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

116 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

151 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

144 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

103 views

### Graph theory: subset-simulation. Has already been studied under different names?

Hello,
this is my first question, I hope it will be clear and correct enough.
I am looking for a way to compare graphs in order to create a partial order among them (based on some kind of subgraph ...

**2**

votes

**0**answers

400 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

313 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

93 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

71 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

78 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

247 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

184 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

232 views

### Gromov-Hausdorff convergence for locally finite spaces

Update: I've edited the question, since maybe it was a bit confusing and it's better to start with a more basic question.
I'm looking for properties of Gromov-Hausdorff convergence in the particular ...

**2**

votes

**0**answers

125 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

224 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

372 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

180 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

191 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

263 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

263 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

222 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

133 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

175 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

261 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

202 views

**1**

vote

**0**answers

34 views

### Mappings between adaptive networks and Markov processes

Are there any known mappings between adaptive networks models (i.e. graph model representations of networks where the internal vertex dynamics and connectivity topology can change subject to specific ...

**1**

vote

**0**answers

9 views

### Is it true that centrality measures in SNA are indicative for most important vertices only?

I read about the limitations of centrality measures on Wikipedia. It says that centrality measures are good only for identifying top most important nodes in a social network. Their relative values can ...

**1**

vote

**0**answers

52 views

### What's the complexity of the one sink directed subgraph isomorphism problem?

I am considering trying a new approach for the subgraph isomorphism problem in my PhD, but it just seems to work well for digraphs of one sink. By working well I mean some promise of not having to ...

**1**

vote

**0**answers

125 views

### Kripke frames as classes of partitions

Here's something I've been playing with off and on for a bit; I'm curious if anyone has seen it before.
For this question, a Kripke frame $K$ is a finite reflexive directed graph. (Reflexivity isn't ...

**1**

vote

**0**answers

86 views

### Discrete p-Laplacian

One of the definitions of the discrete (weighted) $p$-Laplacian is the following:
$$\Delta_{p,w}u(x):=\sum_y |u(y)-u(x)|^{p-2}(u(y)-u(x))w(x,y).$$
Consider the one dimensional case. Then the free ...

**1**

vote

**0**answers

99 views

### Multiple Bipartite graphs and matchings

I've been told recently that it's better i just for help regarding my 'specific' problem rather than lots of little questions around the same topic which appear somewhat unclear. I would first like to ...

**1**

vote

**0**answers

164 views

### Threshold for perfect Matchings in Bipartite graph

Consider the random bipartite graph with vertex classes of size $n$ and each edge being present independently with probability $p(n)$.
I know one way to prove the threshold of a perfect matching is ...

**1**

vote

**0**answers

58 views

### Is there an elliptic Harnack equality for directed graphs?

The elliptic Harnack inequality for undirected graphs was proven by Delmotte in the paper "Inegalite de Harnack elliptique sur les graphes" (French, ...

**1**

vote

**0**answers

42 views

### Rate of convergence of graph-theoretic quantity to fractional graph-theoretic counterpart

Let $G^n$ denote the OR product of a graph with itself $n$ times, i.e. the graph which has an edge between distinct vertices $(v_1,v_2,\ldots,v_n)$ and $(u_1,u_2,\ldots,u_n)$ if there exists some $i$ ...