**1**

vote

**0**answers

157 views

### Threshold for perfect Matchings in Bipartite graph

Consider the random bipartite graph with vertex classes of size $n$ and each edge being present independently with probability $p(n)$.
I know one way to prove the threshold of a perfect matching is ...

**4**

votes

**1**answer

149 views

### Structure of the stabilizer of a vertex-neighborhood of a vertex-transitive graph

Given a simple, undirected graph and a vertex $v$ of the graph, let $L_v$ denote the set of automorphisms of the graph that fixes the vertex $v$ and each of its neighbors. When the graph is ...

**0**

votes

**0**answers

64 views

### Covering a set in a hypergraph

I'm interested in counting the following. Consider a set $\{v_1,\dots,v_m\}$ of $m$ vertices in the complete $k$-uniform hypergraph on $n$ vertices where $m < k$. I want to know the number of ...

**0**

votes

**0**answers

67 views

### Parallelism degree of a DAG

Let me first give a motivation. Suppose a connected DAG G with one source X and one sink Y. The goal is to find some "bottleneck" node between X and Y, i.e. node through which every path from X to Y ...

**1**

vote

**1**answer

70 views

### Spectral radius of a time-varying matrix with strictly positive increment of the matrix's entry

Consider a time varying non-negative matrix $A(t)$ and its spectral radius $\rho(A(t))$ being the largest eigenvalue of $A(t)$ and $t$ denotes the time. If $A(t)$ changes over time with each time a ...

**18**

votes

**5**answers

1k 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)?

**10**

votes

**2**answers

693 views

### What is a “Ramanujan Graph”?

I noticed an apparent conflict in the definition in literature about what is a "Ramanujan graph, which I was wondering if someone could kindly clarify.
(1)
The Hoory-Linial-Wigderson review on ...

**10**

votes

**1**answer

248 views

### Are there non-trivial graphs that uniquely embed to hypercubes?

The $n$-dimensional hypercube is the graph formed by $0$-$1$ sequences of length $n$ where two vertices are adjacent if they differ at only one place.
The weight of a sequence is the number of $1$'s ...

**2**

votes

**2**answers

200 views

### Removing subtrees

