All Questions
Tagged with reference-request graph-theory
453 questions
7
votes
2
answers
186
views
Graph embedding that locally minimizes total edge lengths
I consider a graph $G$ (possibly infinite, but locally finite) embedded in the Euclidean plane $\mathbb{E}^2 \cup \{\infty\}$ such that each local perturbation of the embedding "increases the ...
- 2,581
7
votes
2
answers
247
views
complicated combinatorial algorithms with good descriptions
For educational purposes, I am looking for an example of a complicated, elementary, but very well-explained combinatorial algorithm.
Such an example might be a bijection between two easily described ...
7
votes
1
answer
785
views
Chromatic number of induced subgraphs as upper bound to the chromatic number
Motivation: At the Erdős100 conference in Budapest András Gyárfás presented some interesting conjectures. One of them was the following:
Given that in a graph $G$, every subgraph $H$ formed by ...
- 3,004
7
votes
2
answers
560
views
What is a hypergraph minor?
Is there a theory of hypergraph minors? I could only find some attempts to define them at papers/theses, whose main topic was something else. What would be a useful definition? Does the hypergraph ...
- 18.9k
7
votes
1
answer
393
views
Kneser graph with overlap
Consider a graph with the vertices being all subsets of size $n$ of a set of size $2n$. Two vertices are connected if their overlap has size at most one. What is the chromatic number of this graph?
...
- 1,209
7
votes
0
answers
97
views
What is known about chromatic polynomial of hypergraph at $-1$
Let $H$ be a hypergraph and let $P_H$ denote its chromatic polynomial. I am interested in the best results interpreting $P_H(-1)$. I am interested both in the general case (which I think is hard) as ...
- 7,875
7
votes
0
answers
74
views
Graphs all of whose cuts are positive
Let $(V, E, w)$ a weighted graph, with vertices $V$, edges $E$, and signed weight $w:E\to \mathbb R$.
I am interested to know other popular properties that are known to imply, or are equivalent to, ...
- 2,041
7
votes
0
answers
102
views
Median spaces as retracts of hypercubes
It is known (See e.g. here, Theorem 2.1) that median graphs are retracts of hypercubes.
Question: Is it also known that median metric spaces are retract of some $l¹$ product of unit intervals?
By ...
- 887
7
votes
0
answers
171
views
What is known about the distribution of lengths of the cycle you get by adding an edge to a uniform spanning tree?
Let $G$ be a finite, connected graph. Let $T$ be a uniform spanning tree, and let $e$ be a uniformly random edge not in $T$. When we add $e$ to $T$, we get a subgraph with a unique cycle, $C$. I am ...
- 1,462
7
votes
0
answers
279
views
Relations between Betti numbers for clique complex
Given a clique complex $K$ constructed from a discrete set of vertices (i.e. its faces are isomorphic to the set of cliques in the 1-skeleton of $K$.), it seems that the Betti numbers $\beta_k$ ...
- 8,071
7
votes
0
answers
232
views
The smallest order of a 4-chromatic graph of given girth
Let $n_4(g)$ denote the smallest order of a $4$-chromatic graph with girth $g$. It is known that $n_4(4)=11$ [2] and $n_4(5)=21$ [1]. By a famous proof of Erdös, it is known that $n_4(g)$ is well-...
- 537
7
votes
0
answers
229
views
Has anyone seen these binary trees (Catalan-type related to the Gegenbauer polynomials and Motzkin paths)?
The OEIS entry A121448 enumerates binary trees with $n$ edges and $k$ vertices with outdegree 1.
Has anyone seen these trees?
The o.g.f. for this entry, $G(x,t)$, is essentially a discriminant ...
- 10.5k
6
votes
4
answers
2k
views
Delaunay triangulations and convex hulls
This is a reference request.
I have the impression that those who work in computational geometry are accustomed to the following. You have some locally finite set of sites in $\mathbb{R}^n$ and you ...
6
votes
1
answer
237
views
Does the existence of a unique chromatic (possibly transfinite) number for every (possibly non-finite) simple graph imply the axiom of choice?
Assuming the axiom of choice I can write for any cardinal number $\kappa$ and any simple graph $G$ that a function $f$ is a $\kappa\text{-coloring}$ of $G$ if and only if the cardinality of the image ...
- 2,506
6
votes
2
answers
318
views
Universal graphs on higher cardinals
The Rado graph contains every finite graph as induced subgraph, and its also holds for countable graphs. So it is an universal graph of size $\aleph_0$, which contains all graphs of size $\aleph_0$ as ...
- 432
6
votes
2
answers
477
views
Heyting algebras originating from directed graphs
The category RefGph of reflexive directed graphs is the functor
category $\hat{∆}_1=\mbox{Fun}(∆^◦_1,$Set), where $∆_1$ is
the simplex category truncated at level 1.
Hence the poset Sub(X) of ...
- 567
6
votes
3
answers
855
views
Fundamental solution of Discrete Laplace in the plane
We consider a discretization of the Laplace operator on $\mathbb Z^2$, https://en.wikipedia.org/wiki/Discrete_Laplace_operator
Then, it is natural to consider its fundamental solution $u$, i.e. $|u(x)...
- 5,063
6
votes
2
answers
400
views
Geometric dominating set: NP-complete?
Let $G=(V,E)$ be a geometric graph, a graph embedded in the plane whose edge lengths are
the Euclidean distance between its endpoint vertices.
Say that a set of vertices $D \subseteq V$ is a geometric ...
- 151k
6
votes
1
answer
295
views
Disjoint paths between four vertices
Consider the following property of an undirected graph: For any four distinct vertices $a,b,c,d$, there is a path from $a$ to $b$ and a path from $c$ to $d$ such that the two paths do not share any ...
- 95
6
votes
1
answer
899
views
Reconstruction Conjecture: Group theoretic formulation
As we read from wiki, informally, the reconstruction conjecture in graph theory says that graphs are determined uniquely by their subgraphs.
Is there a group-theoretic formulation of this conjecture?
...
- 2,855
6
votes
2
answers
936
views
Human brains considered as directed graphs
I assume that human brains can be considered as directed graphs with neurons as nodes and synapses as edges. I explicitly don't want to consider the weights, the dynamics of neural activity (based on ...
- 9,720
6
votes
3
answers
430
views
Name for Kneser/Johnson-like graphs?
I wonder if the following simple generalization of Johnson and Kneser
graphs has a name? Let the vertex set of the graph $G(n,k,t)$ be the
set of $k$-element subsets of an $n$-set, with two $k$-sets ...
- 349
6
votes
1
answer
304
views
Citations graphs: what is known?
There has been much research related to web graphs and social graphs.
They can be thought of as a kind of random graphs, but the point is that
they are different from the well-known Erdős–Rényi model.
...
- 24.9k
6
votes
1
answer
610
views
Directed graph minor theorems
In proving the graph minor theorem, Robertson and Seymour proved a stronger statement, namely that the directed graph minor theorem is true, using the definition
A directed graph is a minor of ...
- 612
6
votes
2
answers
661
views
Cut locus in a graph
I am wondering if the concept of a cut locus has been defined and explored in discrete graphs, rather than their usual home on manifolds?
The Wikipedia definition (which I believe I (co-?)authored) is:...
- 151k
6
votes
2
answers
1k
views
Determinant of the oriented adjacency matrix of a tree
Let $(V,E)$ be a finite oriented directed graph, with vertices and edges ordered, and $M$ the $|V|\times |E|$ matrix with entries
$$ m_{ve} = \begin{cases} 1 &\text{if $e$ points at $v$}\\
-1 &...
- 27.8k
6
votes
1
answer
746
views
Relationship between spectral gaps of adjacency and Laplacian matrices of graphs
Let $G$ be an undirected simple graph on $n$ vertices, with self-loops allowed, and with arbitrary positive edge weights $w_{u,v}$ (which is $0$ if there is no edge between $u$ and $v$).
Let $A$ be ...
- 150
6
votes
1
answer
79
views
Looking for the name or reference regarding a bipartite graph parameter
I'm writing a paper about a math puzzle and the thing I'm studying ends up equivalent to finding the following parameter of a bipartite graph G with parts X and Y:
The largest $k$ such that any $k$ ...
- 255
6
votes
1
answer
454
views
What is/are the best bound/s on the sum of squares of degrees in a graph?
Let $G$ be a graph with degrees $d_{1},\ldots,d_{n}$. I am interested in upper bounds on
$$
\sum_{i=1}^{n}{d_{i}^{2}}.
$$
An example is de Caen's bound:
$$
\sum_{i=1}^{n}{d_{i}^{2}} \leq e(\frac{2e}{...
- 6,962
6
votes
1
answer
644
views
Random path in a graph
Consider a finite graph $G$. I would like to define a random path between two vertices $s$ and $t$ of the graph $G$ by looking at a measure $\mu$ on all spanning trees. Then the probability of a given ...
- 4,432
6
votes
1
answer
305
views
Name of a binary matroid coming from the cycle space of a graph
In some of my recent work, I have 'discovered' a binary matroid which I will describe below.
Given a graph $G$, let $H_1(G, \mathbb{Z}/2\mathbb{Z})$ denote the cycle space. This is a vector space ...
- 291
6
votes
2
answers
461
views
Cubic graphs decompositions
There are many interesting computational problems related to connected cubic graph decomposition. For instance, decomposition of cubic graph into a perfect matching and a connected 2-factor (NP-...
- 2,993
6
votes
0
answers
373
views
Circle numbers on edges of a graph
Let $k$ vertices in a graph be given. Some pairs of vertices are connected by an edge, each edge is labeled either $\{1,2\}$, $\{1,3\}$, or $\{2,3\}$. We can circle some of the numbers on the edges. ...
- 277
6
votes
0
answers
116
views
The properties of almost all directed graphs
A mathematician on the forum previously requested a reference on human brains modelled as directed graphs. This makes sense as neurons are mostly unidirectional and I have been thinking about similar ...
- 3,871
6
votes
0
answers
477
views
The topos of a graph
If $G$ is, for example, a finite directed graph, one can attach to it a topos $T_G$ whose objects are "$G$-sheaves". A $G$-sheave $F$ is the data of:
For each verticies $x$ a set $F(x)$, for each ...
- 42.4k
6
votes
0
answers
138
views
Counting $K_4$ on two graphs sharing the same vertices
Let $f(G)$ denote the number of $K_4$ in a graph $G$ and $e(G)$ denote the number of edges of $G$.
Consider two simple graphs $G_1$ and $G_2$ having the same set $V$ of $n$ vertices and let $H_1(U)$ ...
- 3,153
6
votes
0
answers
116
views
Chromatic numbers for coloring-constrained graphs
I am interested in any and all articles about chromatic numbers applying to constrained colorings of a graph. For example, if a graph must be (properly) colored so that there is a 2-color path ...
- 91
6
votes
0
answers
359
views
Have topographs been studied before?
This is my first post on MO so I hope this question is suitable. I have quite a few definitions which I will need to state before my questions at the end of this post. Please let me know if anything ...
- 661
6
votes
0
answers
749
views
Tensor product of quivers
As a special case of a general construction I have constructed "accidentally" a tensor product of quivers aka directed multigraphs (aka directed graphs for category theorists). Probably this ...
- 63.1k
5
votes
2
answers
718
views
Bound on graph domination number when min degree is 7
I have a graph $G$ whose minimum vertex degree is $\delta=7$.
I am seeking an upper bound on the domination number $\gamma(G)$
in terms of the number of vertices $n$ of $G$.
I found a paper by
Edwin ...
- 151k
5
votes
2
answers
391
views
Conjecture about minimal number of edge crossings in complete bipartite graphs
I am interested in the status of the conjecture about the minimum number of edge crossings $cr(K_{m,n})$ in a drawing of the complete bipartite graph $K_{m,n}$.
The Wikipedia article https://en....
- 125
5
votes
1
answer
274
views
Is there a polynomial-time algorithm to check if a signed graph contains an odd-K5 minor?
I suspect this exists, if anyone has a reference please that would be very helpful.
By signed graph, I mean each edge is designated either odd or even (e.g. as in Guenin's result for weakly bipartite ...
- 311
5
votes
2
answers
439
views
Condition(s) for the full autormophism group $\operatorname{Aut}(C(G, S))$ of the Cayley graph of $G$ to be isomorphic to $G$
If $\Gamma = C(G, S)$ is the (undirected) Cayley graph of a finite group $G$ with generating set $S$, then $G \le \operatorname{Aut}(\Gamma)$, the "full" automorphism group of $\Gamma$.
When is it ...
- 178
5
votes
2
answers
373
views
Genus of Tutte-Coxeter Graph
What is the genus of the Tutte-Coxeter graph -- the incidence graph of the
GQ of order 2? Seems like it should be well known, since nearly every other
parameter for that graph is known, but I can ...
user48028
5
votes
2
answers
943
views
Methods to approximate the betweenness centrality on large networks
To calculate the between centrality wiki def:
$g(v) = \sum_{s\neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}$
of a node in a graph/network;$\sigma_{st}$ is the ...
- 197
5
votes
1
answer
310
views
A variant of Ramsey numbers
The well known Ramsey number $R(k)$ is the least integer $n$ so that every 2-edge coloring of $K_n$ contains a monochromatic $K_k.$
Another interpretation of the above definition is that every graph ...
- 3,463
5
votes
2
answers
529
views
Involution-free Trees are Asymmetric: Reference request
I am currently writing a proof in which I need to use the fact that if a tree has no involutions, its automorphism group is trivial (ie, if a tree has any non-trivial automorphisms, then it has at ...
- 53
5
votes
2
answers
779
views
Does this type of graph have a name?
The following graph property has come up naturally in some work I've been doing, and it seems like something that may have already been studied.
Namely, let $G$ be a graph with no loops or double ...
- 23k
5
votes
1
answer
258
views
A graph similar to the Bruhat graph, what is it called?
The weak Bruhat graph (or 1-skeleton of the permutohedron) $B_n$ can be constructed as follows:
the vertices of $B_n$ are the permutations of the tuple $(1,...,n)$, two are joined by an edge, if they ...
- 13.6k
5
votes
1
answer
206
views
A simple requirement for a degree sequence to be graphical
The following theorem about the degree sequences of finite simple graphs is quite easy to prove from the Erdos-Gallai theorem.
Let $0 \lt \alpha \le \beta \lt n$ be integers. Call $(\alpha,\beta,n)...
- 37.7k