**13**

votes

**2**answers

372 views

### Has there been a computer search for a 5-chromatic unit distance graph?

The existence of a 4-chromatic unit distance graph (e.g., the Moser spindle) establishes a lower bound of 4 for the chromatic number of the plane (see the Nelson-Hadwiger problem).
Obviously, it ...

**3**

votes

**1**answer

89 views

### A modified bipartite assignment problem

Consider the following optimization problem. I have $n$ advisors and $dn$ students. I want to assign each student an advisor so that each advisor has exactly $d$ students. Each advisor/student pair ...

**5**

votes

**2**answers

130 views

### Finite graph colorings without symmetries

Let $G$ be a connected finite simple graph with vertex set $V$, $F$ a finite set and let $\Delta(G)$ denote the degree of $G$, i.e. $\Delta(G)= \max_{v\in V} \deg(v)$. We say that a coloring $\phi\...

**4**

votes

**3**answers

184 views

### Relation between diametral path and regularity of a graph

Let $G(V,E)$ be a graph. A path whose length is equal to the diameter of a graph is called a diametral path. In a cycle graph every vertex has $2$ diametral paths. Now I need to prove that this:
...

**1**

vote

**1**answer

153 views

### What does the higher coefficients of ihara zeta function reveal?

Assume we have a graph $G=(V,E)$.
The ihara zeta function $Z(G,u)$ is of form $$\frac1{\displaystyle\sum_{i=0}^{2|E|}c_iu^i}$$
A graph which has $|E|$ edges cannot have a simple cycle of length ...

**1**

vote

**0**answers

48 views

### How to count the number of shortest paths in a 2x2 grid? [closed]

Say that we have a 2x2 regular grid or network. We label the nodes 0 to 3 row-wise. Then, for each node, we want to compute the number of shortest paths that pass through them.
I have a Python code ...

**1**

vote

**0**answers

36 views

### Infinite graphs with number of common neighbors given for each pair of vertices

