**1**

vote

**1**answer

86 views

### Number of eigenvalues of a Cayley graph

Let $G=Z_2^n$ and $S\subset G$. Is there any relation for number of distinct eigenvalues of $\Gamma=Cayley(G,S)$ graph depending on $n$ and $|S|$, or at least diameter of $\Gamma$? If you have any ...

**3**

votes

**1**answer

61 views

### Alternative parallel paths

Parallel strings which connect points $x_1,\dots, x_n$ with points $y_1,\dots, y_n$, are sewn with an additional string. The union of these $n+1$ strings is considered a framed graph (we remember ...

**1**

vote

**1**answer

65 views

### Size of connected components of a graph via its spectrum

I know that we can determine the number of connected components of a graph from the eigenvalues of its Laplacian matrix. My question is:
Is there a way to understand the size of each connected ...

**7**

votes

**1**answer

237 views

### Choosing two-colorable subgraph in a triangulation

Consider a planar graph which is a triangulation.
Is it possible to find a two-colorable subgraph which has common edge with every face of our graph?
It is known that such spanning tree not always ...

**0**

votes

**2**answers

58 views

### Shortest path in a weighted graph with coloured edges

I have a weighted undirected graph with $N$ veritces and $M$ edges with 10 different colours in the whole graph. Each time I pass edges of different colour I have to pay additional fee equal to $K$. ...

**6**

votes

**1**answer

67 views

### Which graphs embedded in surfaces have symmetries acting transitively on vertex-edge flags?

A vertex-edge flag in a graph is a vertex together with an edge incident to that vertex. Given a graph $\Gamma$ embedded in a compact oriented surface $S$, when does the group of homeomorphisms of ...

**2**

votes

**1**answer

140 views

### Self-containing trees

Suppose that $r^2-r-1=0$ and that $T$ is the tree with root $1$ such that the children of each node $x$ are $rx$ and $x+1$. Remove all duplicates as they occur, and let $T(r)$ denote the remaining ...

**2**

votes

**0**answers

67 views

### Maximum number of $4$-cycles

Suppose we have a balanced bipartite planar maximum degree $k$ graph.
How many such graphs on $2n$ vertices have at most $f(n)$ maximum number of $4$ cycles for a given function $f:\Bbb ...

**1**

vote

**0**answers

65 views

### Is there an efficient algorithm to find all the maximum matching in any tree?

A matching in a graph (G) is a set of mutually non-adjacent edges of (G). A maximum matching is a matching of maximal cardinality. A tree is an acyclic connected graph.
Is there an efficient ...

**0**

votes

**0**answers

65 views

### maximal sets of vertices that avoids a clique

I am looking for some known algorithm that finds, for a given graph, all the maximal sets of vertices that avoid a clique of some given size $k$. I'd prefer one written in MATLAB, but other languages ...

**3**

votes

**1**answer

92 views

### chromatic polynomial of G - Join graph

Given a connected graph $G$ with $n$ vertices and given set of $\{m_1,m_2,...,m_n\}$ $n$ integers, we form a new graph $G^{\wedge} $ by considering the complete graph $K_{m_i}$ for each vertex i and ...

**-1**

votes

**1**answer

91 views

### Subgraphs of $\mathbb{R}^2$ in the Hadwiger-Nelson problem

In the setting of the Hadwiger-Nelson problem, two points of $\mathbb{R}^2$ form an edge if and only if their distance is $1$. The resulting graph $G$ has chromatic number $\chi(G)\in \{4,5,6,7\}$ and ...

**0**

votes

**0**answers

46 views

### Factor group lemma [closed]

I have seen the following statement in http://www.sciencedirect.com/science/article/pii/0012365X84900104 [Page 294, part 2.2], but I cannot understand why "then $\mid N\mid *[a_i: 1\leq i\leq n]$ is ...

**1**

vote

**1**answer

54 views

### Counting bounded genus non-isomorphic graphs

What is the number of non-isomorphic $2n$ vertex balanced bipartite graphs of degree at most $d$ and genus $g$?
I am most interested in $d\leq3$ and $g=0$.

**4**

votes

**1**answer

165 views

### exact definition of Fiedler vector

For a given N-vertex similarity graph $ G=(V,A) $ the eigenvalues of the unrenormalized (graph) Laplacian may be denoted as
$$ 0= \mu_0 \leq \mu_1 \leq ... \leq \mu_N $$
where the corresponding ...

**4**

votes

**2**answers

171 views

### Non-Cayley expander graphs

When I search about expander graphs in google I see a lot of articles about expander Cayley graphs. Now my questions are as follows:
Are all expander regular graphs are Cayley, or there is a special ...

**1**

vote

**0**answers

22 views

### Expected number of perfect matchings in bounded degree bipartite graphs

Consider collection $\mathcal C_{n,n,\Delta}$ of every $2n$ vertex balanced bipartite graph of average degree $\Delta$.
What is the expected number of perfect matching a graph in $\mathcal ...

**1**

vote

**0**answers

45 views

### A centralised website for computational attemps in graph theory and metric geometry?

The set of questions below stems from this question.
1) does a website exist that contains (at least links to) code and data files, with the aim to centralise computational results in graph ...

**0**

votes

**0**answers

20 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

110 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

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

**3**

votes

**1**answer

90 views

### Number of perfect matchings of bipartite graphs

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

75 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

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

**0**

votes

**1**answer

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

**0**

votes

**0**answers

41 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

21 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

38 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

56 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

356 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

86 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

119 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

**0**answers

45 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

150 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

44 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

34 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

59 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

71 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

125 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

58 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

460 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

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

**0**

votes

**1**answer

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

**6**

votes

**3**answers

218 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

41 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

58 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

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