# Questions tagged [graphs]

Questions about graphs, discrete structures of nodes which are connected by edges, including trees and graphs with weighted edges.

4,852 questions
Filter by
Sorted by
Tagged with
42 views

### Algorithm for leader election in synchronous ring with a known network size $n$ with phases of length $\frac{n}{m}$

Consider the following leader election algorithm election of a synchronous ring with a known network size $n$ (simultaneous wakeup and uni-directional communication): The leader is the node with the ...
93 views

### Path planning on 2D grid graph to maximize the neighboring grid points of a path: Can we do better than brute DFS?

On a finite 4-connected grid graph, given the source point and destination, it is allowed to consecutively move in one of the four orientions (up, down, left or right) to form a path. We get 1 bonus ...
51 views

### Find directed spanning tree of unweighted directed graph in $O(|V| + |E|)$

A directed tree (also called an arborescence) of $G$ is a directed subgraph of $G$ in which there exists a vertex $v$ such that there is a unique path from $v$ to every other vertex in the graph. ...
125 views

### Fast $k$-clique checking algorithm?

I have a problem where part of it requires answering the question: does graph $G=(V,E)$ contain a clique of size at least $k$? Obviously, answering this question is a NP-Complete problem. I am no ...
43 views

### Has Triangle Finding ever been faster than Matrix Multiplication?

The Triangle Finding problem (TF) in Graph Theory was shown by Itai and Rodeh in 1977  to be solvable as fast$^1$ as Boolean Matrix Multiplication (BMM, Matrix Multiplication over $\{0, 1\}$ with ...
52 views

### Is the set of all duals same as the set of all planar graphs?

Let $P$ be the space of all possible planar graphs. Fact: A planar graph may have multiple duals based on its embedding. Let $D_p$ be the set of all possible duals of a planar graph $p\in P$ Let $S$ ...
1 vote
66 views

### Enumerate faces in any one embedding of a planar graph

Given: A planar undirected connected graph $G$ in which degree of every vertex is $2$ or more. Fact: A planar graph can have multiple planar embeddings. Question: Give an efficient algorithm to find ...
61 views

### Checking if all nodes are reachable in a oriented graph from all other nodes

I'm having a lot of troubles understanding a preparation exercise about oriented graphs: Consider the following game played on a directed graph G = (V, E) with n nodes and m edges. A pawn is ...
1 vote
45 views

### Showing that nearly regular graphs have a specific $(2,O(\log n))$ ruling set with high probability

An $(\alpha,\beta)$-ruling set is a set $S$ such that any two nodes in $S$ are at distance at least $\alpha$ from each other, and, for any node $v \notin S$, there exists a node $u \in S$ such that ...
1 vote
46 views

### How to express that a graph has Independent set of size at least $n/2$ in $\exists SO$

I am looking to provide a formula saying "A graph with $n$ vertices has an independent set $X$ of size at least $n/2$" in existentional second order logic. (This is exercise 1.2. from Libkin'...
52 views

1 vote
81 views

58 views

### Is there a decomposition/structural theorem for 3-edge-connected graphs?

A graph is 2-edge-connected if and only if it has a closed ear decomposition. I am looking for such a theorem for the 3-edge-connected case. Unfortunately, I have not been able to find one. Is there ...
1 vote
101 views

1 vote
41 views

### Show that the graph on 99 vertices cannot be divided into two classes

In a graph with 99 vertices, two vertices have a degree of 3, and the degree of the other vertices is 4. Show that the graph contains an odd cycle. I figured I have to show that the graph cannot be ...
59 views

### Can negative edge weights in a graph be positive numbers?

I'm a little confused by the concept of a "negative" edge weight. All of the examples I have seen represent negative edge weights as negative numbers. Is it possible for an edge weight to ...
131 views

### Let the vertices of the graph G be the numbers 1, 2, ..., 100, a. Determine χ(G), the chromatic number of the graph G

Let the vertices of the graph G be the numbers 1, 2, ..., 100, and two (different) vertices be adjacent if and only if at least one of 2, 3, or 5 is a common divisor of the respective numbers. ...
1 vote
61 views

I have read the definition of treewidth/tree-decomposition both in Wikipedia and in here: https://medium.com/@karlrombauts/treewidth-how-all-graphs-are-trees-in-disguise-ec699b69e2fb I'm finding ...
65 views

### Creative solving of searching redundant connection in graph

I am trying to solve problem in leetcode: https://leetcode.com/problems/redundant-connection/description/ *finding redundant connection in undirected graph And now I am writing a solution, inpired by ...