**11**

votes

**5**answers

1k views

### Texts on the General History of Contemporary Combinatorics

I am looking for some core texts (books, book chapters, papers) about the general history of contemporary combinatorics, starting, say, from the interwar period up to today.
Texts about the history ...

**8**

votes

**0**answers

60 views

### Which paths in a graph are orthogonal to all cycles?

Start with some standard stuff. Suppose we have a directed graph $\Gamma$. I'll write $e : v \to w \,$ when $e$ is an edge going from the vertex $v$ to the vertex $w$. We get a vector space of ...

**5**

votes

**2**answers

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

**1**

vote

**1**answer

69 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

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

**19**

votes

**3**answers

967 views

### Obstructions for embedding a graph on a surface of genus g

Kuratowski's theorem tells us the complete graph $K_5$ and the bipartite graph $K_{3,3}$ are the only obstructions to a graph being planar, ie embeddable in the plane with no edge-crossings.
Is ...

**2**

votes

**0**answers

43 views

### What is the densest bipartite graph with unique Hamiltonian cycle?

In a prior post regarding perfect matching, it was stated that the densest graph with a perfect matching cannot have more than $n^2$ edges, if graph has $2n$ vertices.
Analogously, what is the ...

**8**

votes

**2**answers

356 views

### Densest Graphs with Unique Perfect Matching

Given a graph $G$ with $n$ vertices, that has a perfect matching $M$, what is the maximal number of edges that $G$ can have without contradicting the uniqueness of $M$?
Are examples of such extremal ...

**3**

votes

**1**answer

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

**3**

votes

**1**answer

105 views

### Alternative parallel paths

There are $n$ non-intersecting strings (with ends $x_1,\dots, x_n$ and $y_1,\dots, y_n$). An additional string intersects the first $n$ strings somehow. All the intersections are simple (vertices of ...

**8**

votes

**2**answers

643 views

### Spanning trees of plane graphs containing an edge of every face

I feel sure this must be known, but can I find it??
Which connected plane graphs (graphs drawn in the plane without crossings) have a spanning tree such that at least one edge of each face is in the ...

**7**

votes

**1**answer

268 views

### Choosing two-colorable subgraph in a triangulation

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

**1**

vote

**1**answer

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

**1**

vote

**1**answer

117 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

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

**6**

votes

**1**answer

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

**0**

votes

**2**answers

80 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$. ...

**14**

votes

**4**answers

1k views

### Checking if two graphs have the same universal cover

It's possible I just haven't thought hard enough about this, but I've been working at it off and on for a day or two and getting nowhere.
You can define a notion of "covering graph" in graph theory, ...

**2**

votes

**0**answers

73 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

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

**8**

votes

**1**answer

560 views

### Bipartite Graphs arising from two k-partitions of a given Graph

Let $G$ be an $n$-chromatic connected graph. Let $(V_1, V_2, \cdots, V_n)$ and $(U_1, U_2, \cdots, U_n)$ be two partitions of $V(G)$ corresponding to proper n-colorings of $G$.
Consider the bipartite ...

**0**

votes

**0**answers

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

**-1**

votes

**1**answer

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

**1**

vote

**1**answer

58 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

**2**answers

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

**0**

votes

**1**answer

264 views

### Reverse optimization of a minimum cost flow network

Given an undirected graph $(V,E)$, with $W$ as the weight of each edge, and a convex cost function $F(X)$, such as $|X|^k$ ($k>1$).
The cost to send $x$ unit of flow through edge $e_i$ is defined ...

**4**

votes

**1**answer

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

**1**

vote

**0**answers

25 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

**3**answers

122 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

**0**answers

46 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

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

**13**

votes

**2**answers

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

**4**

votes

**1**answer

421 views

### inequality with exponents

We are given a graph $G$, each vertex $v$ has an assigned value $\gamma_v\in [0,1]$, and it happens that for every $v$ we have $\gamma_v+\sum_{u\in \delta(v)} \gamma_u = 1$. Assume that $\sum_v ...

**1**

vote

**1**answer

50 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

93 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

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

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

**1**answer

134 views

### Finding many disjoint sub-trees with many leaves

Let $T$ be a rooted binary tree with $L$ leaves, and let $\ell$ be a natural number smaller than $L$. The question is what is the maximal number of disjoint rooted sub-trees with at least $\ell$ ...

**0**

votes

**1**answer

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

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

**0**answers

42 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

25 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

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

**0**

votes

**1**answer

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

**3**

votes

**2**answers

455 views

### How many triangles can a connected graph with $n$ vertices and $m$ edges have?

I am very interested in the maximum number of triangles could a connected graph with $n$ vertices and $m$ edges have. For example, if $m\leq n−1$, this number is $0$, if $m=n$, this number is $1$, if ...

**1**

vote

**1**answer

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

**5**

votes

**2**answers

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

**3**

votes

**1**answer

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

**1**

vote

**2**answers

106 views

### The cost function in the Weighted Bipartite Matching Problem (a.k.a the Assignment Problem)

In the definition of this problem, the weight/cost function generally takes value in $\mathbb{Z}$ (or sometimes $\mathbb{Q}$).
This is what I observed from some books (e.g. "Combinatorial ...