# Questions tagged [graph-theory]

Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.

1,558 questions
Filter by
Sorted by
Tagged with
1 vote
101 views

### Is Gnag's proof of Graceful Tree Conjecture correct?

Gallian's dynamic survey on graph labeling mentions Gnang's preprints which claim to resolve the graceful tree conjecture. The latest version of this preprint dates 2023 August. Another related ...
• 1,759
18 views

### On the Relationship Between Graph Isomorphism and Equivalence in ETL Workflow Dependency Graphs

Let $G = (V, E)$ and $G' = (V', E')$ be two DAGs representing dependency graphs of ETL workflows. Each node $v \in V$ (or $v' \in V'$) represents a task, which is a tuple $t_v = (q_v, d_v, s_v)$, ...
• 1
96 views

### Deciding whether there are directed paths between two vertices of all possible lengths

I recently read a paper The presence of a zero in an integer linear recurrent sequence is NP-hard to decide by Blondel and Portier, in which they prove the statement The problem of determining for a ...
• 109
33 views

### Enhancing a bipartite perfect matching solution with 1-to-2 matchings

We're doing hobby events where people list their items followed by a wishlist of what they would like to receive in exchange for each one of their items, then the current algorithm finds the biggest ...
79 views

### Channel Capacity & Dependency Graph

A single-input-single-output communication channel is to be used repetitively. Denote by $X_i \in \mathcal X$ the input at time $i$ and by $Y_i \in \mathcal Y$ the output at time $i$. Assume the ...
• 101
121 views

### Is the protocol perfect zero knowledge?

Consider such protocol for $GI$ (Graph-isomorphism problem). $P$ randomly chooses permutations $\sigma_1, \sigma_2, ..., \sigma_k$ and sends $H_1 = \sigma_1(G_0), ..., H_k = \sigma_n(G_0)\ (k > 1)$;...
1 vote
84 views

### Development details of the Hungarian algorithm for Maximum Perfect Bipartite Matching

There are two realization forms of Hungarian algorithm. One is the original dynamic matrix, and the other is via equality subgraph. I just checked the original paper of Hungarian method by Kuhn, which ...
70 views

### What work on min max connectivity problems has there been?

For instance has min max spanning/steiner/prize-collecting tree been studied. i.e. each edge $e$ has costs $c_{v,e}$ of each resource $i$. And we wish to find a spanning tree minimizing the maximum ...
• 228
65 views

### Has multiobjective prize collecting steiner tree or TSP been studied?

Suppose we have a graph $G$ a root $r$ and each node $v$ has some amount of $c_{v,i}$ of each resource $i$. I connect a set of nodes to the root that maximizes the minimum amount of any resource using ...
• 228
1 vote
95 views

### Induced subgraphs with interface

I am interested in hypergraphs with interfaces, I'll call them simply "graphs" in the following. Formally, a graph of sort $k$ is a tuple $(V,E,i)$ with $E\subseteq V^+$ is the set of edges, ...
• 8,903
47 views

### On a modular inverse graph construction

Given a balanced bipartite graph $G_1$ on $2n$ vertices on the condition $PM(G_1)\equiv1\bmod2$, an integer $i$ of size $\Omega(n\log n)$, can we find a balanced bipartite graph $G_2$ on $poly(n)$ ...
• 13k
1 vote
69 views

• 103
69 views

### Is every 4-claw-free graph a bounded degree graph?

I am looking of some graph properties of 4-claw free graph, where neighborhood of every vertex has independent set of size at most 3. As per my observations, this type of independent set size ...
189 views

### property of minimal triangulations

A graph is chordal if every cycle on four or more vertices contains a chord i.e. an edge between non-adjacent vertices of the cycle. A triangulation (or chordalization) of a graph $G=(V,E)$ is the ...
137 views

### Error in TAOCP 4a on the bipartite graph constructed from a hypergraph

The first sentence on page 33 of Donald Knuth's The Art of Computer Programming (TAOCP) Vol. 4a reads: Furthermore, a hypergraph is equivalent to a bipartite graph with vertex set $V \cup E$ and ...
1 vote
126 views

### Upper bound on the number of maximal paths in rooted intransitive DAGs

Let $D(V, A)$ be a DAG. Definition 0: We name a path between two nodes $i$ and $j$ as an $i$-$j$-path. Definition 1: Let $p$ be a path, we call $|p|$ the path length, representing the number of arcs ...
51 views

• 158
18 views

### Any value in a formula that calculates (not look up) the 'order' of a 'Independent Edge Set' OR a 'I.E.S.' given an 'order' on complete graphs?

Any value or interest in a formula that calculates (not look up) the 'integer order' of a given 'Independent Edge Set' OR given an 'Independent Set' calculates the 'integer order' on Complete Graphs? ...
• 1
78 views

### Name for a cyclic path in a graph that visits every vertex while minimizing the maximum number of times a given vertex is revisited?

Me and my colleague are interested in whether anyone has looked into a generalization of Hamiltonian cycles where vertices can be revisited, but we want to minimize the maximum number of times a given ...
• 439
90 views

