3
votes
1answer
104 views

A problem related to routing in a graph

I have come across a new problem - I want to know whether this problem is similar to some existing problem or not. The new problem is this. There is a tourist who has a having the following ...
1
vote
1answer
110 views

How many edges can you put in a graph such that every edge belongs to a minimal $k$-cycle?

I am trying to solve: Given $n, k$, find maximum $m$ such that there exists a graph on $n$ nodes, $m$ edges such that every edge is part of a minimal $k$-cycle. I only care about the asymptotic ...
4
votes
0answers
158 views

Rough structure of the double coset space/Graph bijections up to automorphisms

I am dealing with bijective maps $\pi:\Gamma_1\to \Gamma_2$ between two graphs with the same number of vertices $N=O(10)$. The graphs have a significant automorphism group (these are disconnected ...
2
votes
0answers
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 ...
1
vote
0answers
92 views

Schönhage's SMM with only one instruction

It is possible to implement $\lambda$-calculus in Schönhage's storage modification machine using an infinite set of nodes and one single program consisted exclusively of (about hundred) instructions ...
1
vote
1answer
250 views

Distance between vertices in a vertex transitive graphs. [closed]

Can anybody help me in finding out the distances between vertices in a vertex transitive graphs. Is there any specific formula to calculate distance between vertices in this graph. Thanks for your ...
1
vote
0answers
107 views

Turing-complete primitive interaction systems

Let us call primitive an interaction system with the signature $\Sigma = \{(\rho, 0), (\xi, n)\}, \quad n \geq 2;$ and the only rule being of the form $\rho \bowtie \xi[\rho, \xi(a_1, \dots , a_n), ...
3
votes
2answers
533 views

Turing-complete primitive blind automata

Let $N$ be the set of natural numbers, $S$ be the set of finite binary sequences, and $Q = [N \rightarrow N] \times [N \rightarrow N],$ where $[N \rightarrow N]$ is the set of all computable ...
2
votes
0answers
151 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 ...
0
votes
1answer
190 views

hypergraph cartesian join operation (over same vertex set)

consider two hypergraphs $H_1 = (V, \mathscr{E}_1), H_2 = (V, \mathscr{E}_2)$ over the same vertex set $V$. am interested in what could be called a "cartesian join" operation building a new hypergraph ...
0
votes
1answer
249 views

Counterexamples for this algorithm for recognizing lexicographic product of graphs?

Found a possible reduction from recognizing lexicographic product of graphs to 2SAT (since 2SAT is polynomial, the algorithm is polynomial). Can't prove completeness of the algorithm and since it is ...
0
votes
0answers
85 views

Exact Length Problem in a directed graph

I have a directed graph that consist of N^2 vertices (like a square) and each vertex is connected to at most 1 node (not bidirectional) and every connections have length 1. There are no cycles in the ...
0
votes
1answer
278 views

Is there any relationship between a tree(graph theory) and semi-metric?

suppose we have a tree(undirected) with $n$ vertices.The edges are weighted(distances). Is it possible to impose a semi-metric structure on the graph using these distances and adjacency matrix?
2
votes
1answer
325 views

Algorithm for satisfiability of inequalities.

I am looking for an algorithm for checking the satisfiability (with natural values) of a set of inequalities made of variables and natural numbers, for example: $u < v, u \leq z, 3 \leq v$. In ...
0
votes
0answers
343 views

Examples of Hamiltonian Cycle Problem / Traveling Salesman Problem in general grid graph form

I understand that there is a polynomial algorithm to solve TSPs that are in solid grid graph form (grid graphs without holes). I am particularly interested in the non-solid grid graph form of the ...
0
votes
1answer
244 views

Universality of blind graph rewriting

Let us consider $S(M) = \{(f_0, f_1) | f_0, f_1: M \rightarrow M\}$, where $M$ is a finite set. Each element of $S(M)$ is equivalent to a finite directed graph with the set of nodes $M$, which has ...
3
votes
1answer
630 views

Algebraic structure generated by primitive graph operations

Let $M$ be a finite set, and $S(M) = \{(f_0, f_1) | f_0, f_1: M → M\}$. Each element of $S(M)$ can be considered as a finite directed graph with the set of nodes $M$, which has exactly two arrows ...
2
votes
2answers
537 views

Graph Theory Conjectures [closed]

What are some important conjectures in graph theory that have been checked by computer up to order 11?
2
votes
1answer
466 views

Composite finite-state machines

A finite state machine, FSM, is a box with C input/output channels, and S states, and a fixed map $f : S\times C \to S\times C\cup {0}$. If a state $(c_i,s_j)$ is mapped to the 0 element it means it ...
3
votes
1answer
627 views

Decomposition of a complete graph into maximal matching subgraphs

Is there a general way to decompose a complete graph $K_n$ into an union of maximal matching subgraphs such that no two subgraphs share an edge? For example, consider $K_4$ with vertices ...
1
vote
1answer
188 views

Recoving an unknown tree graph with knowledge of root node to leaf node distances

Imagine I have an unknown (undirected) tree graph, $G$, with some unknown number of nodes $||V||$. However, I know the edge-length between nodes is of fixed size, $L_{edge} = 1$, and I have access to ...
0
votes
1answer
461 views

Transition Graph per alphabet?

How do you determine how many different Transition Graphs are over a particular alphabet? For example How many TG's are over the alphabet {x, y}. I am taking a class with a similar question from ...
2
votes
1answer
622 views

Official name and complexity of k-way balanced set partitioning? What is the best heuristic?

As a lot of people know, graph partitioning is NP-Complete. In graph partitioning, you try to create k balanced (within some pre-specified epsilon) disjoint subsets of (possibly weighted) vertices ...
3
votes
5answers
572 views

Is the following two-dimensional graph likely to be globally rigid?

Consider the two-dimensional non-planar graph $G$, with known topology and edge lengths $(r_1, r_2, ... r_N) \in R$, but unknown vertex coordinates. We further specify that: All vertices within a ...
0
votes
0answers
82 views

Does there exist an algorithm for computing reachability in dynamic directed forests with fast update?

I'm interested in an algorithm which is able to compute reachability between any two nodes in polylog update (add or remove a valid edge) and query. I know that such an algorithm does exist for all ...
5
votes
1answer
378 views

What is the pathwidth of the 3D-grid (mesh or lattice) with sidelength k?

This question is now also on http://cstheory.stackexchange.com/questions/4081/what-is-the-pathwidth-of-the-3d-grid-mesh-or-lattice-with-sidelength-k, where a discussion started, and one reference ...
4
votes
2answers
573 views

Coloring edges on a graph s.t. the set of edges for any two vertices have no more than 'k' colors in common

Please imagine the case where one has a planar graph, $G$, with a set of $|V|$ vertices, $(v_1, ..., v_{|V|}) \in V$, and $|E|$ edges, $(e_1, ..., e_{|E|}) \in E$. Now, provided a total of $N$ ...
2
votes
3answers
317 views

Can we uniquely define a graph to have the topology of a polytope via proper edge length selection?

I'll ask you to consider a situation wherein one has a series of edges for a graph, $(e_1, e_2, ..., e_N) \in E$, each with a specifiable length $(l_1, l_2, ..., l_N) \in L$, and the goal is to insure ...
5
votes
1answer
331 views

Drawing graphs on circles

Please consider the following problem: Given: a simple graph (without self-loops and without multiple edges) $G$ on $n$ vertices. Task: place equidistantly the vertices of $G$ on a circle of unit ...
27
votes
1answer
3k views

An edge partitioning problem on cubic graphs

Hello everyone, I already asked this question on the TCS Stack Exchange, but it has not been resolved yet. Maybe readers of this forum will have other ideas or information, although I suspect that ...
4
votes
3answers
742 views

Software for Tree-Decompositions

Does anybody know about software that exactly calculates the tree-width of a given graph and outputs a tree-decomposition? I am only interested in tree-decompositions of reasonbly small graphs, but ...
5
votes
1answer
537 views

Counting Eulerian Orientation in a 4-regular undirected graph

We would like to know how hard it is to count Eulerian orientation in an undirected 4-regular graph. For a given edge orientation to be Eulerian, we mean that every vertex has 2 in-edges and 2 ...
22
votes
2answers
2k views

Counting subgraphs of bipartite graphs

I'm not a graph theorist or computational complexity specialist, so my apologies if this question is stupid or poorly posed! Given a bipartite graph $G$ of $n$ vertices, how many induced subgraphs of ...
4
votes
6answers
624 views

Reconstructing an ordering of a multiset from its consecutive submultisets

We have a multiset $S$ of size $t$ with $r$ distinct elements, where $t$ is much larger than $r$. We want to reconstruct an ordering $s_1, s_2, ... s_t$ of the elements of $S$ given the values of $t$ ...