**0**

votes

**0**answers

22 views

### 1-factorizations of complete multigraphs

When is it possible to find a 1-factorization of the complete multigraph $\lambda K_{2k}$ in which any two 1-factors have at most 1 edge in common? In particular, I am interested in whether such a ...

**1**

vote

**3**answers

131 views

### On number of perfect matchings

Consider $2n$ vertex balanced bipartite graph.
If total number of edges is $n^2$ then we have $n!$ perfect matchings.
Fix $c\in(0,\frac12)$ and consider collection of $2n$ vertex balanced bipartite ...

**1**

vote

**1**answer

53 views

### Is there any digraph data set that gives all directed graphs satisfying certain requirements?

I'm looking for a digraph dataset that can return all directed graphs satisfying certain requirements.
Following are some examples:
All tournament with 12 vertices;
All connected digraphs with 10 ...

**4**

votes

**2**answers

245 views

### Are all numbers from $1$ to $n!$ the number of perfect matchings of some bipartite graph?

Let $f(G)$ give the number of perfect matchings of a graph $G$.
Consider set $\mathcal N_{2n}=\{0,1,2,\dots,n!-1,n!\}$.
Consider collection of all $2n$ vertex balanced bipartite graph to be ...

**2**

votes

**0**answers

78 views

### Regularity for a bipartite graph

Let $G$ be a bipartite graph with $2^n$ left vertices and $2^n$ right vertices such that:
1) degree of every vertex is not greater then $2^t$
2) number of all edges is greater than $2^{n +t - O(\log ...

**0**

votes

**1**answer

55 views

### Long term behavior of a certain discrete time dynamical system on graphs

Consider the graph $(V,E)$ with vertex set $V=\{v_1,...,v_n\}$ and edge set $E\subset V\times V$. Further, assume that $\forall v_i\in V, (v_i,v_i)\in E$.
Assume that each vertex has an ...

**1**

vote

**1**answer

101 views

### Graph Isomorphism for Triangle Free graph

Is there any specific computational complexity result of Graph Isomorphism for Triangle Free graphs?
Anything close to the subject will help and of course, I have searched Google.

**3**

votes

**1**answer

98 views

### Covering a graph by trees with depth constraint

Given a graph $G$ and a depth constraint $h$, my question is: what is the complexity to find a tree cover of $G$, denoted as $T=\{T_1, T_2, ..., T_n\}$. For each $T_i$, its depth(height) is no larger ...

**1**

vote

**0**answers

44 views

### Largest number of perfect matchings in bounded genus graphs

What is the largest number of perfect matchings a genus $g$ bipartite graph on $n+m$ vertices have?

**0**

votes

**0**answers

28 views

### Similarity metric for labelled weighted graph/minimum spanning tree

I'm looking for a metric to measure similarity of minimum spanning trees of labelled weighted graphs. Each entity to compare has the same nodes (number of nodes and labels identical) but (unlabelled) ...

**1**

vote

**0**answers

42 views

### Influence of independent variables on boolean functions?

Suppose a simple connected graph $G$ where its vertices are assumed to be independent. An event with uncertainty corresponds to each vertex. My instructor guides me that even though the vertices ...

**2**

votes

**0**answers

57 views

### When is the graph of cliques isomorphic to the graph itself?

Given a graph $G$ and the set $C_k(G)$ of the $k$-cliques in $G$, one can build a clique graph $H$ whose vertices $c_i\in C_k(G)$ are connected if the vertex sets of $c_i$ and $c_j$ have an ...

**13**

votes

**2**answers

369 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

88 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

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

**4**

votes

**3**answers

176 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

75 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

126 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

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

**-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

470 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

76 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

70 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

292 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

61 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

94 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) = ...

**5**

votes

**0**answers

115 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

200 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

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

**3**

votes

**1**answer

83 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

123 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

192 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

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

**0**

votes

**0**answers

35 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

94 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

81 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

116 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

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

**0**

votes

**1**answer

89 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 } ...

**0**

votes

**0**answers

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

**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)$ ...