Let $T$ be a complete infinite rooted binary tree. Is it possible to remove (infinitely many) subtrees of $T$ and get a subgraph $G$ such that:
$G$ has no complete subtrees (the graph below any ...

**4**

votes

**1**answer

199 views

### Prime labelling of graphs

A prime labeling of a graph is an injective function $f: V(G) \to \{1, 2, ..., |V(G)|\}$
such that for every pair of adjacent vertices $u$ and $v$, $\text{gcd}(f(u), f(v)) = 1$ (labels of any two ...

**2**

votes

**1**answer

114 views

### How to construct a graph with arbitrarily large girth and large chromatic number? [closed]

Erdos theorem says it is possible and it is not so easy. What is the general procedure to construct graphs like Grötzsch graph?

**0**

votes

**0**answers

17 views

### Looking to derive bound for modulus of harmonic eigenfunction on weighted graph

We have a homogeneous graph $G = (V,E)$ with a function $f:V\rightarrow \mathbb{R}$. We define the following modulus:
$\displaystyle \omega(s) = \sup\{f(x)-f(y) \ | \ |x-y|=s \}$
and wish to lower ...

**5**

votes

**1**answer

162 views

### Algorithm to minimally connect line segments in Euclidean plane

Suppose you have finitely many line segments in the Euclidean plane. How do you "connect them to form one chain of line segments of minimal length?"
More formally and generally, what I'm looking for ...

**2**

votes

**0**answers

47 views

### finding dominating cycles in $2K_2$-free graphs

A cycle $C$ in a connected graph $G$ is called dominating if its complement $V(G)-V(C)$ is an independent set. H.J. Veldman proved in 1983 (Disc. Math. v.43, 281-96) a general result that in ...

**4**

votes

**1**answer

256 views

### Endomorphisms and almost all graphs

Is it known what fraction (almost all?) of graphs have a trivial endomorphism monoid? I can't seem to find any reference to the question. Maybe it's related to the question: what fraction of graphs ...

**1**

vote

**0**answers

58 views

### Is there an elliptic Harnack equality for directed graphs?

The elliptic Harnack inequality for undirected graphs was proven by Delmotte in the paper "Inegalite de Harnack elliptique sur les graphes" (French, ...

**4**

votes

**1**answer

108 views

### Determining the number of hamiltonian paths of $K_n-C_n$

I would like to know information regarding the function $h(n)$ where $h(n)$ is the number of hamiltonian cycles the graph $K_n$ has after removing the edges that make up a hamiltonian cycle of $K_n$. ...

**2**

votes

**1**answer

177 views

### Edge density of triangle-free graphs

Let $G$ be a finite, simple, loopless graph with $|V(G)|=n$. We define its edge density as $$ed(G) := \frac{|E(G)|}{n \choose 2}.$$
Moreover we set $$d_n := \text{max}\big\{ed(G): G \text{ is a ...

**1**

vote

**0**answers

41 views

### Rate of convergence of graph-theoretic quantity to fractional graph-theoretic counterpart

Let $G^n$ denote the OR product of a graph with itself $n$ times, i.e. the graph which has an edge between distinct vertices $(v_1,v_2,\ldots,v_n)$ and $(u_1,u_2,\ldots,u_n)$ if there exists some $i$ ...

**7**

votes

**1**answer

170 views

### Universal graph homomorphisms

By a graph I mean a pair $G = (V, E)$ where $V$ is a set and $E \subseteq \mathcal{P}_2(V) := \{\{a,b\}: a\neq b \in V\}$. A graph homomorphism between graphs $G, H$ is a map $f:V(G)\to V(H)$ such ...

**17**

votes

**1**answer

299 views

### Lens spaces and generalized Petersen graphs

Recently I came across this mathoverflow question, in which the number of homeomorphism classes of 3-dimensional lens spaces $L(p, q)$ is computed as a function of $p$. Using the OEIS, I found a ...

**10**

votes

**1**answer

380 views

### Cauchy-Schwarz proof of Sidorenko for 3-edge path (Blakley-Roy inequality)

Is there a "Cauchy-Schwarz proof" of the following inequality?
Theorem. Given $f \colon [0,1]^2 \to [0,1]$, one has
$$
\int_{[0,1]^4} f(x,y)f(z,y)f(z,w) \, dxdydzdw \geq \left(\int_{[0,1]^2} f(x,y) ...

**1**

vote

**2**answers

165 views

### Proving a random bipartite graph contains a perfect matching

I have the following problem
consider a random bipartite with vertex classes $A$ and $B$ of size $|A|=|B|=\mathrm{log}^{2}(n)$ graph in which every possible edge is chosen independently with ...

**31**

votes

**9**answers

3k views

### Generalizations of the Four-Color theorem

The four color theorem asserts that every planar graph can be properly colored by four colors.
The purpose of this question is to collect generalizations and strengthenings of the four color theorem ...

**6**

votes

**1**answer

247 views

### Do perfect matching(s) have signatures in the graph eigenvalues?

If the edges of a bipartite graph are such that they can be seen as a disjoint union of perfect matchings then will this somehow reflect in the eigenvalues of the Laplacian?
It would be helpful to ...

**0**

votes

**0**answers

58 views

### Computation on Random Bipartite graphs

I'm looking at a random bipartite graph $K_{\omega(n)}*K_{\omega(n)}$ where $\mathrm{log}(n)\leq \omega(n) \leq n^{1/2}$, in which each of the $\omega(n)^{2}$ edges is placed randomly with probability ...

**3**

votes

**1**answer

59 views

### Minor ordering for finite graphs

Let $\mathcal{G}_{<\omega}$ be the set of graphs $G = (V,E)$ such that $V = \{0,\ldots,n\}$ for some $n \geq 0$ and $E \subseteq \mathcal{P}_2(V) = \{\{a,b\} : a,b \in V \textrm{ and } a\neq b\}$. ...

**1**

vote

**0**answers

64 views

### Matchings in random bipartite graphs

I was wondering if anyone could point me in the direction of a text or paper which would help deal with the following problem
Suppose i am given a $K_{\mathrm{log}(n)} \times K_{\mathrm{log}(n)}$ ...

**4**

votes

**2**answers

138 views

### Graphs whose degree vectors coincide for all powers of their adjacency matrices

Let symmetric $A,B \in \{0, 1\}^{n \times n}$ denote the adjacency matrices of two simple graphs. Further let $\mathbf{1}$ denote the all-one-vector.
Now assume that $A^k \mathbf{1} = B^k \mathbf{1}$ ...

**0**

votes

**1**answer

76 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 ...

**2**

votes

**2**answers

151 views

### “Homomorphism fingerprint” for graphs

Let $G, H$ be simple, undirected graphs without loops. We say that $G, H$ have the same homomorphism fingerprint if $|\text{Hom}(X, G)| = |\text{Hom}(X, H)|$ for all graphs $X$. (By graph ...

**3**

votes

**0**answers

99 views

### Cores of infinite graphs

Let $\kappa$ be a cardinal and let $\textrm{Grph}(\kappa)$ be the set of graphs $G = (V,E)$ such that $V \subseteq \kappa$ and $E \subseteq \mathcal{P}_2(V) := \{\{a,b\} \subseteq V: a\neq b\}$.
We ...

**4**

votes

**1**answer

156 views

### What can be said about graphs if there are homomorphisms in both directions?

Let $G,H$ be simple undirected graphs without loops such that there are graph homomorphisms $f_1:G\to H$ and $f_2: H\to G$.
An easy argument shows that we have $\chi(G) = \chi(H)$, even for graphs ...

**1**

vote

**0**answers

99 views

### NP hard problems on geometric graphs

I have posted this question before but i don't feel i expressed my confusion clearly enough. So i would like to try and explain again. This is a proof of the minimum vertex cover for unit disk graphs ...

**2**

votes

**0**answers

64 views

### Total number of spanning trees of a set of graphs

Given an undirected graph G with $n$ nodes, we can compute its number of spanning trees in polynomial time using Kirchhoff's matrix-tree theorem. Now consider a more complicated setting, in which each ...

**9**

votes

**4**answers

310 views

### Are these three different notions of a graph Laplacian?

I seem to see three different things that are being called the Laplacian of a graph,
One is the matrix $L_1 = D - A$ where $D$ is a diagonal matrix consisting of degrees of all the vertices and $A$ ...

**1**

vote

**0**answers

62 views

### Max flow with minimal requirements algo problem

While applying the algorithm to solve the max flow of the network with minimal requirements on edges, I have encountered a problem.
The algorithm states:
For graph G
create an edge from target to ...

**1**

vote

**1**answer

89 views

### n-cube connectivity problem

Given $n\geq 2$, let us consider the n-cube $H_n=(V,E)$, i.e. vertex set $V$ is $\{0,1\}^n$.
Here, the edges of $H_n$ are directed, oriented by set inclusion, i.e., $(x,y)\in E$ iff $x\subseteq y$ and ...

**6**

votes

**2**answers

118 views

### Realizing a monoid as $\mathrm{End}(G)$ for some graph $G$

This question relates to Realizing groups as automorphism groups of graphs.
Given a monoid $M$, is there a graph $G$ such that the endomorphism monoid $\textrm{End}(G)$ is isomorphic to $M$?

**9**

votes

**1**answer

338 views

### Could there be an exact formula for the Ramsey numbers?

Let $R(k)$ denote the diagonal Ramsey number, i.e. the minimal $n$ such that every red-blue colouring of the edges of $K_n$ produces at least one monochromatic $K_k$.
Is it possible that there ...

**4**

votes

**1**answer

93 views

### Strongly asymmetric graphs

Asymmetric graphs are graphs that have a trivial automorphism group $\textrm{Aut}(G)$, i.e. the only graph isomorphism from $G$ to itself is the identity.
Let's call a graph $G$ strongly asymmetric ...

**6**

votes

**1**answer

95 views

### Isomorphic Hadwiger graphs

Let $G$ be a graph, then we define its Hadwiger graph $\textrm{Hadw}(G)$ in the following way:
$V(\textrm{Hadw}(G)) = \{S\subseteq (V(G): S\neq \emptyset\textrm{ and } S \textrm{ is connected}\}$;
...

**2**

votes

**1**answer

194 views

### Counting Ribbon graphs

Let $G$ be a ribbon graph (sometimes called fat graph) with $v$ vertices and $e$ edges. Furthermore each vertex is of degree $d$.
Q) What is the number of $G$ with the above properties? I mean does ...

**2**

votes

**0**answers

58 views

### relationship of max-sat and min-cut in theory and practice

I have been using MAX-SAT solver to obtain the exact ground state of ising spin glass model:
For 1D periodic model, for systems with 50 binary variables and interaction range of 15th nearest ...

**3**

votes

**1**answer

169 views

### Determinant of the oriented adjacency matrix of a tree

Let $(V,E)$ be a finite oriented directed graph, with vertices and edges ordered, and $M$ the $|V|\times |E|$ matrix with entries
$$ m_{ve} = \begin{cases} 1 &\text{if $e$ points at $v$}\\
-1 ...

**4**

votes

**3**answers

696 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 ...

**1**

vote

**0**answers

46 views

### Solutions for n such that the path number to the n-th node is also n in a complete, rooted, ordered k-ary tree

The path to find the $n$-th node within a complete, rooted, ordered $k$-ary tree can be represented by a number to the base $(k+1)$ that contains no zero digits. See A245905 in OEIS as an example for ...

**7**

votes

**1**answer

233 views

### Number of median graphs?

What is the number of $n$-vertex median graphs? These graphs generalize hypercubes and trees, and have many applications. It seems unlikely that a closed form expression is known, so I would also be ...

**-2**

votes

**1**answer

94 views

### how to reduce 3-colorable graph to this? [closed]

suppose we have a finite set X and a set S of subsets of X and we want to determine is there a subset S' of S such that all members of X belong to exactly one set in S' I think the best problem to ...

**0**

votes

**0**answers

14 views

### matching Robinson-Foulds distance and way to compute RF dist in Phylip

In Comparison of Phylogenetic Trees, Robinson D.F. and Foulds L.R., didn't show how to compute the RF distance between trees, counting the different partition generated by the removing of an internal ...