# Questions tagged [graph-theory]

Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

15,938 questions
0answers
12 views

### Update an existing route with a set of pedestrian crossings

I am trying to route though a set of pedestrian crossings. I ask a route to some location service to get a default route, the problem with that route is that it does not include some waypoints (...
1answer
11 views

### Graph theory: plex and clique

How do a 2-plex relates to a 2-clique? I think that being a 2-plex means that is also a 2-clique but i don't know how to prove it. Thanks,
0answers
19 views

### Number of eulerian paths in an undirected connected graph between two given vertices?

Given a undirected connected graph G(V, E). Provide an optimal algorithm, which finds the number of eulerian paths between vertex 1 and vertex |V|. I was thinking about matrix multiplication, but I ...
0answers
10 views

### ST-CON variation: is it also in NL?

Consider the following variation on the ST-CON decision problem: given a directed graph $G$, for every two different vertices $s$ and $t$, there is a directed path between $s$ and $t$. Intuitively, it ...
0answers
21 views

1answer
30 views

### Number of ordered trees of size $n$

I'm trying to solve a problem related to counting the number of trees. Basically, I want to count trees as different only if they have different structure. So, for example, there are $5$ trees of ...
0answers
33 views

### Prove that every planar graph is the union of at most $5$ acyclic graphs.

Prove that every planar graph is the union of at most $5$ acyclic graphs. Reminder: As union of two graphs $G_1(V_1, E_1)$ and $G_2(V_2, E_2)$ we consider the graph $G(V_1\cup V_2,E_1\cup E_2)$ ...
0answers
17 views

### Path between nodes in a colored oriented tree with given weight sum

Consider an oriented tree where each node is colored either black, white, or both. In addition, each (oriented) edge has a given weight. I am trying to see whether there exists a pair $(u, v)$ of ...
0answers
16 views

### Is it okay to not provide a whitelist when using the Hill-Climbing algorithm?

So, I'm trying to use Hill-Climbing for a Bayesian learning network. For some reasons, I do not know all of the variables that I'm going to use and hence, I cannot provide a whitelist or a blacklist ...
1answer
27 views

### Every cubic 3-connected Hamiltonain graph has three Hamiltonian cycles with special property

It is known that every cubic Hamiltonian graph has at least three Hamiltonian cycles (by Tutte's theorem that every edge of a cubic graph belongs to an even number of Hamiltonian cycles) It is true ...
1answer
46 views

### Knightwise Connectedness of a Chessboard Fragment

Define the “Knightlyness” of a square on a chessboard fragment as the number of squares on that fragment that a knight could jump to in one move from the square under consideration. The “average ...
1answer
44 views

### A problem from Germany [on hold]

Every road in Sikinia(city) is one-way. Every pair of cities is connected exactly by one direct road. Show that there exists a city which can be reached from every city directly or via at most one ...
0answers
14 views

### Spanning forests of bipartite graphs and distinct row/column sums of binary matrices

Let $F_{m,n}$ be the set of spanning forests on the complete bipartite graph $K_{m,n}$. Let $$S_{m,n} = \{(r(M), c(M)), M \in B_{m,n} \}$$ where $B_{m,n}$ is the set of $m \times n$ binary matrices ...
1answer
29 views

### Hamiltonian and Eulerian graph with 2 bridges?

Is it possible to have graph which is Hamiltonian and Eulerian at once with 2 bridges in it? If yes, how can it look like? Thank you. Edited: The bridge is an edge of a graph whose deletion ...
1answer
37 views

### Bounding the number of edges in a graph satisfying a certain property

I am going through past papers because I am revising for my Graph Theory exam this week. I encountered the following question: The bipartite Ramsey number $R(s,t)$ is the minimum $n$ s.t. a ...
1answer
23 views

0answers
16 views

### Coloring of hypergraph with polynomial implication

Sorry to bother again with my misunderstandings, but I encountered yet again an issue with the topic of coloring in graphs and again I require some help to deal with this exercise: Let $\mathbb{F}$ ...
1answer
19 views

0answers
29 views

### Spectral measure of a finite graph

Let $A$ be the adjacency operator of connected, locally finite graph $G = (V,E)$ ($A$ seen as an operator on $\ell^2(V)$). Then we have the spectral representation $$A = \int_{\sigma(A)} t \mu(dt)$$ ...
0answers
21 views

### Minimal one-step distance set of vertices to all vertices

I want to find minimal set of vertices such that every vertex in this graph either in this set or connected with some vertex from this set with one edge. Is there standard name for this algorithm? It ...
1answer
23 views