All Questions
Tagged with reference-request graph-theory
453 questions
5
votes
1
answer
537
views
Which hyperbolic tilings are Cayley graphs?
I realise the question is easy but after asking to a few people (and never getting a clear answer), I thought it could be instructive to ask it here:
Given a regular tiling of the hyperbolic plane is ...
- 4,432
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
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
5
votes
1
answer
196
views
Hadwiger number of a graph: Question about the original article from 1943
I am analyzing Hadwiger's original article (Hadwiger, Hugo (1943), "Uber eine Klassifikation der Streckenkomplexe", Vierteljschr. Naturforsch. Ges. Zurich, 88: 133–143) for my work related ...
5
votes
1
answer
375
views
Dense graphs where every maximal independent set is large
A maximal independent set of a graph $G$ is a subset of vertices $S$ such that each vertex of $G$ is either in $S$ or adjacent to some vertex in $S$, and no two vertices in $S$ are adjacent. Consider ...
- 135
5
votes
1
answer
119
views
Existence of regular factors in dense graphs
All graphs here are finite and simple.
A $d$-factor of a graph is a spanning regular subgraph of degree $d$.
Where can I find theorems of this nature, for constants $a,b,c\gt 0$: If $G$ is a graph ...
- 37.7k
5
votes
2
answers
474
views
Another graph characteristic
This question concerns a method of drawing graphs and a graph characteristic about which I want to learn more.
Consider a connected directed graph with at least one node with in-degree 0 and one node ...
- 9,720
5
votes
1
answer
423
views
The minimum number of Hamiltonian paths in a strongly connected tournament of order $n$
For $n\ge3$ let $a(n)$ be the minimum number of Hamiltonian paths in a strong (i.e., strongly connected) tournament of order $n.$
Where is $a(n)$ discussed in the literature? Is the exact value ...
- 13.4k
5
votes
1
answer
183
views
Resource Constrained Routing with Refueling
What are good algorithms (resp. models) for calculating optimal or near optimal routes while taking into account fuel consumption, options for refueling and, limited tank capacity?
Especially modeling ...
- 13.2k
5
votes
2
answers
383
views
Extremal graph theory for directed graphs
In extremal graph theory, there are results such as
$$t(C_4,G)\geq t(K_2,G)^4,$$
where $G$ is an undirected graph, $C_4$ is a cycle graph on 4 nodes, $K_2$ is a complete graph of $2$ nodes, and $t(\...
- 131
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
5
votes
1
answer
788
views
Deleting triangles in a graph
I'm sure it is well-known how many edges you must delete in a (highly linked) graph to destroy all cycles. Is it also known how many edges you must delete to destroy only all triangles? And even, how ...
- 4,829
5
votes
1
answer
281
views
Transfer-impedance matrix for edge correlations in random spanning tree
Suppose $G$ is a (weighted) connected graph and
let $T$ denote a random spanning tree of $G$,
chosen uniformly (or respecting the edge weights).
It is known that for any distinct edges $e, f$
$$\...
- 2,175
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
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
5
votes
1
answer
107
views
Maximal graphs with a property that is invariant w.r.t. vertex removal
Let $P$ be a property of graphs such that if a graph $G$ has $P$, then any graph obtained from $G$ by removal of a vertex also has $P$.
Let $g(n)$ be the maximum size of a graph of order $n$ having $P$...
- 34.3k
5
votes
1
answer
349
views
Ear decompositions and spanning trees
I am looking for a reference for the following theorem:
Theorem: Let $G$ be a 2-connected, simple, undirected graph, and let $T$ be a spanning tree. Then $G$ has an ear decomposition in which every ...
- 1,500
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
384
views
Flow of an integer
I've stumbled across this family of flow networks, and posted the sequence of maximal flows to OEIS: A238729. I can't find any reference to it either. Has anyone seen it?
Here is the description:
...
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
5
votes
0
answers
141
views
If chromatic polynomials for two graphs agree, can I always find an edge such that the two deletion-contraction minors have same chromatic polynomial?
Suppose I have non-isomorphic graphs $G$ and $H$ (which have at least one edge), but such that their chromatic polynomials are the same. Can I then always find an edge $e$ in $G$ and $f$ in $H$ such ...
- 15.8k
5
votes
0
answers
121
views
The Smith decomposition of the graph Laplacian and Locality
Let $X$ be a graph. Let $V(X)$ and $E(X)$ be the sets of vertices and edges of the graph respectively. If $f:V(X) \rightarrow G$ where $G$ is an abelian group, then one can define a graph Laplacian as ...
- 51
5
votes
0
answers
231
views
Schröder and graphical logic?
I was actually surprised by a comment by John Baez over at the n-Category Cafe about his surprise that Ernst Schröder, a mathematician of whom he had known through Schröder's work on mathematical ...
- 10.5k
5
votes
0
answers
102
views
An upper bound on the minimum number of vertices in a girth 5 graph of chromatic number $k$
Is there a known upper bound on the minimum number of vertices in a graph with girth 5 and chromatic number $k$? Could you also give references for this?
- 51
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
0
answers
308
views
Distance on Markov-chains/graphs and discrete Ricci-flow
I am trying to know if there is a notion of "distance" or pseudo-metric between markov-chains or graphs.
For the purpose of the question, the graph is weighted, and can be considered as labelled, so ...
- 51
5
votes
0
answers
158
views
Does this geometric graph have a name?
Along some geometrical speculations, I came across a graph $\Gamma$ defined as follows:
Let $S$ be the set of vertices of a regular $n$-gon. Then the "vertices" of
$\Gamma$ are the nonempty subsets ...
- 101
5
votes
0
answers
136
views
What's the variance in the Six Degrees model?
Recall the six degrees of Kevin Bacon game. You can even play the game at The Oracle of Bacon, and their search works via Breadth First Search.
I interpret the punchline as saying that if I start ...
- 30.3k
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
4
votes
2
answers
287
views
Triangle-free labeled graphs
The number of connected labeled graphs with $n$ edges and $n$ nodes are listed in OEIS A057500.
I suspect the following must be known but I can't find a reference to it.
Question. How many among ...
- 43.2k
4
votes
3
answers
2k
views
Term for "Directed acyclic graph with exactly one sink and one source"
There's a theorem/lemma that states that a finite directed acyclic graph (DAG) has at least one sink and at least one source. Is there a term for a (finite) DAG with exactly one sink and one source?
...
- 2,235
4
votes
2
answers
933
views
Is there any nontrivial monad on the category of graphs?
The question is in the title, but let me specify what I mean by the category of graphs.
In the context of this question, the category of graphs is the category of symmetric irreflexive relations. ...
- 327
4
votes
3
answers
356
views
reference request: voltage in a resistor network is a unique harmonic function
An undirected graph may be regarded as a resistor network where each edge corresponds to a resistor of unit resistance. This paper covers such an approach.
On electric resistances for distance-...
- 419
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
4
votes
1
answer
4k
views
exact definition of Fiedler vector
For a given N-vertex similarity graph $ G=(V,A) $ the eigenvalues of the unrenormalized (graph) Laplacian may be denoted as
$$ 0= \mu_0 \leq \mu_1 \leq ... \leq \mu_N $$
where the corresponding ...
- 253
4
votes
1
answer
339
views
Vertex-connectivity of connected, vertex-transitive graphs without $K_4$ is maximum possible
A graph is said to have optimal vertex connectivity if its vertex connectivity equals its minimum degree. According to this arXiv preprint, it was shown by Mader in (Arch. Math., 1970) and (Math. Ann.,...
- 406
4
votes
2
answers
297
views
What is the standard name of an edge-graph
Given a graph $G=(E,V)$, I construct a graph $G'$ where the vertices of $G'$ are given by the edges of $G$ and say that two edges of $G$ are neighbors in $G'$ if they have a common vertex.
Is there a ...
- 71
4
votes
1
answer
224
views
Graph presentation of Lexicographic shifts
Consider a finite alphabet $\{0,1, \ldots, n-1\}$. Let $\Sigma_n = \mathop{\prod}\limits_{j=1}^{\infty}\{0, \ldots n-1\}$ be the set of infinite one sided sequences and $\prec$ the lexicographic ...
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
4
votes
1
answer
222
views
Double cover the edges of a complete graph by smaller complete graphs
Suppose we have a complete graph $K_n$ on $n$ vertices. Are there any results on the ways to cover $K_n$ with $k$ copies of $K_m$, for $m<n$, such that each edge of $K_n$ is contained in exactly ...
- 43
4
votes
1
answer
152
views
Method to construct a bipartite graph G' with 2n vertices from a graph G
I have seen mentioned in a talk an operation that takes a graph $G=(V,E)$ and constructs a new bipartite graph $G'=(V',E')$ such that $V' = V\times \{0,1\}$ and $E'=\{((i,1),(j,0)) : (i,j)\in E\} \cup ...
- 20.2k
4
votes
2
answers
2k
views
The number of monochromatic triangles
It is well known that the minimum number of monochromatic triangles in a red/blue coloring of the edges of the complete graph $K_n$ is given by Goodman's formula
$$M(n)=\binom n3-\left\lfloor\frac n2\...
- 13.4k
4
votes
2
answers
237
views
Tournament contained in vertex transitive tournament
Is it true that every finite tournament is contained in some finite vertex-transitive tournament? If not, is it known which tournaments satisfy this property? This seems like a basic question, but I ...
- 41
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
1
answer
243
views
Do right-profiles determine graphs up to isomorphism?
For graphs $G$ and $H$, let $h(G,H)$ denote the number of graph homomorphisms from $G$ to $H$.
Fix some enumeration $G_1,G_2,\ldots$ of (isomorphism classes of) the set $\mathbf{D}$ of finite graphs, ...
- 2,350
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
4
votes
2
answers
237
views
Reference request for differential graph theory
Disclaimer: This question was initially asked yesterday in Mathematics Stack Exchange but left unanswered there.
I am interested in learning about differential graph theory or differential operators ...
4
votes
1
answer
553
views
Product of vertex degrees of an edge in a planar graph
Let $G$ be a planar graph, which we may assume to be a triangulation, with vertex set $V$ and edge set $E$. Suppose the minimum vertex degree is at least 3, and suppose any two distinct edges share at ...
- 565
4
votes
1
answer
267
views
Counting trees according to endpoints
Question: Is there a nice (or any) formula for the generating function
$$T(x,y) = \sum_{m,n} t_{m,n} x^my^n,$$
where $t_{m,n}$ is the number of trees with $m$ vertices and $n$ endpoints?
...
- 1,411
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