# Tagged Questions

**1**

vote

**1**answer

65 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

954 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

581 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

237 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

191 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

180 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

106 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

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

**4**

votes

**1**answer

127 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

46 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

249 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

55 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

103 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

170 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

37 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

163 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

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

**9**

votes

**1**answer

317 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

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

**30**

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

220 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

52 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

59 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

125 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

70 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

142 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

98 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

148 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

84 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

61 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

279 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

58 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

82 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

116 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

321 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

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

**5**

votes

**1**answer

84 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

193 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

54 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

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

**2**

votes

**3**answers

590 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

43 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

222 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

91 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

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

**1**

vote

**1**answer

79 views

### What is “graph-directed iterated function”?

Im translating an article about Rauzy fractal and I ran into this sentence:
...

**9**

votes

**2**answers

422 views

### Can a parent and child node have the same type in a well-founded digraph tree?

$\newcommand\toward{\rightharpoonup}$It would help me to
understand something in a current research project if someone
could provide an example of directed graph $\langle
G,\toward\rangle$ with the ...

**7**

votes

**4**answers

237 views

### 4-regular graph with every edge lying in a unique 4-cycle

What are all 4-regular graphs such that every edge in the graph lies in a unique-4 cycle?
Among all such graphs, if we impose a further restriction that any two 4-cycles in the graph have at most one ...

**0**

votes

**1**answer

47 views

### Petersen 2-factor decomposition theorem for directed graphs

Petersen proved that every 2k-regular graph can be decomposed into k disjoint 2-factors. I would like to know that is it true that if G is a directed regular graph (d_out(v)=d_in(v)=k), then can G be ...