All Questions
Tagged with reference-request graph-theory
48 questions
69
votes
7
answers
17k
views
What is a chess piece mathematically?
Historically, the current "standard" set of chess pieces wasn't the only existing alternative or even the standard one. For instance, the famous Al-Suli's Diamond Problem (which remained ...
25
votes
1
answer
3k
views
Number of hypercube unfoldings
While writing the code for this answer, I noticed that I not only could calculate the number of unfoldings of the $4$-cube, but also the number of the $n$-cube for more values of $n$. Basically, we ...
- 10.7k
20
votes
6
answers
4k
views
Graph theory from a category theory perspective
Are there any textbooks on graph theory written for a category theorist?
It would probably have to be on directed graph theory, but if there's some trick we can use to talk about undirected graphs as ...
13
votes
3
answers
3k
views
Koebe–Andreev–Thurston theorem - where can I find a proof?
Koebe–Andreev–Thurston theorem (known also as the circle packing theorem) says that any planar graph can be realized by a set of (interior-) disjoint disks corresponding to vertices, such that two ...
- 2,178
11
votes
1
answer
627
views
Representations of the automorphism group of graphs via spectral graphs theory
Given a (simple) graph $G=(V,E)$ with $V=\{1,...,n\}$ and let $A$ be its adjacency matrix.
I am interested in the representation theory (over $\Bbb R$) of the automorphism group $\def\Aut{\mathrm{Aut}...
- 13.6k
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
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 ...
5
votes
1
answer
651
views
Counting Problems where Labeled is Known but Unlabeled is Not
Cayley's formula states that the number of labeled trees on $n$ vertices is $n^{n-2}$. There are many nice proofs of this compact formula.
To contrast, counting unlabeled trees is considerably harder....
- 51
5
votes
1
answer
372
views
Graphs with minimum degree $\delta(G)\lt\aleph_0$
Let $G=(V,E)$ be a graph with minimum degree $\delta(G)=n\lt\aleph_0$. Does $G$ necessarily have a spanning subgraph $G'=(V,E')$ which also has minimum degree $\delta(G')=n$ and is minimal with that ...
- 13.4k
3
votes
1
answer
394
views
Min Bend Orthogonal Knots
I am seeking literature on 3D orthogonal drawings of knots,
especially minimum bend drawings.
An orthogonal drawing employs segments parallel to the axes of
a Cartesian coordinate system.
A bend is a ...
- 151k
2
votes
0
answers
905
views
Confusing notation for sets of unordered vs ordered pairs
Given two finite sets $X$ and $Y$, one may consider the ordered pairs $(x,y)$ with $x\in X$ and $y \in Y$. Then, $(x,y) \not= (y,x)$, and $(x,x)$ exists if $x\in X$ and $x\in Y$.
One may also consider ...
- 1,444
2
votes
2
answers
353
views
Matching with probabilistic edges
Let $p<1$ be a constant. Consider two sets $A,B$, each with $n$ vertices. For each pair $(a,b)\in A\times B$, the edge between $a$ and $b$ appears with probability $p$, independently of the ...
- 239
30
votes
2
answers
3k
views
An unfair marriage lemma
I am looking for a citeable reference to the following generalization of Hall's Marriage Theorem:
Given a bipartite graph of boys and girls. In addition to gender difference, they are divided into ...
- 32.4k
22
votes
5
answers
4k
views
Collection of conjectures and open problems in graph theory
Is there something similar to the Kourovka Notebook for graph theory (or anyway an organized, possibly commented, collection of conjectures and open problems)?
user60665
21
votes
7
answers
1k
views
Reference for topological graph theory (research / problem-oriented)
I would be interested in recommendations for topological graph theory texts. I think Gross and Yellen has a great chapter on topological graph theory, and I find Mohar and Thomassen's Graphs on ...
19
votes
3
answers
2k
views
Are "almost all" strongly regular graphs rigid?
I have heard through the academic rumor mill (my advisor heard from so-and-so about a result they heard from big-name who saw it in some journal, etc.) of the following theorem:
Theorem: Almost all ...
- 432
18
votes
1
answer
6k
views
Intersection between category theory and graph theory
I'm a graduate student who has been spending a lot of time working with categories (model categories, derived categories, triangulated categories...) but I used to love graph theory and have always ...
- 30.3k
17
votes
1
answer
1k
views
Which degree sequences are planar graphical?
The Erdős–Gallai theorem characterizes which degree sequences are graphical (i.e. realizable by a simple graph).
There has been some work on which degree sequences are planar graphical (i.e. ...
- 563
13
votes
2
answers
2k
views
What is the smallest 4-chromatic graph of girth 5?
It is known that the smallest 4-chromatic graph of girth 4 is the Grötzsch graph (11 vertices). What happens for girth 5?
The Brinkmann graph (21 vertices) has chromatic number 4, girth 5 and is 4-...
- 537
12
votes
7
answers
769
views
Does the notion of graphs with vertex multiplicity exist?
I need to use graphs where each vertex gets a natural number, $b(v)$, its multiplicity. These numbers indicate how many 'replications' of the vertex we have.
It is actually a way to write in a ...
- 222
11
votes
1
answer
467
views
Correspondence between matrix multiplication and a graph operation of Lovász
In his book "Large networks and graph limits", Lovász describes a multiplication operation (he calls it concatenation) on "bi-labeled graphs". An $(m,n)$ bi-labeled graph is a ...
- 2,339
11
votes
1
answer
337
views
Papers about decentralized search and cluster
I just start an independent study about small world network and clusters and I try to find papers about decentralized search and clusters.
Can anyone give me some references? Thanks!
EDIT (David ...
- 119
10
votes
1
answer
308
views
In what area of study does one encounter this principle in timetabling?
A while ago I saw an image like the one below in a lecture, which was supposed to represent a rail network in a (square) city:
The circles represent trains that are moving either North/South or East/...
- 4,049
10
votes
1
answer
492
views
is there a ‘nice’ lattice on the set of unlabelled graphs with $n$ vertices?
It is easy to endow the set of vertex-labelled graphs with $n$ vertices with a lattice structure: take the union and the intersection of the edge set as meet and join respectively.
However, I wonder ...
- 5,822
10
votes
2
answers
598
views
Is there a "simplest" way to embed a graph in 3-space?
I consider embeddings of graphs into 3-space with edges embedded as arbitrary curves. In the simplest (non-trivial) case the graph $G$ is a cycle or union of cycles, in which case the embeddings can ...
- 13.6k
10
votes
2
answers
728
views
Bounds on chromatic number of $k$-planar graphs
A $1$-planar graph can be drawn in the
plane so that each arc is crossed at most once by another arc.
A $k$-planar graph can be drawn so that each arc is crossed at most $k$ times.
Planar graphs are ...
- 151k
8
votes
0
answers
866
views
Decomposition of graphs as symmetric differences of copies of $K_{a,b}$
I was wondering if the following decomposition of graphs has been studied, whether it has a name, and what the literature might be on it.
Given a labelled graph G, we decompose its edge-set as a ...
- 1,444
8
votes
1
answer
448
views
Graphons and Graphs
The situation is as follows: assume we have a sequence of simple weighted graphs $(G_n)_{n\in\Bbb{N}}$. For the terminology that follows I refer to Limits of dense graph sequences by László Lovász and ...
- 81
8
votes
1
answer
449
views
Does Vizing's conjecture hold for the infinite graphs?
In finite graph theory, there are many (in)equalities which relate the integer value of a certain graph invariant (e.g. domination or chromatic number) for the product of two finite graphs (e.g. ...
8
votes
0
answers
2k
views
What is the best lower bound for the domination number in regular graphs of girth 5?
The following theorem is a classical result (see [Alon and Spencer, The probabilistic method, 2nd ed., Theorem 1.2.2]):
Theorem: Let $G$ be a graph on $n$ vertices with minimum degree $d$. Then $G$ ...
- 161
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
2
answers
637
views
Line graphs called "graph derivatives": any intuition?
Short version: in several papers, line graphs (and closely related graphs) are called graph derivatives or derived graphs; is there any intuition for such terminologies, in connection with the ...
- 1,444
7
votes
1
answer
142
views
equidistributed parameters on graphs
Let $\mathcal G_n$ be the set of (isomorphism classes of unlabelled) simple graphs on $n$ vertices.
I wonder whether there are any 'interesting' combinatorial parameters $a,b: \mathcal G_n\to \mathbb ...
- 5,822
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
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
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
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
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
0
answers
169
views
In the literature on infinite graphs, are there results on "periodizable" graphs?
Let $G=(V,E)$ be a connected countably infinite $k$-regular simple graph (no loops or multiple edges). For $A$ a finite subset of $V$, let me denote by $G_A=(A,E_A)$ the induced subgraph with vertex ...
5
votes
2
answers
441
views
Touching-tetrahedra graphs
Have the graphs representable by touching tetrahedra been explored?
Let $\cal T$ be a collection of tetrahedra in $\mathbb{R}^3$
with pairwise disjoint interiors.
Define a graph $G_{\cal T}$ to have ...
- 151k
4
votes
1
answer
646
views
Combinatorial geodesics
[There has been a flaw in my definition - as Sergei and Andreas pointed out. I hope I could fix it.]
I want to understand how the concepts of directions, straight (or shortest) lines, and geodesics &...
- 9,720
4
votes
2
answers
582
views
How to translate a graph coloring problem to algebraic or geometric language and solve it?
I want to know whether there are ways to use algebraic methods for solving graph theory problems (graph coloring problems). For example, is it possible to prove the four-color theorem purely with ...
- 4,195
4
votes
4
answers
268
views
Bijective operations on finite simple graphs
Let $\mathcal G_n$ be the set of (isomorphism classes of unlabelled) simple graphs on $n$ vertices.
I am interested in specific bijective maps $\mathcal G_n\to\mathcal G_n$, defined for all $n$. An ...
- 5,822
3
votes
3
answers
1k
views
Books that discuss spectral graph theory and its connection to eigenvalue problems in hyperbolic geometry
Hello,
Could you name a couple of books or downloadable lecture notes that discuss spectral graph theory and its connection to spectral problems in hyperbolic Riemann surfaces ? You could also ...
- 1,471
3
votes
1
answer
158
views
Sharp upper bound of the number of edges for graphs of thickness two
A graph $G=(V,E)$ has thickness $2$ if $E$ can be written as a disjoint union $E=E_1\cup E_2$ so that $G_1:=(V,E_1),G_2:=(V,E_2)$ are planar graphs. For instance, $K_5$ has thickness $2$. It is known ...
- 1,075
3
votes
1
answer
166
views
The spectral radius of a modified graph
Let $H$ be a graph and let $G=H \vee K_{1}$ be obtained by creating a new vertex and joining it to every vertex in $H$.
This situation has many different names: $G$ is called the cone or the ...
- 6,962
2
votes
0
answers
163
views
Graph theoretical representation of Wang Tile
We note that for one dimensional tiling problem of Wang Tile could be represented by a graph. Each cycle on the graph represents a periodic solution.
However, is there a well established counter-part ...
- 867
0
votes
0
answers
307
views
Graph Coloring: Two adjacent vertices share same color
Consider, subgraphs $G_1, G_2,...... G_x$ of graph $G$. Each subgraph has $k$ vertices.
Now, Fix subgraph $G_1$ and consider another subgraph $G_k$ where $1 <k \le x$.
The edge set ...
- 267