**2**

votes

**0**answers

95 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

114 views

### Partitioning a cubic graph into two induced cycles of equal order

I am aware that deciding the existence of a partition of the vertices of a connected graph $G(V, E)$ into two induced cycles is $NP$-complete(Theorem 2). Induced cycle is a cycle without any chord ...

**2**

votes

**0**answers

51 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

81 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

91 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

137 views

### If two graphs have same Laplacian spectrums, are they the similar graphs?

If graph A and graph B have exactly the same Laplacian spectrums, can I just say they are same graphs? (only with scaling edge weights and node index reordering) I don't know if there is any explicit ...

**2**

votes

**0**answers

130 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

205 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

94 views

### Groups of automorphisms of weighted graphs

Let $\Gamma=(V,E,\omega)$ be an (edge-)weighted graph without loops and multiple edges. Here $V$ is the set of vertices, $E$ is the set of edges and $\omega:E \to \mathbb{N}$. A permutation $\varphi$ ...

**2**

votes

**0**answers

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

**2**

votes

**0**answers

89 views

### Groups acting on non-locally-finite trees with independence and specified local actions

Suppose I have a biregular tree $T_{m, n}$ (not necessarily locally finite), with distinct cardinal numbers $m, n$, so Aut$(T_{m, n})$ acts on $T_{m, n}$ without inversion. Let $V_m$ be those vertices ...

**2**

votes

**0**answers

281 views

### Why the number of the vertices is even?

Let $G$ be a graph with $n$ vertices and $V$ the vertex set. Suppose that for each non-empty subset $W$ of $V$ there exists an element $\omega \in V$ ( maybe in $W$ or not) such that the degree of ...

**2**

votes

**0**answers

79 views

### Usefulness of polynomial ideals for graphs

Given a graph $G=(V,E)$ on $n$ vertices, one can associate to it the polynomial $f \in k[x_1,\dots,x_n]$ given by $f = \prod_{\{i,j\}\in E}(x_i - x_j)$. Then one can map various graph properties into ...

**2**

votes

**0**answers

86 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

88 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

53 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

111 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

469 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

206 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

86 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

121 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

279 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

69 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

127 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

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

69 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

131 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

155 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

173 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

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

101 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

144 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

128 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

101 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

385 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

92 views

### special 1-factorization of regular bipartite graphs

Let $n= 2k+1, |X|=|Y|= n$ and $G= (X, Y, E)$ be a $(k+1)$-regular bipartite graph.
Let $M$ be a perfect matching of $G$ having the property that every cycle of size 4
$C_4$ intersects $M$ in at most ...

**2**

votes

**0**answers

244 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

88 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

73 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

233 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

178 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

174 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

178 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

338 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

174 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

188 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

237 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

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