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.
5 questions from the last 7 days
0
votes
0
answers
35
views
Does a graph exist such that its vertices can be distributed among "boxes" so that conditions are satisfied?
I want to a graph $G$ on $52$ vertices, call them $x_1 := (a_1, b_1), \ldots, x_{52} = (a_{52}, b_{52})$, where $G := \{(x_i, x_j): x_i \text{ and } x_j \text{ share a common element}\}$ such that the ...
- 41
0
votes
0
answers
16
views
2-regular directed graphs where the commutative property or relation holds at every vertex and abelian Cayley digraphs
2-regular directed graphs where the commutative property or relation holds at every vertex and abelian Cayley digraphs.
You are given a 2 regular (2-in 2-out) directed graph where you can check that ...
- 41
1
vote
1
answer
37
views
Graph classes which have small edge k-cuts
I am interested in graph classes that have the following property: There exists a function $f(k)$ such that for every graph $G$ in the class, for every choice of $k$ vertices $v_1, \ldots, v_k$ in the ...
- 526
-2
votes
0
answers
60
views
Can both conditions about vertex degrees hold true in a planar graph? [closed]
I am working on a problem about planar graphs and trying to understand if two statements can both be true at the same time.
The problem states that for any planar graph with at least 3 or more ...
- 1
1
vote
0
answers
60
views
Bipartite Representation of a Directed Graph
I am working on a combinatorial optimization problem and have constructed a bipartite graph as a representation of a directed graph.
The construction is as follows:
Given an initial directed graph $G$ ...