Let $\Sigma$ be the set $\{ 0, 1 \}$, then the set of all finite binary strings of length $n$ is written as $\Sigma^{\star}_{n}$. Question: Which further ways of representing binary strings of length $... 1 vote 3 answers 125 views ### Stable/Robust Traveling Salesman Approximation Methods I was wondering if there are TSP approximations that are "stable". More specifically, consider the set$G = x_1, ..., x_n$and the set$G^* = G \cup x_{n+1}$, where$x_i$are points in$R^d$.... • 11 0 votes 1 answer 84 views ### A variation of the longest path problem What about finding a path of maximum length in a given graph which may contain cycles, with the constraint that a vertex (or an edge) can be visited at most X (say 2 or 3) times ? EDIT: X would be ... -1 votes 2 answers 198 views ### Bottom up TSP solution? I'm not sure if this is something new or if I'm just not getting previous efforts. TSP can be thought of as a list of weighted links and nodes. If one takes the Nearest Neighbor (NN) of every node and ... 0 votes 0 answers 68 views ### How to reduce a code down to its configuration I have built a system where from atomic information of a UI code I could generate a framework specific code. Here is the concept https://github.com/imvetri/ui-editor. For example, the user of this ... • 99 1 vote 1 answer 121 views ### Tractability of computing generalized hypertreewidth on bounded arity hypergraphs Generalized hypertreewidth is a generalization of treewidth to hypergraphs. Unlike treewidth, it is not tractable, for a fixed width$k \in \mathbb{N}$, given a hypergraph$H$, to determine if$H$has ... • 9,547 1 vote 0 answers 92 views ### Generalization of the Hamiltonian path problem on Grid Graphs Fix a cost to each of these actions: move up, move down, move left, move right. I.e. fix some function$f: \{\text{move up, move down, move left, move right}\} \to \mathbb N$. Define the following ... • 31 0 votes 0 answers 85 views ### 5-color graph and minor We have a 5-color graph G without 5-clique. The question is: is there a minor H of G that is a 5-clique? Here the minor definition. With "5-color graph G" I mean$\chi (G)=5$. 1 vote 1 answer 143 views ### Efficient Algorithm for Partitioning a Directed Acyclic Graph into Short Paths I am working on a problem involving partitioning a directed acyclic graph into distinct multiple paths, each with a maximum length constraint. The goal is to minimize the number of paths (this should ... 1 vote 0 answers 34 views ### Application LCL definition to vertex coloration I'm reading the article "What can be computed locally?" by Naor & Stockmeyer and I struggle to understand the definition of an LCL they gave. Here is an extract: (page 2) An Locally ... • 111 1 vote 1 answer 59 views ### What is known about the complexity of Network Diversion? In the Network Diversion problem, we are given an undirected graph$G$on$n$vertices, with specified nodes$s$and$t$and specified edge$e$, and a positive integer$k$, and are tasked with ... • 686 4 votes 1 answer 91 views ### Independent set queries with preprocessing Suppose we have a sparse undirected graph$G = (V, E)$with$|E| = O(|V|)$, and we want to process it and then answer queries of the following type: given a set$A$, is it an independent set in the ... 0 votes 1 answer 80 views ### What's the exact complexity of a DFS if we revisit nodes? By "revisit nodes," I mean if we didn't maintain a set of nodes we have visited. So the sum I'm examining is just the number of paths from a root to a node, across all roots and nodes. We'll ... 3 votes 1 answer 204 views ### What is the treewidth of the 3D-grid (mesh or lattice) with sidelength n? Here, by 3D-grid of sidelength$n$I mean the graph$G=(V,E)$with$V= \{1,\ldots,n\}^3$and$E=\{( (a,b,c) ,(x,y,z) ) \mid |a-x|+|b-y|+|c-z|=1 \}$. I known how to get the treewidth of$n*n$grid is ... • 316 1 vote 0 answers 50 views ### Notion between connected and strongly connected graphs Let$G$be a directed graph without loops (or even better an oriented graph). Let us assume that$G$is finite. The graph$G$is connected if its underlying graph$G^*$is connected (i.e., for every ... • 1,759 0 votes 0 answers 71 views ### What is a combinatorial embedding? I got a reviewer comment saying that I should consider using combinatorial embeddings rather than idk what I should call what I was doing topological embeddings?. But I'm confused because as far as ... • 228 3 votes 1 answer 114 views ### Maximum cardinality matching on DAGs A question on computational complexity and graph theory. The problem of finding maximum cardinality matchings of undirected graphs (the largest selection of edges such that each vertex is "... 4 votes 0 answers 127 views ### Exploding number of homomorphisms I'm trying to tackle the following problem: given two graphs$A$and$B$, if there exists a graph$D$such that$\hom(A, D) > \hom(B, D)$(i.e. there is more homomorphisms from$A$to$D$than from ... 1 vote 0 answers 50 views ### Bound on the treewidth of a graph from modular contraction I cannot find a reference for this easy to prove result concerning the treewidth of a graph with respect to the treewidth of a modular contraction of it. Let$G=(V,E)$be a graph. A module$M \...
• 2,174
1 vote
Let $G$ be a finite, simple, undirected graph. What conditions on $G$ ensure that every rotation system of $G$ corresponds to a cellular embedding of $G$ on an oriented surface of small genus? (e.g. ...