# Questions tagged [graph-theory]

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

1,374 questions
Filter by
Sorted by
Tagged with
12 views

### Are there works on flows in networks with a dynamic structure?

I have a network that is initialized in some form, I am looking for a method to find feasible flows in it, the only problem is that, say I find an augmenting path, it could end up not just modifying ...
24 views

### Optimum partitioning of vertices into mutually disjoint subsets in a weighted graph

tl;dr I'm trying to partition my students into groups with respect to their preferences, i.e. they can declare if they want to be with someone in a group or if they do not want to be with someone in a ...
104 views

### Are maximum independent set and minimum clique cover also cover-packing problems? [closed]

Maximum independent set and minimum edge cover are a pair of related problems and are cover-packing problems. (Also see p114 of West's Introduction to Graph Theory) Are maximum independent set and ...
32 views

### Internal as well as external partition of (regular) graphs

Let $G$ be a simple finite undirected graph. Let $\{V_1,V_2\}$ be a partition of its vertex set; that is, $V_1\cup V_2=V(G)$ and $V_1\cap V_2=\emptyset$. The partition $\{V_1,V_2\}$ is said to be an ...
133 views

### Obtaining Sets of Ancestors Quickly in a Directed Acyclic Graphs

Suppose I have a DAG, $G = (V, E)$ and we know that all nodes in the DAG have at most $A$ ancestors. Let $V' \subseteq V$ be a subset of vertices of $V$. Is there a way to obtain the set of all ...
2k views

### What are graph grammars?

I have found information on graph grammars and graph rewriting, but the papers that I find on it are a bit thick. Can someone give a quick overview of what graph grammars are, as well as an overview ...
281 views

### Check if graph stays connected after edge swap

Checking whether a (simple, undirected) graph is connected can be done in linear time in the number of edges. What I am looking for is a more efficient way of checking whether it stays connected after ...
34 views

### Finding the cardinality of classes that divide all possible directed graphs into those that share k-subgraph cardinalities?

Let us have a set of nodes $V$, such that $|V|=N$. Let $G= (V,E)$ be an arbitrary directed graph on $V$. Let $U$ be the set of all possible directed graphs on $V$.Hence, $|U| = 2^{|V|^2}$. Now, for ...
101 views

### When does a bipartite graph have bounded treewidth?

As the title says, I want to know when the treewidth of a bipartite graph is bounded by a constant. What families of graphs are both bipartite and bounded treewidth? More generally, I would like to ...
265 views

31 views

### Are there classes where all Eulerian orientations can be listed in polynomial time?

Is there is a subclass of regular graphs (say 4-regular graphs) for which there is a polynomial time algorithm to list all Eulerian orienations? An Eulerian orientaiton of an (undirected simple) graph ...
84 views

### Can someone recommend a reference on graph minors structure theorem and sublinear treewidth?

Can someone recommend a reference on graph minors structure theorem and sublinear treewidth? Doesn't have to be the newest/strongest results as long as it's easier than tracking down all the papers ...
36 views

### Directed tree decompositions on subtrees of DAGs

Given a DAG, is the arboreal decomposition of the DAG with the guarantee that given a node $x$, $v$ such that $x$ is reachable from $v$ are in the subtree of $x$? If not, is there a similar ...
25 views

### Your task is to calculate the number of simple paths of length at least 2 in the given graph

how I can calculate this: Your task is to calculate the number of simple paths of length at least 2 in the given graph. Note that paths that differ only by their direction are considered the same (i. ...
31 views

### calculate the number of simple paths of length at least 2 in the given graph [closed]

how I can calculate this: Your task is to calculate the number of simple paths of length at least 2 in the given graph. Note that paths that differ only by their direction are considered the same (i. ...
112 views

### Standard Name for a vertex removal like operation

I have an operation that looks a lot like vertex removal, and I'm wondering if there's a standard name for it. Given a graph $G$ we remove a vertex $v$, but instead of removing the edges that were ...
27 views

### Are generalized map involutions captured by GNN?

In coming across a post related to this question's topic, posting in Theoretical Computer Science might be the right place. In combinatorial maps (1,2,3), are generalized map involutions captured by ...