# Questions tagged [graph-theory]

Questions about the branch of combinatorics called graph theory (not to be used for questions concerning the graph of a function). This tag can be further specialized via using it in combination with more specialized tags such as extremal-graph-theory, spectral-graph-theory, algebraic-graph-theory, topological-graph-theory, random-graphs, graph-colorings and several others.

3,932 questions
Filter by
Sorted by
Tagged with
24 views

### Bandwidth of two-dimensional grid graphs

Suppose that $G$ is a subgraph of the two-dimensional grid and there are $n$ vertices in $G$. What is the maximum possible graph bandwidth of $G$ as a function of $n$? If $G$ is a square grid graph ...
26 views

### how to find out a node that is not reachable from other nodes in a list and then add an edge b/w that node and a random node in python [closed]

I have an adjacency matrix of graph G=(V,E) and a list of nodes 'v' subset of V. Now I want to find out node/nodes of 'v' that is/are not reachable from other nodes of 'v' and then adding an edge ...
56 views

### Effect of collapsing two vertices of distance $2$

Motivating example. Consider the graph $G=(V,E)$ with $V = \{0,1,2,3\}$ and $E = \big\{\{i,i+1\}: i\in \{0,1,2\}\big\}$. We have $\chi(G) = 2$, but if we collapse $0$ and $3$, we get the complete ...
41 views

### De Morgan applications for Graphs [closed]

$\DeclareMathOperator\comp{comp}$Are the De Morgan laws applicable for simple graphs? For example if I know that certain operations like Union, Intersection and Complement are working for $G$ and $H$ ...
21 views

### Clustering coefficient in a directed graph

I am wondering what the meaning of the clustering coefficient in a directed graph. I know how to calculate it: local clustering coefficient formula, retrieved from [Wikipedia]1 and I know how to ...
30 views

### Perfect Cayley graphs for abelian groups have $\frac{n}{\omega}$ disjoint maximal cliques

Let $G$ be a perfect/ weakly perfect Cayley graph on an abelian group with respect to a symmetric generating set. In addition let the clique number be $\omega$ which divides the order of graph $n$. ...
24 views

### Finding minimum weight perfect matchings in sparse bipartite graphs

Question: What can be recommended for finding optimal perfect matchings in large bipartite graphs with small vertex degree if the edge-weights are positive real values? I am looking for ...
368 views
+50

54 views

### What is the standard definition of dual of disconnected planar graph when underlying graph derives 'product structure' over connected graphs?

Dual graph of a plane graph has a standard definition https://en.wikipedia.org/wiki/Dual_graph and an edgeless graph on $n$ vertices is planar. What is the standard dual graph of such a graph? Update ...
5k views

### Proofs where higher dimension or cardinality actually enabled much simpler proof?

I am very interested in proofs that become shorter and simpler by going to higher dimension in $\mathbb R^n$, or higher cardinality. By "higher" I mean that the proof is using higher dimension or ...
29 views

10 views

### Finding weight minimal swap-free directed vertex covers

Suppose a complete directed graph is given with $n$ vertices and $n(n-1)$ weighted arcs $a_{ij}$ and we have $\omega(a_{ij}\ne\omega{a_{ji})$ for at least one pair of antiparallel arcs and the ...
Let $V$ be a set of $n$ vertices. Fix $3 \le k \le n$. Let $\binom V k$ be the set of all $k$ element subsets of $V$. We add the edges in $V$ as follows: Let $\mathcal S \subseteq \binom V k$ be ...