# Questions tagged [graphs]

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

4,796 questions
Filter by
Sorted by
Tagged with
1 vote
30 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'...
48 views

50 views

### How to determine the largest number of disconnected arcs in a graph?

Given a directed graph $G=(V,E)$, I'm wondering if there's a way to determine the largest size of a set of edges that are disconnected pairwise. There is a similar problem for vertices (Maximum ...
30 views

### How to generate all the possible nodes inside a polygon, if the polygon is represented by its vertices

If a polygon is represented by its vertices(latitudes, longitudes), is it possible to find all the possible points or nodes(latitudes, longitudes). If so, what kind of algorithm is used. The polygon ...
14 views

### Is there a mathematical classification of formal languages for denoting graphs as a sequence of finite symbols?

I believe a general or pure definition of a “graph” in mathematics can be from algebraic topology, where a graph can be more abstractly seen as a simplicial complex, or a cell complex, or with scheme ...
82 views

### Finding a connected subset of edges with minimal sum of weights for a distributed network

Let there be $n$ processes in a general connected network with no leader such that each process has a distinct UID. Each edge has a weight , with weights being positive or negative. Assume that each ...
44 views

### Bounded clique width graphs vs parameter clique width

I am Balchandar Reddy, a research scholar. I am currently working on the parameterized complexity of a problem for the parameter clique width. The problem is known to be polynomial-time solvable on ...
70 views

### Algorithm to find intersection between collection of sets

I have two dataframes representing products two distributors sell. They look like this: df1 for distributor 1. ...
24 views

### Are there pairs of connected graphs that always fail the k-wl test for any k?

Is there a pair of connected graphs for which the k-wl test always fails (= judges isomorphic when not isomorphic) for any k? If so, please give an example. How about the following image? Are they non-...
35 views

### how to find the right path for A* algorithm (not the real time algorithm)

Hey to everyone I am trying to understand A* algorithm not the real time A* algorithm To understand this I created the following problem Node s is connected with Α and the heuristic value of Α is 4 ...
1 vote
120 views

### Find the number of all possibilities to visit all vertices once in a connected graph

Let $G$ be a connected undirected graph, e.g.: u -- v -- w \ / x I would like to determine the number of sequences in which every vertex of the graph is ...
56 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
51 views

1 vote
40 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 ...
55 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 ...
114 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
54 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 ...
60 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 ...
12 views

### Existence of a Path from Initial to Accepting Configuration in Turing Machine Runs: A Reduction-Based Proof

Is it possible to show, by reduction(Reduction in the length of the path and the running time), that for a Turing machine M and an input X, there exists a run in which M accepts X if and only if there ...
45 views

### Efficient Algorithm To Find A Path Which Covers Maximum Area Along Polygonal Perimeter For Surveillance Application

In the context of surveillance, I am working on a project where the goal is to find an algorithm that determines a path along a polygonal area, connecting a root node to a target node, while ...
114 views

### Budgeted Independent Vertex Cover

Suppose that we are given a graph $G = (V,E)$ and a number $n$. The problem is to find an independent set $I$ with $|I| = n$, such that number of vertices covered by $I$ is maximized (that is, the ...
1 vote
41 views

### Dynamic Programming: Counting *cycles* consisting of distinct numbers

I was thinking about this question and thought about it for quite a while but couldn't come up with an answer. Firstly, we fix two sets $R$ and $S$. We consider "cycles", which are tuples in ...
1 vote
39 views

### Finding maximal cliques in a graph represented as a collection of complete biparti graphs

I have a graph whose edges can be very efficiently represented as a set of complete biparti graphs (that may share nodes). Is there a name for such a representation? And secondly. I want to enumerate ...
52 views

### Partition a graph into connected subgraphs of 3 vertices each

We need to partition a graph into subgraphs of 3 vertices each, such that every subgraph has at least 2 edges. The problem is similar to the partition into triangles problem (which is NP-complete) but ...
73 views

### Constant factor approximation algorithm for Vertex Deletion version of Maximum Diameter Bounded Subgraph

I've been stuck with this problem for quite a while now, and after reading so many papers I'm unsure whether this is even possible. The problem is quite simple: Given $G = (V, E)$ an undirected graph, ...
30 views

### Directed graph where each node must contain all elements from source nodes

I'm looking for a directed graph data structure where each node is unique and contains a set of elements (at least one). Each node must contain all elements from nodes pointing to it so it possible to ...
175 views

### Partitioning a graph into connected pairs and triplets

We need to partition an undirected graph into connected subgraphs of size between $2$ and $k$, where $k$ is an integer. When $k=2$, the problem is equivalent to the perfect matching problem which is ...
### Color a a general graph with maximal degree $\Delta$ using $2^{O(\Delta)}$ colors within $\log^{*}n$ rounds
Consider the following algorithm $A$ to 6-color an rooted tree within $\log^{*}n$ rounds in a distributed system: 1: Assume that initially the nodes have IDs of size $\log(n)$ bits 2: The root is ...
Given a graph $G=(V,E)$ and any edge $(u,v) \in E$, let us denote by $G_{(u,v)}=(V,E\setminus\{(u,v)\})$ obtained from $G$ by removing this edge. I am interested in the difference between the average ...