All Questions
Tagged with reference-request graph-theory
453 questions
1
vote
0
answers
54
views
Beck-Fiala Discrepency Type Results for Arbitrary Graph Labelings
Suppose we have a graph $G$ on $n$ vertices $x_1 , \dots, x_n$ attached with weights of values from $1$ to $n$. We will write $\text{weight}(x_i)$ as simply $x_i$ and let $\text{diff}(G) = \min _{(x_i,...
- 139
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
3
votes
1
answer
598
views
Asymptotic formula for the number of connected graphs
It can be shown that the set of graphs with $N$ vertices $G_N$ has cardinality:
\begin{equation}
\lvert G_N \rvert = 2^{N \choose 2} \tag{1}
\end{equation}
Recently, I wondered how much bigger $\...
- 3,871
1
vote
1
answer
76
views
Shortest path on graphs
I would like to now if there has been any work on related problems, that is, shortest path problem in dynamically evolving graphs.
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
4
votes
1
answer
218
views
Most adequate software for proof checking graph theory proofs
What might be the best software for checking the validity of proofs of graph theoretical statements? Lean, HOL, ... ? One criterion would also be, what would be the easiest for a graph theorist to ...
- 1,018
1
vote
2
answers
116
views
How to use probability to find a matching in a family of graphs?
In a conference, I heard that we can use some probabilistic methods to find a matching in some kind of graphs. I would like to see some examples of such technics. Can someone provide some references ...
- 57
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
3
votes
1
answer
495
views
Ear decomposition with initial cycle
It is known that a graph is 2-vertex-connected iff it has an (open) ear decomposition, and there is a linear-time algorithm for finding an ear decomposition.
I think it is also true that if a graph ...
- 137
0
votes
1
answer
84
views
Primage structures: induced domain partitioning by itterated inverse (reference request)
I am studying the list of inverse images (preimage sets) of some function $f$ at a given inverse depth $j$ -- for each element $x_i$ of a finite domain $X$.
For example, the j-th such preimage list ...
- 23
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
1
vote
0
answers
40
views
Reference on graphs such that contracting 2 non-adjacent vertices increases the Hadwiger number
Suppose $G=(V,E)$ is a finite simple graph. Let $h(G)$ denote the Hadwiger number, that is, the maximum $n\in\mathbb{N}$ such that $K_n$ is a minor of $G$.
We say that a finite, simple, undirected ...
- 48.9k
1
vote
1
answer
393
views
Hyperbolic embedding of a directed acyclic graph defined over strings
For integer $n$ and alphabet $\Sigma$ we construct a DAG (directed acyclic graph) $G=(V,E)$ over strings $s\in\Sigma^\star$ as follows:
$$V = \{s\in\Sigma^\star\colon |s|\le n\}$$
$$E = \{(s_1,s_2)\...
- 187
2
votes
0
answers
55
views
Reference request: $n$-edge-coloring bipartite graph $K_{n,n}$ such that monochromatic parts are isomorphic
I am finding references for the following problem:
We call a $n\times n$ 0-1 matrix permutation if there are exactly one $1$ in each row/column.
Suppose $A$ is a 0-1 matrix of size $n\times n$ in ...
- 1,551
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
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 ...
- 19k
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
0
votes
0
answers
87
views
Necessary Conditions for a Graph not possible to Rainbow Color?
Suppose we have a $t$-uniform hypergraph ($t \ge 3$) $G$, and have $t$ colors available. A question in my research is equivalent to asking what the necessary and sufficient conditions are on $G$ for ...
- 103
9
votes
2
answers
505
views
Moore graphs and finite projective geometry
In a comment on a blog post from 2009 about the hypothetical Moore graph(s) of degree 57 and girth 5, Gordon Royle offered the following observation (reproduced here in full for the sake of ...
- 1,645
1
vote
1
answer
94
views
What is the expected distance between the sides of a random subgraph of the grid?
Let $G$ be the $n \times n$ grid, in which each vertex is connected to the vertices above it, below it and on either side. Let $G_p$ be the random subgraph of $G$ obtained by keeping each edge with ...
- 1,643
3
votes
0
answers
114
views
Reference Request: simple graph vertex labelings with balanced induced edge weights
Say that the edge weight induced by a vertex labeling is the sum of the weights of the two vertices comprising it. Here is the problem of interest: given a simple $d$-regular graph $G = (V,E)$, find a ...
- 81
2
votes
0
answers
30
views
Graph vertex label dynamics, statistical model reference request
I am modeling some type of social interaction, and came up with the following natural question.
Let $K_n$ be the complete graph on $n$ vertices, with some initial edge labeling in some alphabet $A$.
...
- 15.8k
7
votes
2
answers
415
views
Graph which do not satisfy a pseudo-Poincaré inequality
Say that an infinite (connected) graph (with vertices of bounded degree) satisfies a $\ell_1$-pseudo-Poincaré inequality if there is a constant $C>0$ so that for any $n \in \mathbb{N}$ for any ...
- 4,432
8
votes
1
answer
214
views
What is known about graphs that permit only one colouring?
Some graphs ($K_n$ or $K_n$ minus any one edge, for instance) only permit one minimal colouring up to different labels of the colours. Is there anything known about these kind of graphs? I can think ...
- 349
13
votes
2
answers
749
views
Is there a version of Weyl's law for graph Laplacians?
Is there a version of Weyl's law or a local Weyl's law for eigenvectors of the graph Laplacian?
For some context, a colleague in statistics has encountered eigenvectors of the Laplacian for certain ...
- 6,001
2
votes
0
answers
58
views
Flat or linkless embeddings of graph with fixed projection
The problem of finding whether a given planar diagram of a graph, with over- and under-crossings, is a linkless embedding or not has unknown complexity (Kawarabayashi et al., 2010). My first question ...
- 221
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
4
votes
0
answers
109
views
Reference on generalization of plane graph duality between bonds and simple cycles
Let $G$ be a plane graph, and $G^*$ its dual. Among the $k$ partitions of the nodes of $G$, I'll call the connected k-partitions those such that each block of nodes of the partition induces a ...
- 1,462
12
votes
1
answer
424
views
Quantitatively characterizing the failure of the converse of Dirac's theorem
First, I am an undergraduate so I apologize if this is trivial and certainly understand if it is closed immediately.
I am currently in a combinatorics and graph theory class and recently we have ...
- 221
1
vote
0
answers
119
views
Tight upper and lower bounds for unbalanced left-regular expander graphs
I am interested in finding the best expansion parameters for unbalanced left-regular expander graphs.
Specifically, fix $\delta\in(0,1/2)$, and a positive integer $d$. Let us call a bipartite graph $\...
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
2
votes
0
answers
59
views
Weak convexity in graphs
I asked the following question in MathStackExchange, but I did not get any answer, and I think that this might be the appropriate venue for the question.
As we know, a finite undirected graph ...
- 123
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
8
votes
0
answers
1k
views
$R(3,6) = 18$, especially proving that $R(3,6)>17$
I'm studying the Ramsey numbers, especially $R(3,6) = 18$
I understand that the proof using the theorem $R(m,n) <R(m-1,n)+R(m,n-1)$ can only prove that $R(3,6)<20$. However by Cariolaro's "On ...
- 181
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
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
4
votes
0
answers
236
views
Groups inducing edge-colorings on graphs. Is this concept known?
Are the following concepts known in graph/group theory, and if Yes, what are they called and where to read about them? Because I do not know better, I gave them placeholder names for now.
1. ...
- 13.6k
10
votes
1
answer
526
views
Maximum number of triangles no two of which have a common edge
For $n\in N_+$, define $f(n)$ to be the maximum number of triangles in a graph $G$ with $n$ vertices, taken over all $n$-vertex graphs having the property where no two triangles have a common edge.
Do ...
- 475
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
7
votes
1
answer
210
views
Grinberg's uniquely hamiltonian 3-connected graphs (Russian paper)
Many years ago, Grinberg found some uniquely-hamiltonian $3$-connected graphs, and published his results in a paper that has been cited several times as follows.
E. Grinberg, Three-connected graphs ...
- 12.7k
1
vote
0
answers
93
views
Percolation and diameter of graph
Is the critical probability in percolation and diameter of graph related. I guess larger the diameter higher the probability. Is there any result like this?
By critical probability I mean the ...
0
votes
1
answer
62
views
Standard names of two finitary properties of hypergraphs?
Now we are writing a paper on minimal covers and minimal vertex-covers in hypergraphs and would like to know if there are any standard names for the following two (dual) properties of a hypergraph $(V,...
- 41.9k
1
vote
0
answers
81
views
Matchings in infinite, not necessarily bipartite, graphs
Aharoni, Nash-Williams, and Shelah have extended the famous marriage theorem for finite bipartite graphs due to Hall to arbitrary graphs.
Is there a similar generalization of Tutte's theorem on ...
- 48.9k
2
votes
2
answers
312
views
Random walk and isoperimetric constant
I assume that a result of the following kind is known, and I would really appreciate a reference for it... Or at least, some hints as to where to start looking.
Theorem(?): Let $\varepsilon>0$ ...
- 11.2k
37
votes
2
answers
4k
views
How to find Erdős' treasure trove?
The renowned mathematician, Paul Erdős, has published more than 1500 papers in various branches of mathematics including discrete mathematics, graph theory, number theory, mathematical analysis, ...
3
votes
0
answers
106
views
Reference request: Bipartite symmetric graphs are hamiltonian
Does anyone know whether bipartite symmetric graphs are hamiltonian?
I'm not sure whether anyone have proved it before, but a nonhamiltonian symmetric bipartite graph would lead to a counterexample to ...
- 9,501
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. ...
1
vote
0
answers
47
views
Family of rooted trees parameterized by binary sequences
Let $A=\{1,2\}$. For any $d \in A$ and any sequence $a=(a_1,a_2,\dots)\in A^{\mathbb N}$ the associated rooted tree $T(d,a)$ is recursively defined in the following way. The degree of the root of $T(d,...
- 17k
8
votes
3
answers
779
views
Computer program for counting graph homomorphisms
I would like to ask is there a computer program for counting graph homomorphisms?
- 4,826
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