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
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:
...
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
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
-2
votes
1
answer
202
views
Natural constructions (not depending on parameters) [closed]
Consider graph clusterings as a prototypical example of (logical) constructions.
Let a clustering of a graph $(V,E)$ be any covering of $V$, i.e. a set $C$ with $\bigcup C = V$.
I am looking for a ...
- 9,720
1
vote
0
answers
42
views
Harmonic Bergman spaces on graphs
Harmonic Bergman spaces on Euclidean domains are a set of harmonic functions on a domain that are from $L^{p}$ of that domain. I tried to find something on harmonic Bergman spaces on graphs because we ...
- 325
3
votes
2
answers
1k
views
A structure of the group of automorphisms of an infinite binary tree
My friend asked me to ask his question here. Where he can find (a paper or a book) containing a complete description (with the proof) of a structure of the group of automorphisms of an infinite binary ...
- 5,409
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
3
votes
1
answer
220
views
Have chordal outerplanar graphs been studied before?
Recall a graph is chordal if it contains no induced cycle of length 4 or more, and outerplanar if it has a crossing-free embedding in the plane such that all vertices are on the same face. While ...
- 717
8
votes
2
answers
377
views
A family of skew-symmetric matrices corresponding to cycles in graphs
When investigating loops in Markov chains I ran into the following observation.
A cycle in a graph $G$ with $n$ vertices may be represented by a matrix $\Gamma \in \mathbb R^{n \times n}$ having the ...
- 985
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
2
votes
1
answer
227
views
Is this Graph parameter known?
Let $\lambda(G)$ denote the edge-connectivity of $G$.
Consider the following parameter:
$\rho(G) = \max_{X \subset V(G)} \min(\lambda(G[X]), \lambda(G[V(G) - X]))$
Has this parameter been studied? ...
- 1,034
0
votes
0
answers
107
views
Maximum Independent set of sparse graphs with few triangles
Notations used
$\alpha(G) = $ Max sized independent set of graph $G$.
$n(G) = $ Number of vertex in graph $G$.
Theorem (by Ajtai et al.): For a triangle-free graph $G$ and max degree being $\Delta$,...
- 189
1
vote
0
answers
64
views
Complexity of in-dominating set
Is the decision problem In-Dominating Set NP-complete for digraphs of regular out-degree (greater than $\frac{n-2}{4}$, in particular)? --
I'm mainly looking for a reference.
Thanks for any answer!
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
4
votes
1
answer
696
views
Is there a graph-theoretical proof of Tutte's theorem on matroids?
First of all, I'm not a mathematician and I hope this question isn't too elementary, but I got no answers on math.SE, and since this is a reference request on a relatively advanced theorem, I thought ...
- 623
1
vote
0
answers
611
views
Is the automorphism group of a homogeneous (locally finite) tree unimodular?
I have seen somewhere (that I don't remember now) that the (full) automorphism group of a k-regular tree is unimodular. I assume a k-regular tree is the same thing as the homogeneous tree of degree k (...
user23860
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
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
3
votes
0
answers
135
views
Groups acting on non-locally-finite trees with independence and specified local actions
Suppose I have a biregular tree $T_{m, n}$ (not necessarily locally finite), with distinct cardinal numbers $m, n$, so Aut$(T_{m, n})$ acts on $T_{m, n}$ without inversion. Let $V_m$ be those vertices ...
- 313
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
2
votes
3
answers
184
views
Reference Request for: Finding Large Bipartite Subgraphs via Destruction of Odd Cycles in Graphs
From the observation, that a bipartite graph doesn't contain odd cycles, it would seem natural to attempt to destroy all odd cycles in the most efficient way, by either removing edges or vertices of ...
- 13.2k
4
votes
1
answer
503
views
For what classes of comparability graphs are their complements also comparability graphs?
An interval graph is an intersection graph of real intervals, that is, an undirected graph whose vertices can be labeled with real intervals so that there is an edge between two vertices iff their ...
- 43
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
7
votes
2
answers
533
views
Recovering a Weighted Graph from Shortest Path Distances
I am interested in the following problem (A) and its related formulation (B).
(A) Suppose that $G = (V,E,w)$ is an unknown weighted graph on the vertex set $V$ and that one has access to $d_G(v,v'), \...
- 168
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
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
8
votes
2
answers
669
views
Fractional chromatic number, find reference to a particular alternate definition for
I'm searching for a reference to a particular alternate definition of the fractional chromatic number of graphs.
Let me review the most common definition and basic properties first.
Let $ G $ be ...
- 1,944
-1
votes
1
answer
148
views
Intersection graphs of 2-element subsets
I am interested in the intersection graphs of $\binom{X}{2}$, i.e. the set of all 2-element subsets of a (finite) set $X$.
[Motivation: One can represent every simple graph with $n$ vertices by an ...
- 9,720
4
votes
0
answers
128
views
Metrized categories
Motivation: Let $\Gamma = (V,E)$ be a directed graph. To each edge $e \in E$, choose a value $\kappa^e \in \mathbb R$, representing the cost of transporting one unit of "stuff" through the edge. Let $\...
- 8,512
2
votes
0
answers
1k
views
Incremental minimum spanning tree
Given a connected graph $G=(V,E)$ with a weight function $w:E\to\mathbb{R}$ and a subset $E_0\subseteq E$ such that the subgraph $(V,E_0)$ is connected, I am looking for a sequence $E_0\subseteq E_1\...
- 2,966
13
votes
1
answer
933
views
Drawings of complete graphs with $Z(n)$ crossings
Hill conjectured that the minimum number of crossings in a drawing of the complete graph $K_n$ in the plane is exactly
$$Z(n) = \frac{1}{4} \bigg\lfloor\frac{n}{2}\bigg\rfloor \left\lfloor\frac{n-1}{...
- 6,101
7
votes
2
answers
851
views
Deriving Konig's Lemma directly from Infinite Ramsey's Theorem for triples
Let KL denote König's Lemma (for trees over $\mathbb{N}$), and RT(3) denote the
Infinite Ramsey Theorem for triples over $\mathbb{N}$ (notation as in Simpson's
book Subsystems of second order ...
- 205
12
votes
4
answers
1k
views
How dense is the set of asymmetric graphs?
On $n$ nodes, we have $2^{n(n-1)/2}$ graphs. Asymmetric graph is a graph that has only trivial automorphism. We known that asymptotically almost all finite graphs are asymmetric. Therefore, in the ...
- 2,993
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
1
vote
0
answers
372
views
counting k-cliques not also (k+1) on random graphs
consider the set of graphs with $n$ vertices and exactly half of all $\binom n 2$ possible edges.
looking for a formula that counts the number of these graphs that have a $k$-clique but not a $(k+...
- 529
12
votes
3
answers
552
views
Estimate on currents in Cayley graphs
Take a Cayley graph $\Gamma$ (thought of as an electrical network with all edges having equal resistance) and break one edge $e$ and put a battery there. (Assume the graph has only one end* so that ...
- 4,432
1
vote
1
answer
281
views
complexity of dominating sets of regular graphs
Hi,
I believe it is just an easy question, but I have not found the answer: Is the optimization / decision problem DOMINATING SET NP-complete when restricted to regular graphs? Where can I find a ...
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
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
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
0
votes
2
answers
871
views
Reference for "almost all graphs have diameter 2"
The property in the title is well-known. I am trying to find an original reference to its first appearance in print. The 4th edition of Graphs & Digraphs by Chartrand and Lesniak lists this as ...
- 6,962
0
votes
1
answer
61
views
Reduction of $f$-solubility to $1$-factor
This has been put in math.SE for a while without any responses.
Given $G$ and an $f:V(G)\to{\Bbb N}$, there exists a graph $G_f$ such that $G$ is $f$-soluble if and only if $G_f$ has a $1$-factor.
...
user14319
2
votes
1
answer
138
views
(Heuristic for) Partitioning n-partite weighted graphs into bounded n-cliques
Consider a complete $N$-partite graph $X$ with $X_n$ denoting the $n$-th vertex bin for $1 \leq n \leq N$, where we may assume that each $X_n$ has $k$ vertices for some universal constant $k$. Assume ...
- 249
3
votes
1
answer
1k
views
Dual (/reduction?) graph of a curve
This might be a bit of a broad question, or maybe even questions.
Recently I have learned about the connection between algebraic geometry and graph theory, via the dual graph of a curve. I have also ...
- 5,504
0
votes
2
answers
331
views
Hypergraph cartesian join operation (over same vertex set)
Consider two hypergraphs $H_1 = (V, \mathscr{E}_1), H_2 = (V, \mathscr{E}_2)$ over the same vertex set $V$. am interested in what could be called a "cartesian join" operation building a new ...
- 529
0
votes
0
answers
71
views
products/factoring of two hypergraphs with same vertex set?
all the basic products for graphs have been extended to hypergraphs[1].
is there a concept of a product of hypergraphs with the same vertex set? has this been studied?
normally the hypergraph ...
- 529
0
votes
0
answers
188
views
Conjugate subgraphs and (maybe) a generalized Burnside's lemma?
It's rather straightforward, I guess, to define conjugate subgraphs of a graph via its conjugate nodes. (Two nodes $x,y$ are conjugate when there is an automorphism $g$ such that $x = g(y)$.)
...
- 9,720
4
votes
1
answer
508
views
Graph Theory: 2012 ARML Power Question - references?
The definition of the Workday Number of a finite graph is given on page 14 in http://www.arml.com/2012_contest/2012_Contest_Final_Version.pdf and the rest of the problem statement is given at the top ...
- 43
4
votes
2
answers
2k
views
Regular graph colorings
[Since I didn't get any feedback at MSE, I dare to post this question here, too.]
Call a coloring $C:V(G) \rightarrow \lbrace 1,\dots,n \rbrace$ of a graph $G$ regular when every vertex with color $...
- 9,720