**17**

votes

**2**answers

988 views

### Cops and drunken robbers

Consider a game of cops and robbers on a finite graph. The robber, for reasons left to the imagination, moves entirely randomly: at each step, he moves to a randomly chosen neighbour of his current ...

**6**

votes

**2**answers

91 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$?

**1**

vote

**1**answer

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

**8**

votes

**1**answer

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

**-1**

votes

**0**answers

36 views

### Random Spanning Tree Edge Probability [on hold]

I am working on a problem with a Loop Erased Random Walk used to create random spanning trees. The problem has many parts, but there are two hints to help with the more complicated problems
Figure ...

**-1**

votes

**0**answers

60 views

### Are there any special properties of graph eigenvalues of perfect matchings?

Say if the graph is just a perfect matching of its vertices OR if it is an union of a few perfect matchings OR its an union of a few perfect matchings and a part of another?
Anything if one further ...

**-2**

votes

**0**answers

77 views

### What is the characterization of a graph Laplacian? [on hold]

Given a matrix, what properties must it have so that its ensured that there exists a graph whose Laplacian it would be? (...may be you can consider weighted and unweighted cases separately...)
And ...

**3**

votes

**1**answer

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

**0**

votes

**0**answers

57 views

### Number of graphs with M edges that does not contain K-clique [on hold]

If we consider the space of graphs $G(n,M)$ where $M$ denotes the number of edges. Is there any known way of calculating the number of graphs within this space that does not contain any k-cliques? Can ...

**8**

votes

**1**answer

179 views

### Vertex-primitive graphs with two vertices having almost the same neighbourhood

Hypothesis: Let $\Gamma$ be a vertex-primitive graph with two vertices $u$ and $v$ such that $$|N(u) \cap N(v)|=|N(v)|-1$$
Question: Is it true that $\Gamma$ must either be a complete graph or have ...

**0**

votes

**1**answer

76 views

### Finding nodes with a particular weight in a graph

Say that an edge $e$ is incident to a node $v$ if one of its two extremes is $v$.
Then we can also say that $v$ is hit by $e$. We might define the notion of "weight of a node $v$" as the sum of all ...

**5**

votes

**1**answer

79 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

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

**0**

votes

**1**answer

149 views

### Efficient isomorphic subgraph matching with similarity scores

I'm a computer vision PhD student, and I'm looking for an efficient approximation to the following problem, which could end up helping in image to image matching. Failing that, pointers to relevant ...

**2**

votes

**0**answers

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

**5**

votes

**1**answer

124 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

**3**answers

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

**3**

votes

**1**answer

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

**1**

vote

**0**answers

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

**1**

vote

**1**answer

64 views

### Coloring algorithm maximising color difference between neighbors

Consider a graph and a set of ordered colors ${\cal C} = \{1,2,\cdots,C\}$. I want to color each node $i$ with a color $c_i\in{\cal C}$ so as to maximize the minimum color difference between two ...

**-2**

votes

**1**answer

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

**3**

votes

**1**answer

115 views

### special 1-factorization of regular bipartite graphs

Let $n= 2k+1, |X|=|Y|= n$ and $G= (X, Y, E)$ be a $(k+1)$-regular bipartite graph.
Let $M$ be a perfect matching of $G$ having the property that every cycle of size 4
$C_4$ intersects $M$ in at most ...

**0**

votes

**0**answers

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

**0**

votes

**1**answer

31 views

### Is it known whether Minimum Cost Multicut is APX-hard?