This is a follow-up to this question.
For any set $X$ we set $[X]^2 = \big\{\{x,y\}: x\neq y \in X\big\}$. If $G=(V,E)$ is a simple undirected graph, and $v\in V$, we set $N(v) = \{w\in V:\{v,w\}\in ...

**1**

vote

**0**answers

62 views

### Number of rooted spanning forests

Let $G$ be a connected simple graph, and identify two vertices $s$ and $t$. Let $\tau(G)$ be the number of spanning trees of $G$, and let $f(G)$ be the number of spanning forests of $G$ with $2$ ...

**1**

vote

**1**answer

76 views

### If the two smallest eigenvalues of the Laplacian matrix of a network are equal to zero, then does it mean that the network is not connected? [closed]

What does it mean if the two smallest eigenvalues of the Laplacian matrix of a graph are equal to zero?

**7**

votes

**1**answer

134 views

### Can the graph removal lemma be proved directly from the triangle removal lemma?

The Triangle Removal Lemma states that any graph with $o(n^3)$ triangles can be made triangle-free by removing only $o(n^2)$ edges. More generally, the Graph Removal Lemma states that for any graph $...

**0**

votes

**1**answer

130 views

### Stable marriages for infinite bipartite graphs

Short and informal version: Does the stable marriage problem have a solution if there are $\kappa$ men and $\kappa$ women for any cardinal $\kappa \geq \aleph_0$?
Long and formal version: Let $\kappa$...

**-2**

votes

**1**answer

61 views

### Splitting the vertices of undirected graphs into 2 sparse sets

(A version of this question for undirected graphs.)
Let $G=(V,E)$ be a finite, simple, undirected graph. For $v\in V$ set
$$
N(v) := \{x\in V: \{x,v\}\in E\}.
$$
Is it possible to find a ...

**15**

votes

**5**answers

479 views

### Cayley graphs of $A_n.$

Consider the Cayley graphs of $A_n,$ with respect to the generating set of all $3$-cycles. Their properties must be quite well-known, but sadly not to me. For example: what is its diameter? Is it an ...

**1**

vote

**1**answer

78 views

### many 5-list colorings

If a graph is 4-list-colorable, then it is easy to see that it has exponentially many 5-list colorings.
This is the first sentence in [Exponentially many 5-list-colorings of planar graphs,JCTB,97 (...

**1**

vote

**1**answer

72 views

### Partitioning finite directed graphs into 3 “incoming-sparse” sets

Let $G=(V,E)$ be a directed graph. For $v\in V$ set $\text{In}(v)=\{x\in V: (x,v)\in E\}$.
Is it possible to find a partition $P_1,P_2,P_3$ of $V$ such that for every $P_i$ and every vertex $v\in ...

**7**

votes

**3**answers

299 views

### A simplified Art Gallery Problem in a matrix

Let's take a $m \times n$ matrix as an area with $m \times n$ blocks (likes a 2D-version of the world in Minecraft). We have to put some lamps in this matrix to illuminate the whole matrix. Here is ...

**1**

vote

**0**answers

42 views

### How to estimate the size of balanced biclique in random bipartite graph?

We have a random bipartite graph $G=(V,U,E)$ and $|V|=|U|=n$, in which any vertex pair $<v,u>$ ($v\in V$,$u\in U$) exists an edge with probability $p$. A balanced bipartite complete graph is a ...

**1**

vote

**0**answers

59 views

### Equivalence between bipartite undirected graph and arbitrary directed graph

Let the adjacency matrix of an undirected bipartite graph be $A = \begin{pmatrix} 0 & B \\ B^T & 0 \end{pmatrix}$ where B is called the biadjacency matrix.
Now, by instead interpreting B as ...

**-2**

votes

**1**answer

62 views

### Degrees and common neighbors

For any simple, finite, undirected graph $G=(V,E)$ and $v\in V$ let $N(v) = \{w\in V:\{v,w\}\in E\}$.
Suppose $G, H$ are finite, simple, undirected graphs and there is a bijection between the vertex ...

**-6**

votes

**1**answer

96 views

### Do degrees determine the chromatic number?

Suppose $G, H$ are finite, simple, undirected graphs and there is a bijection between the vertex sets $\varphi:V(G) \to V(H)$ such that for all $v\in V$ we have $$\text{deg}_G(v) = \deg_H(\varphi(v)).$...

**5**

votes

**0**answers

119 views

### Complexity of graph isomorphism

Last year, Laszlo Babai proved that the graph isomorphism problem can be solved in time:
$$ \exp(O(\log^c n)) $$
where $n$ is the number of vertices.
What is the best bound we have for $c$? (The ...

**4**

votes

**2**answers

207 views

### Algorithms for finding graph isomorphisms

I was wondering if anybody knows where I can find some information about the current (practical) algorithms for finding graph isomorphisms. I've joined the bandwagon and wrote my own which I would ...

**3**

votes

**1**answer

74 views

### Let $S$ be the nonempty set of strongly regular graphs with given parameters. Must $S$ contain vertex transitive graph?

As the title says, let $S$ be the nonempty set of strongly regular graphs with given parameters. Must $S$ contain vertex transitive graph?
I suspect the most likely counterexample would be $|S|=1$.

**5**

votes

**2**answers

130 views

### “Common-neighbor-regular” graphs

Let $G=(V,E)$ be a finite, simple, undirected graph. For $v\in V$ we set $N(v)=\{w\in V:\{v,w\}\in E\}$.
We say that $G$ is $k$-common-neighbor-regular if for all $v\neq w\in V$ we have $|N(v)\cap N(...

**3**

votes

**1**answer

84 views

### Tournament whose large subtournaments contain no automorphism

For sufficiently large $n$, it is known that most tournaments of size $n$ contains no nontrivial automorphism, though I forgot the reference.
For sufficiently large $n$, does there always exist a ...

**4**

votes

**1**answer

125 views

### Representing a graph's vertices as linear combinations of paths

I have a (directed graded) graph $G=(V,E)$ with two distinguished subsets of $V$: sources and destinations. I am to show that the set of indicator functions of paths starting in a source and ending in ...

**5**

votes

**1**answer

193 views

### Construction of a graph

To construct a specific kind of undirected graph $G=(V,E)$, which $|V|=n>2$. For convenience, label the vertices with $v_1,v_2,\dots ,v_n\in V$, and $(v_i,v_j)\in E$ means there is a edge between ...

**0**

votes

**0**answers

59 views

### Tight bound of Turan number for K_{1,t,t}?

I'm looking for a tight bound for Turan number $ex_2(n,K_{1,t,t})$, where $K_{1,t,t}$ is the complete 3-partite graph with parts of size 1, t, and t.
The motivation is that we now $ex_2(n,K_{t,t})=O(n^...

**0**

votes

**0**answers

36 views

### Question about number of faces for regular graphs

I came upon the following problem. Consider a regular 3-graph with faces of degree $2, 3, 4, 5$, 4-graph and faces of degree $2, 3$ and 5-graph with faces of degree $2, 3$. Are there any such graphs ...

**3**

votes

**1**answer

96 views

### Menger's Theorem for planar triangulations

I was reading the paper "Planar separators" by Alon, Seymour and Thomas (available on the first author's webpage). They consider a planar triangulation, that is, a maximally planar graph $G$ drawn in ...

**4**

votes

**1**answer

82 views

### The minimum number of Hamiltonian paths in a strongly connected tournament of order $n$

For $n\ge3$ let $a(n)$ be the minimum number of Hamiltonian paths in a strong (i.e., strongly connected) tournament of order $n.$
Where is $a(n)$ discussed in the literature? Is the exact value ...

**2**

votes

**1**answer

128 views

### Removing cycles in a directed graph by swapping edges orientation

I have the following problem: let $G$ be a finite directed graph with $V$ vertices $v_i$ and $E$ (directed) edges $e_j$. I know that if an edge $e_k = (v_i, v_j)$ is in the graph, then the opposite ...

**0**

votes

**0**answers

25 views

### A measurement for vertex- and edge failure sensitivity

I want to have a metric that helps me judge how independent different paths in one graph are.
So here are my assumptions:
A graph consists of a set of vertices ($V$) and edges ($E$).
A path ...

**1**

vote

**0**answers

103 views

### Extending continuous functions from $\partial X$ to $X\cup \partial X$

Consider a proper geodesic hyperbolic space $X$ (in the sense of Gromov). Let $\partial X$ be its Gromov boundary. Consider a complex-valued continuous function on the boundary $f\colon\partial X\to\...

**0**

votes

**1**answer

92 views

### Topology on $\omega\times\omega$ such that topologically connected equals graph-connected

For any set $X$ we define $[X]^2 =\big\{\{a,b\}: a, b \in X\text{ and }a\neq b\big\}$.
Let $$E = \big\{\{(a_1, a_2), (b_1, b_2)\}\in[\omega\times\omega]^2: |a_i-b_i| = 1\text{ for some } i\in\{1,2\}\...

**0**

votes

**0**answers

36 views

### For which matrices deciding permutation similarity is polynomial?

Q1 For which matrices deciding permutation similarity is polynomial?
It is not easier than graph isomorphism (and very likely is equivalent to it).
If necessary, assume the entries are nonnegative ...

**0**

votes

**0**answers

39 views

### Is the Hadwiger number reconstructible?

Let $G, H$ be two finite, simple, undirected graphs. We call them "reduce-by-1"-isomorphic, or $r_1$-isomorphic for short, if there is a bijection $\psi: V(G) \to V(H)$ such that for all $v \in V(G)$ ...

**0**

votes

**1**answer

110 views

### “Reduce-by-1”-isomorphic graphs

Let $G, H$ be two finite, simple, undirected graphs. We call them "reduce-by-1"-isomorphic, or $r_1$-isomorphic for short, if there is a bijection $\psi: V(G) \to V(H)$ such that for all $v \in V(G)$ ...

**0**

votes

**0**answers

45 views

### Approximation to colouring for bounded degree graphs

I have already asked one question on colouring, this question is more specific.
Given a bounded degree graph $G$ with $\Delta(G)=2d$, is there a well know algorithm to achieve an approximation ratio ...

**3**

votes

**0**answers

84 views

### What is the complexity of finding a third Hamilton Cycle in cubic graph?

According to Smith Theorem: if a cubic graph has a hamilton circuit then it must have a second one. SMITH : Given a Hamilton circuit in a 3-regular graph, find a second Hamilton circuit. It is known ...

**2**

votes

**0**answers

134 views

### Is the class of Heyting algebras originating from directed graphs a variety?

The category RefGph of reflexive directed graphs
is the functor category $\hat{∆}_1=\mbox{Fun}(∆^◦_1,$Set), where $∆_1$ is
the simplex category truncated at level 1.
Hence the poset Sub(X) of ...

**1**

vote

**1**answer

76 views

### Graph colouring for bounded degree graphs

I'm fairly new to colourings on bounded degree graphs i'm interested in the following questions,
For planar graphs with bounded degree $4$ is finding the colouring number $NP$-hard? So is ...

**1**

vote

**1**answer

69 views

### Intersection number of categorical product of graphs

Let $G, H$ be finite, simple, undirected graphs. Suppose $i(G), i(H)$ are their respective intersection numbers.
If $G\times H$ denotes the categorical product of graphs, what is $i(G\times H)$ in ...

**2**

votes

**1**answer

40 views

### Generalizing series-parallel digraphs with feedback

There are common definitions of series-parallel (SP) graphs and digraphs: the basic idea is as follows. A SP graph (or digraph) has two distinguished vertices $s$ ("source") and $t$ ("target"). The ...

**1**

vote

**1**answer

157 views

### Product and coproduct for bipartite graphs

Consider the category $BiGraph$ of bipartite graphs (vertices are named "places" and "transitions" like in Petri nets) and continous maps. A subgraph is named open iff it is place-bordered, and a map ...

**8**

votes

**1**answer

145 views

### Non-isomorphic graphs with isomorphic edge vectors

Let $G$ and $H$ be graphs on the vertex set $\{1, \ldots, n\}$ and let $(e_i)$ be the standard basis of $\mathbb{R}^n$. For each edge $\{i,j\}$ define edge vectors $e_i - e_j$ and $e_j - e_i$ in $\...

**5**

votes

**2**answers

92 views

### Majority coloring for directed graphs

I came up with the following coloring concept when studying neural networks (which are often modelled using directed graphs). No idea whether there is already an established name for it.
If $X$ is a ...

**3**

votes

**0**answers

47 views

### Number of Hamiltonian paths in the Hoffman-Singleton graph/Moore graphs?

Does anyone happen to know how many Hamiltonian paths are in the Hoffman-Singleton graph, or have any idea on how I could count such paths?

**0**

votes

**1**answer

76 views

### Majority colorings

If $X$ is a non-empty set, we say that $M\subseteq X$ is a majority if $|M| > |X\setminus M|$.
Let $G=(V,E)$ be a finite, simple, undirected graph. For $v\in V$ we set $N(v)=\{x\in V: \{x,v\} \in ...

**4**

votes

**3**answers

88 views

### Name for directed graphs with “balanced cycles”

Does the following class of graphs have a name?
I'm interested in directed graphs with the following property: for every cycle (of the underlying undirected graph) half of the edges go in one ...