All Questions
Tagged with reference-request graph-theory
453 questions
4
votes
2
answers
666
views
Minimal labeling of a directed acyclic graph
I define a $n$-labeling of a directed acyclic graph $G = (V, E)$ as a function $f$ from $V$ to the power set of {1, ..., $n$} such that for any $x, y \in V$, $x \neq y$, we have $f(y) \subset f(x)$ ...
- 431
8
votes
2
answers
572
views
Clique weight-optimal matchings on n-partite graphs.
I am trying to analyze the results of a physical experiment consisting of $n$ "runs" of measurements, each of which generates a set of $k$ points in Euclidean space. The following problem came up when ...
- 103
2
votes
0
answers
216
views
Polyhedral embeddings of large face-width where all faces have the same length
Where can I find examples of polyhedral embeddings of simple graph with large face-width, such that all the faces have the same length?
By polyhedral embedding I mean an embedding of the graph on a ...
- 884
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
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
2
answers
2k
views
Number of Ordered Trees of given degree sequence
Is there any result known about counting the number of (unlabeled) ordered trees which follow a given unordered degree sequence?
Here an ordered tree is understood as a rooted tree in which the order ...
- 57
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
1
vote
1
answer
375
views
Definition of convex cycles
Consider the following definition.
Let $C$ be a cycle of a simple graph $G$. We say that $C$ is convex if for any pair of distinct vertices $u,v \in V(C)$ $$ d_C(u,v) < d_{G-C}(u,v).$$
Is there ...
- 3,463
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 ...
17
votes
3
answers
2k
views
Laplacians on graphs vs. Laplacians on Riemannian manifolds: $\lambda_2$?
A graph $G$ is connected if and only if
the second-largest eigenvalue $\lambda_2$ of
the Laplacian of $G$ is greater than zero.
(See, e.g.,
the Wikipedia article on algebraic connectivity.)
Is ...
- 151k
12
votes
5
answers
2k
views
Extensions of the Koebe–Andreev–Thurston theorem to sphere packing?
The Koebe–Andreev–Thurston theorem states that any planar graph can be represented
"in such a way that its vertices correspond to disjoint disks, which touch if and only if
the corresponding vertices ...
- 151k
1
vote
1
answer
309
views
counting edges in tesselations of a torus
Here's another one that no one's rushing to answer on stackexchange.
Tesselate a torus with finitely many simply connected polygons. Do not allow four or more of them to meet at a point. Count the ...
2
votes
3
answers
274
views
learning sources about Ihara Coefficient
Do we have any good sources(lecture notes or books) for learning about $Ihara$ Coefficient?
Is there any relation between $Ihara$ Coefficient and the eigenvalues of graphs?
Thanks for any help.
- 4,784
16
votes
5
answers
3k
views
Simple random walk on a locally finite graph: when is it recurrent?
I'm giving a talk tomorrow about a result in computer science which I recently proved. It's a recurrence-transience result on a random process which is related in spirit to a simple random walk. My ...
- 30.3k
8
votes
2
answers
811
views
A hypercube-related graph
For integer $n\ge 3$, consider the graph on the set of all even vertices of the $n$-dimensional hypercube $\{0,1\}^n$ in which two vertices are adjacent whenever they differ in exactly two coordinates....
- 23k
8
votes
1
answer
682
views
Red-blue alternating Menger's theorem
Suppose we have a graph where every edge is colored red or blue. We say that a path is alternating if the red and blue edges alternate in it. Our goal is to find many edge/vertex-disjoint alternating ...
- 18.9k
4
votes
3
answers
755
views
Is this statement about the real edge space of a graph known or trivial?
The statement is:
($u$ is a fixed node in a fixed graph $G$)
$G$ is 3-connected
if and only if
the set of u-cycles span $\mathbb{R}^{E(G)}$.
A u-cycle is a simple (no vertex repetitions) cycle in G ...
- 406
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
12
votes
1
answer
593
views
Characterizing graphs by their "walkers"
Let $G$ be a (large) graph and $W$ another (smaller) graph.
$W$ is what I call a walker.
Let me use "vertices" and "edges" for $G$ and
"nodes" and "arcs" for $W$.
$W$ has a distinguished node, its ...
- 151k
2
votes
0
answers
642
views
Hamiltonian paths in subgraphs of rectangular lattice graphs
Is following decision problem NP-hard / NP-complete:
Having vertex-induced subgraph of rectangular lattice graph determine if any Hamiltonian path exists
Having vertex-induced subgraph of rectangular ...
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
5
votes
1
answer
637
views
Upper bounds on number of vertices of graphs whose complements has no induced cycles of certain lengths
Let $G$ be a finite, simple, undirected, connected graph. Suppose that $G$ has maximal degree $d$ and the complement $G^c$ has no induced cycles of lengths $i$, for $4 \leq i \leq l$. My question is:
...
- 30.5k
2
votes
2
answers
253
views
Infinite connectedness and projective graphs
Call two nodes $v$ and $w$ of a graph infinitely connected iff there is an infinite path $P(v)$ starting at $v$ and an infinite path $P(w)$ starting at $w$ such that there is an $x \in P(v) \cap P(w)$ ...
- 9,720
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
2
votes
1
answer
242
views
Edge-objectified graphs
Consider an undirected graph. It's obvious what is a vertex (≙ object) and what is an edge (≙ fact).
(source)
Now "objectify" the edges (≙ facts) by adding an extra vertex ...
- 9,720
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
14
votes
0
answers
522
views
Reconstruction conjecture and partial 2-trees
Reconstruction conjecture says that graphs (with at least three vertices) are determined uniquely by their vertex deleted subgraphs. This conjecture is five decades old.
Searching relevant literature,...
- 281
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
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
15
votes
1
answer
1k
views
Has the technique of "sprinkling" been used in studying random matrices?
In 1982, while studying the component sizes of random subgraphs of a hypercube, Ajtai, Komlós, and Szemerédi introduced a technique that came to be known as sprinkling. In this technique, the edges of ...
- 4,922
5
votes
1
answer
700
views
What is the pathwidth of the 3D-grid (mesh or lattice) with sidelength k?
This question is now also on https://cstheory.stackexchange.com/questions/4081/what-is-the-pathwidth-of-the-3d-grid-mesh-or-lattice-with-sidelength-k, where a discussion started, and one reference ...
- 151
1
vote
0
answers
137
views
Number of ways to separate a terminal from labelled vertices in a graph
I have a question about the number of different ways to separate a terminal vertex from labeled vertex sets in a simple graph. There is a bound on this number that I am interested in. I have succeeded ...
- 495
4
votes
3
answers
410
views
Name of an operation on graphs
I asked this a week ago on math.SE, but haven't obtained an answer yet, so I hope it is fine to ask this here too.
Let $G$ and $H$ be two possibly directed, non necessarily simple, vertex-labelled ...
- 1,164
2
votes
1
answer
257
views
Weighted Polytope
I am curious if this kind of construction (or something similar) exists:
Consider a convex polytope $P$ and then consider the graph of the polytope $G(P)$ (1-skeleton). Suppose a weighting structure ...
- 475
5
votes
1
answer
564
views
Every connected planar graph contains adjacent vertices with at most 2 common neighbors
I am looking for a reference for the following fact.
Let $G$ be simple undirected connected planar graph with $\geq 2$ vertices. Then $G$ contains an edge $\{u,v\}$ such that $|N(u) \cap N(v)| \leq ...
- 495
13
votes
1
answer
719
views
Homotopy theory for spanning trees of a graph
I am studying a paper of L. Lovász, ``A homology theory for spanning trees of a graph,'' but professor Babai has told me that Lovász later realized that this work is better framed in the language of ...
- 5,898
3
votes
0
answers
284
views
Semantics of neural network-like structures
Background
Language (of mathematicians and most other people) has a sequential surface structure and a tree-like deep structure. So semantics usually is the semantics of such syntactical structures: ...
- 9,720
3
votes
1
answer
277
views
Theorems about the directed bandwidth of a rooted tree?
Let $T$ be a rooted tree with root $r$. Say an ordering $v_1,\ldots,v_n$ of the vertices of $T$ is a search order if $v_1=r$ and for all $2 \leq i \leq n$, there is $j < i$ such that $v_j$ is the ...
- 4,922
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
8
votes
0
answers
152
views
Disjoint Rooted Paths with Specified Patterns
Let $S:=$ { $s_i : i \in [k]$ } and $T:=$ { $t_i : i \in [k]$ } be disjoint subsets of vertices of a graph $G$. Furthermore, let $A$ be a subset of $S_k$ (the symmetric group on $[k]$). A set of ...
- 32.1k
10
votes
3
answers
1k
views
What is this operation on graphs called?
I am currently studying certain infinite graphs in terms of their finite induced subgraphs.
For the graphs that I am interested in the class of finite induced subgraphs is closed under the following ...
- 16.2k
4
votes
4
answers
452
views
Bound on the number of unlabeled cographs on n vertices
A cograph is a graph without induced $P_4$ subgraphs. I am looking for a reference for a simple exponential bound on the number of distinct unlabeled cographs on $n$ vertices. By the Mathworld ...
- 495
15
votes
2
answers
755
views
Random noncrossing chords of a circle
Suppose you generate random chords of a circle, with endpoints selected uniformly over the circumference, rejecting any chord that crosses a previously generated chord.
The disk is then partitioned ...
- 151k
5
votes
1
answer
392
views
Ref request: A graph G contains H as a minor iff it contains one of finitely many graphs as a topological minor
For definitions of graph minors and topological minors, see wikipedia's article on graph minors.
Theorem: For every graph H, there is a finite set of graphs, say S(H), such that G contains H as a ...
- 1,332
3
votes
2
answers
259
views
Have this subclass of split graphs been studied before?
I am interested in the properties of the following subclass of split graphs:
The class consists of all split graphs $G=(C\cup I)$ where $C$ is a clique and $I$ an independent set, and every pair of ...
- 185
8
votes
3
answers
602
views
Decimating the infinite grid graph
Let $G$ be the graph whose nodes are the points of
$\mathbb{Z}^d$ in the nonnegative orthant (i.e., all
coordinates are $\ge 0$), with edges connecting each
pair of points separated by unit distance.
...
- 151k
6
votes
1
answer
900
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
3
votes
0
answers
142
views
Dimension of convex arrangements for hypergraphs
Suppose you have a hypergraph H on n vertices. Let d be the smallest integer such that we can find an arrangement A of convex subsets in Rd so that H represent the intersections of sets in A.
Has ...
- 4,586
15
votes
2
answers
1k
views
When does graph minor containment imply subgraph containment?
Consider a path of length 3. Any graph G which contains this graph as a minor must also contain it as a subgraph. For paths of any length this is easy to prove.
In general this happens for any graph ...
- 1,332
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