All Questions
5,777 questions
0
votes
0
answers
35
views
Can both conditions about vertex degrees hold true in a planar graph?
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
0
votes
0
answers
12
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 ...
- 516
1
vote
1
answer
176
views
Refinement of face vectors of the simplicial noncrossing hypertree complexes of McCammond
Einziger on page 65 of "Incidence Hopf algebras: Antipodes, forest formulas, and noncrossing partitions" presents the antipode of a noncrossing partition Hopf algebra as a graded sequence of partition ...
CommunityBot
- 1
4
votes
1
answer
229
views
Minimum number of possible proper colorings
Properly colored graph (edge has color) means that any two adjacent edges have distinct colors.
For any graph with $2k-2$ edges such that it can be properly colored using $k$ colors. What is the ...
- 91
0
votes
1
answer
164
views
Heuristics for lightweighted "cubic" spanning trees
I have the problem of calculating a good approximation of the minimimum-weight spanning tree with vertex-degrees in $\lbrace 1,3\rbrace$ of a complete symmetric graph, without parallel edges or self-...
CommunityBot
- 1
2
votes
1
answer
201
views
Can a Feynman graph be an empty set?
I was reading the section about Feynman graphs from the book Renormalization - An Introduction and this question arose. To set the notations, let $p \in \mathbb{N}_{+}$ and, for each $k \in \{1,...,p\}...
- 3,065
1
vote
0
answers
28
views
Integral hull of a polyhedron Q is polyhedron
Let $Q \subseteq R^n$ be a rational polyhedron and let $Q_I=Convexhull(Q \cap Z^n)$. By finite basis theorem, we have $Q=P+C$ for some rational polytope $P$ and finitely generated cone $C$ where $C=R_+...
- 21
-1
votes
0
answers
41
views
Is it possible to backtrack an optimization solver? [closed]
I have an optimization problem and was using a linear programming optimizer to find solutions. However, I find that past a certain size, the problem becomes "infeasible" and has no solutions....
5
votes
3
answers
274
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}{\...
- 13.4k
1
vote
0
answers
159
views
+50
A question relates to edge chromatic-polynomial
Properly colored graph (edge has color) means that any two adjacent edges have distinct colors.
For any graph with $m$ edges such that it can be properly colored using $k$ colors. What is the minimum ...
- 91
44
votes
4
answers
5k
views
Why is "P vs. NP" necessarily relevant?
I want to start out by giving two examples:
Graham's problem is to decide whether a given edge-coloring (with two colors) of the complete graph on vertices $\lbrace-1,+1\rbrace^n$ contains a planar $...
CommunityBot
- 1
1
vote
0
answers
59
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$ ...
2
votes
1
answer
875
views
Interpreting mincost flow dual variables
Consider the task of finding flow of size $b$ with minimum possible cost.
It may be formulated as linear programming in a following way:
$$\boxed{\begin{gather}
\min\limits_{f_{ij} \in \mathbb R} &...
CommunityBot
- 1
7
votes
0
answers
219
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 ...
- 4,600
5
votes
2
answers
556
views
What is the proper name for this "tersest path" problem in Infinite Craft?
The web game Infinite Craft gives you a starting set of elements $V_0\subset V$ and a mapping $E$ of type $V\times V\rightarrow V$. In fact, $F$ is commutative: $E(v_a,v_b) = E(v_b,v_a)$. So another ...
CommunityBot
- 1
19
votes
4
answers
1k
views
Minimal graphs with a prescribed number of spanning trees
As it's long ago since Erdős died and MathOverflow is the second best alternative to him (for discussing personal problems), I'd like to start a fruitful discussion about the following problem that I ...
- 8,597
2
votes
1
answer
137
views
Convergence of the average weight of an infinite path through a weighted directed graph
Consider a directed graph $G = (V, E, w)$, where $V$ is the set of vertices, $E \subseteq V \times V$ is the set of directed edges (with self-loops allowed), and $w : E \to \mathbb{R}_+$ is a weight ...
CommunityBot
- 1
1
vote
1
answer
177
views
Spectral characterization of complete or complete bipartite graphs
The Lemma 6 in this paper mention the following spectral characterization of complete or complete bipartite graphs:
Let $G$ be a connected graph with $\ge 2$ vertices. Then $\lambda_2=...=\lambda_{n-...
CommunityBot
- 1
0
votes
2
answers
530
views
Any idea of solving an optimization problem with cubic constraints?
I have the following optimization problem with cubic constraints, which is hard to solve. Are there any ideas, or related references, of solving such a problem?
$$ \begin{array}{ll} \underset {y, z} {\...
CommunityBot
- 1
7
votes
1
answer
165
views
$|G|/\alpha(G) \leq \eta(G)$ where $\eta(G)$ is the Hadwiger number
Let $G=(V,E)$ be a finite, simple, undirected graph. The Hadwiger number $\eta(G)$ is the maximum $n\in\mathbb{N}$ such that $K_n$ is a minor of $G$.
Hadwiger's celebrated conjecture states that $\chi(...
CommunityBot
- 1
1
vote
0
answers
122
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
1
vote
1
answer
86
views
Complexity of calculating the optimal amalgamation of an optimal cycle-cover
Let $G(V,E)$ be a complete symmetric graph with positive edge weights and let further $\mathcal{C}=\lbrace C_1,\,\cdots\,C_k\rbrace$ be the minimum-weight vertex-disjoint cycle cover.
The set $E$ of ...
CommunityBot
- 1
0
votes
0
answers
34
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
131
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 ...
- 12.2k
7
votes
1
answer
343
views
Can the corollary of the Ihara–Bass formula be extended to $ u^2 = 1 $?
Suppose there is a finite undirected graph $G(V,E)$ having $n$ vertices and $m$ edges.
The non-backtracking matrix $B$ is indexed by $2m$ directed edges and defined as
$$
B(a \to b, c \to d) = \delta_{...
- 6,357
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: ...
- 12.7k
2
votes
1
answer
126
views
"Balanced" separator which is independent set
I am looking for existence results on separators of $r$-regular graphs $G=(V,E)$, which have the property that
$S\subset V$ is a separator
for all $v,w\in S$ the edge $\langle v,w\rangle\not\in E$ (i....
CommunityBot
- 1
0
votes
0
answers
21
views
Easy instance of set cover
I am trying to prove that a natural greedy algorithm solves the following instance of the set cover problem: for a set of elements $e\in U$ with a set of weights $w_e$, we define the cost of a subset ...
- 4,049
0
votes
1
answer
86
views
Regular maps on hyperbolic plane for large number of vertices
I want to generate large regular maps of a tiling on hyperbolic space. How I can start doing that?
CommunityBot
- 1
2
votes
1
answer
445
views
Automorphism group of tensor product of two graphs
Is there any relation between the automorphism group of the tensor product of two graphs $G = G_1 \times G_2$ and the automorphism groups of $G_1$ and $G_2$?
I am aware of the nice results for the ...
CommunityBot
- 1
4
votes
1
answer
171
views
Forbidden minor characterization of polytope skeletons
Say that a graph is "$d$-dimensional" if it is the node-disjoint union of $1$-skeletons of closed convex polytopes in $d$ dimensions, or a subgraph thereof. So the $2$-dimensional graphs are exactly ...
12
votes
1
answer
2k
views
Hobbled rook tour – Hamiltonian cycle on square grid
Consider a square grid of even side length ($2n \times 2n$). It is easy to see that there must exist a Hamiltonian cycle on the corresponding grid graph. Such a cycle is called balanced if the number ...
CommunityBot
- 1
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}\\ ...
2
votes
1
answer
319
views
Why are graph embeddings defined the way they are?
In my recent question I asked about a proof for the fact that the dual of a dual graph embedding is equal to the original graph. Thinking about this a little more leads me to wonder why graph ...
- 32.1k
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 ...
- 12.7k
5
votes
1
answer
322
views
Connected graphs that are not 2 connected
In the great book by Harary and Palmer (Graphical Enumeration) one can find many interesting things about graph asymptotics.
For example it is stated that the number of all unlabeled graph is $\sim ...
- 1,446
7
votes
2
answers
242
views
Prove that $ n \leq d+1 $ under ordering constraints in $\mathbb{R}^d$
Let $x_1, \dotsc, x_n \in \mathbb{R}^d$ and $\theta_1, \dotsc, \theta_n \in \mathbb{R}^d$ be vectors such that for every $k \in [n]$, the following inequality holds:
$$
\langle x_k, \theta_k \rangle &...
- 109k
5
votes
1
answer
383
views
Shortest polygonal chain with $6$ edges visiting all the vertices of a cube
I am trying to find which is the minimum total Euclidean length of all the edges of a minimum-link polygonal chain joining the $8$ vertices of a given cube, located in the Euclidean space. In detail, ...
CommunityBot
- 1
10
votes
3
answers
460
views
Do triple-linked graphs exist?
Lets say that a finite simple graph $G$ is (intrinsically) fully triple-linked if for each embedding of $G$ into $\Bbb R^3$ we can find three disjoint cycles $C_1,C_2,C_3\subset G$ whose embeddings ...
- 13.6k
11
votes
1
answer
427
views
Graph chromatic numbers defined by interactive proof
Edit (2020-07-15): Since the discussion below is perhaps a bit long, let me condense my question to the following
Short form of the question: Let $G$ be a finite graph (undirected and without self-...
1
vote
0
answers
233
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
2
votes
1
answer
112
views
Finding survivable paths with a set of vulnerable edges
Consider a graph $G=(V,E)$ and a source-destination pair $(s,t)$. A set of edges $E'\subseteq E$ are vulnerable in the sense that at most $k$ of them may fail. My problem is to find a set of $(s,t)$ ...
CommunityBot
- 1
1
vote
1
answer
99
views
Is there any known upper bound for the local crossing number of a graph drawing in the plane?
The local crossing number ${\rm LCR(G)}$ of a graph $G$ is defined as the least nonnegative integer $k$ such that the graph has a $k$-planar drawing. In other words, it is the smallest possible number ...
- 21
1
vote
1
answer
73
views
"Gray code" for $[\omega]^{<\omega}$
Let $\newcommand{\oo}{[\omega]^{<\omega}}\oo$ denote the collection of finite subsets of the set of non-negative integers $\newcommand{\o}{\omega}\o$.
If $A,B$ are any sets, let $A \,\triangle \, B ...
- 24.2k
4
votes
0
answers
66
views
is a 4-connected planar graph still Hamiltonian after removing an edge?
We know that 4-connected planar graphs are Hamiltonian(by the known Tutte Theorem). Additionally, Thomas and Yu [1] proved that removing two vertices from a 4-connected planar graph still preserves ...
- 1,851
0
votes
1
answer
50
views
Cycle-Sculpturing with Minimal Vertex-Deletion
given a simple, finite and symmetric graph $G(V,E)$ with $n$ vertices and at least $n$ edges
Question:
how can the smallest set of vertices $W\subset V$ be calculated for which the graph induced by $...
- 5,429
2
votes
1
answer
147
views
What is the analogue of a Block-Cut Tree Decomposition in directed graphs?
Let $G$ be a connected, undirected graph. We define a block $B$ to be a maximal $2$-connected induced subgraph in $G$. It is easy to see that any two distinct blocks are either disjoint or overlap at ...
- 5,407
1
vote
1
answer
87
views
Bounds on the number of proper 3-colorings of cubic graphs
Are there known bounds on the number of proper 3-colorings of a 3-regular in terms of vertex count?
- 12.7k
0
votes
1
answer
77
views
Bipartite matching where every adjacent pair of vertex on the left side of the graph has at least 1 vertex matched
The question is as stated above. I want to devise bipartite matching algorithm where it determies whether every adjacent pair of vertex on the left side of the bipartite graph has at least 1 vertex ...
- 126