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.
15 questions from the last 30 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$ ...
7
votes
0
answers
220
views
Is there a Cayley graph with end space infinite and discrete?
A Cayley graph of a finitely generated group must be locally finite, and we know end spaces of locally finite graphs must be compact - so we can't have an infinite and discrete end space in this ...
- 407
5
votes
3
answers
286
views
The max-clique chromatic number of a graph
Let $G = (V,E)$ be a graph. Every clique, that is, complete subgraph, is
contained in a maximal clique with respect to $\subseteq$ (this is
an easy consequence of Zorn's Lemma). Let $\newcommand{\MC}{\...
- 48.9k
1
vote
0
answers
123
views
Growth polynomial of the Associahedron graph ? (Is it approximately Gaussian ?)
Consider Associahedron, consider graph build from its vertices and edges. Choose some vertex. Let us count the number of vertices on distances $k$ from the selected vertex. Write a generating ...
- 24.9k
0
votes
0
answers
35
views
separator and vertex-connectivity
A definition of "separator" is the following: Let $G$ is an $n$-vertex graph, then $S\subseteq V(G)$ is a separator if there is a partition $V=A\cup B\cup S$ such that $|A|,|B|\le 2n/3$ and ...
- 281
3
votes
1
answer
132
views
Is a simply connected locally 2-connected complex a union of spheres and planes?
Let $X$ be a (potentially infinite) 2-dimensional simplicial complex. Then each link at a vertex $x\in X$ is a graph.
Question. If $X$ is simply connected and each link is 2-connected (in the sense ...
- 13.6k
1
vote
1
answer
80
views
What are the efficient algorithms to compute Hamiltonian paths on Cayley graphs of finite groups ? Can GAP do it?
The famous Lovasz conjecture predicts existence of the Hamiltonian path on Cayley graphs. In general finding such a path is NP-complete problem, but there are many heuristic algorithms.
Question 1: ...
- 24.9k
3
votes
1
answer
200
views
Matrix-tree theorem for inverse matrices
Let $L$ be the Laplacian of a directed weighted graph on $n$ nodes, e.g., for $n=4$:
$$
L = \left(\begin{array}{cccc} w_{1,1}+w_{1,2}+w_{1,3}+w_{1,4} & -w_{1,2} & -w_{1,3} & -w_{1,4}\\ ...
- 20.2k
2
votes
1
answer
111
views
Is there a ternary Cayley graph on 27 vertices that is a non-complete core?
Is there a non-complete ternary Cayley graph that is a core with $3^3 = 27$ vertices?
By a ternary Cayley graph, I mean a (simple, undirected) graph whose vertex set is $\mathbb{Z}_3^n := \bigoplus_{i ...
- 331
1
vote
0
answers
235
views
Claimed proofs of graph labelling conjectures [closed]
The following recent series of arXiv papers claims to prove several of the most famous graph labelling conjectures. Edinah Gnang is the common author, none of the papers seem to be published further, ...
- 1,319
0
votes
0
answers
24
views
Minimizing intersections between spanning trees of graph embeddings in polynomial time
Assume I have $N$ complete graphs $G_1, G_2,...,G_N$, and consider their embeddings $E_1, E_2,...,E_N$ in $\mathbb{R}^2$. Is there a (potentially stochastic) polynomial time algorithm to construct ...
- 1