My questions is concerned with the following problem: Given an undirected graph $G = (V, E)$ and (edge costs) $c \in \mathbb{Z}^E$,
$$\min \left\{ \sum_{e \in E} c_e x_e\ \middle|\ x \in \{0,1\}^E \ ...

**-2**

votes

**0**answers

43 views

### when a given graph is 3-colorable? [closed]

I want to use graph 3-colorability to prove a problem is NP-complete But I'm not sure when a given graph is 3-colorable.
I think if it doesn't have any node to be connected to all 3 vertices of a ...

**-4**

votes

**0**answers

63 views

### About diagonal entries of the graph Laplacian [on hold]

[..in the following you can assume its a regular graph if necessary..]
Is anything special known about them?
Are they characterized in any other way?
Is the largest diagonal entry in any power of ...

**7**

votes

**4**answers

205 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

**0**answers

75 views

### independent subset problems [closed]

I'm interested in the following which i suspect is probably a well studied problem.
Given a set $N=\{1,2,...,n\}$ and $M=\{1,2,...,m\}$ consider a map $$f:N\rightarrow 2^{M}$$ (elements of $N$ to ...

**9**

votes

**2**answers

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

**1**

vote

**1**answer

65 views

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

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

**4**

votes

**1**answer

250 views

### How to find or constrain “particularly good” (two-sided) spectral expanders?

I'm new to graph theory, but a response to a question I asked a while ago introduced me to the concept of expander graphs.
A k-regular graph (henceforth "graph") on n nodes has eigenvalues k = λ1 ≥ ...

**0**

votes

**0**answers

44 views

### $\Omega(G)$ is homeomorphism to $\Omega(T)$ [closed]

Is it possible that the end set of graph $G$ is homeomorphism to the set of end for every spanning tree of $G$ where $G$ has a cycle. In other hand, for given graph $G$ and spanning tree $T$ of $G$. ...

**1**

vote

**1**answer

104 views

### NP hard problems on UD graphs

I'm reading up on NP hard problems in Unit Disk graphs. I'd like to point out i'm fairly new to this NP hard stuff so i'm trying to get around how to prove something is NP hard.
...

**22**

votes

**6**answers

1k views

### Shortest grid-graph paths with random diagonal shortcuts

Suppose you have a network of edges connecting
each integer lattice point
in the 2D square grid $[0,n]^2$
to each of its (at most) four neighbors, {N,S,E,W}.
Within each of the $n^2$ unit cells of ...

**0**

votes

**1**answer

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

**10**

votes

**1**answer

665 views

### A generalization of the triangle counting problem for simple weighted graphs

One nice identity is $$tr(A^3)/6$$ which counts the number of triangles of a graph represented with adjacency matrix $A.$ It also implies that triangle counting can be performed in subcubic time.
...

**2**

votes

**1**answer

132 views

### Graph automorphism that swaps two pairs of nodes

Suppose we have two automorphisms on a graph $G$ such that each one swaps a separate pairs of vertices. Is it possible to construct (or prove the existence of) a third automorphism that swaps both ...

**0**

votes

**1**answer

54 views

### Intersection graphs

Does anybody know of a paper which proves that finding the maximum independent set in geometric intersection graphs is NP hard? Even general intersection graphs?

**5**

votes

**3**answers

292 views

### Visualizing a graph

I have a finite but huge metric graph with say 1000 vertices.
It comes say as 10000x10000 symmetric matrix filled by $0,1,\dots$ and $\infty$;
0's on the diagonal and $\infty$ is for pairs of vertices ...

**7**

votes

**4**answers

266 views

### Do there exist sparse graphs with large crossing number?

Does there exist a sequence of graphs $\{ G_n \}$ such that
$G_n$ has $n$ vertices,
the number of edges of $G_n$ is $O(n)$, and
the crossing number of $G_n$ is $\Omega(n)$?
In particular, do ...

**2**

votes

**1**answer

83 views

### irregular pairs in half graphs - Szemeredi regularity

Szemeredi's regularity lemma is a well-known result about partitioning large graphs into pieces such that most pairs of pieces are "regular". The precise statement takes a bit of detail so I'll just ...

**0**

votes

**0**answers

80 views

### Does the weak Hadwiger conjecture imply the Hadwiger conjecture?

For any cardinal $\kappa$, let $K_\kappa$ denote the complete graph on $\kappa$. We consider the following statements:
(H) If $G$ is a graph and $\chi(G) = \kappa$ then $K_\kappa$ is a minor of $G$.
...

**2**

votes

**1**answer

210 views

### Cospectrality and dimension of graphs

Firstly, I apologize if the question is long. I appreciate any helpful answers and ideas.
In the following all graphs are simple and connected.
Let $G$ be graph with vertex set ...

**12**

votes

**0**answers

164 views

### Coloring the edges of a torus graph

Question:Consider the $2k \times 2k$ grid graph on a torus. Is it true that for every $2$-coloring of the edges, there is an antipodal pair of vertices connected by a path that changes colors at most ...

**9**

votes

**1**answer

299 views

### Shortest Paths in the “Cantor Graph”

First, let me explain, what I understand by a "Cantor Graph":
it is an infinite, directed graph with self loops and countably many vertices labelled with the natural numbers; every ordered pair of ...

**9**

votes

**3**answers

2k views

### Lagrange four-squares theorem: efficient algorithm with units modulo a prime?

I'm looking at algorithms to construct short paths in a particular Cayley graph defined in terms of quadratic residues. This has led me to consider a variant on Lagrange's four-squares theorem.
The ...

**0**

votes

**0**answers

48 views

### Expected number of distinct nodes visited in a directed bipartite graph [migrated]

Let $G = (V,E)$ be a directed bipartite graph with $V = \{I \cup O\}$ where $\left\vert{I}\right\vert = n$ and $\left\vert{O}\right\vert = m$.
All the edges start from a vertex in $I$ and end on a ...

**7**

votes

**3**answers

345 views

### Is there a continuous analogue of Ramanujan graphs?

I think it might help to think of the following definition of a Ramanujan graph - a graph whose non-trivial eigenvalues are such that their magnitude is bounded above by the spectral radius of its ...

**6**

votes

**2**answers

224 views

### Counting valid coordinates

We are given a matrix $D = (d(i,j))_{1 \leq i,j \leq n}$ such that $d(x,z) \leq d(x,y) + d(y,z)$ for each $1 \leq x,y,z \leq n$. It is also known that $d(x,y) \in \mathbb{N}$ (In this question $0 \in ...

**1**

vote

**1**answer

136 views

### Probability of each edge in K-clique [closed]

For $c \in R$ and $k \in N$, $k \geq 3$ let
$p_{k,c} := n^{\frac{−2}{k+1}}log^c(n)$.
I would like to prove that exists $c\in R$ such that every edge in the random graph $G(n,p_{k,c})$ lies in a copy ...