Is there a characterization of graphs $G$ such that $\exists$ $\phi : G \rightarrow KG(n,k)$, where $KG(n,k)$ is the Kneser graph ($k \leq \lceil \frac{n}{2}\rceil $). Any refe …

I am looking for examples/families of graphs with the following (maybe vague-sounding at first) property: the graph $G$ has a relatively large subgraph $B$ such that $B$ is biparti …

Consider a minimally connected graph (i.e., a spanning tree) on $n$ nodes, $\mathcal{T}=(\mathcal{V},\mathcal{E}_{\tau})$, and its complement $\overline{\mathcal{T}}=(\mathcal{V}, …

A spanning tree in a graph is a connected spanning subgraph with no cycles; it is well known that the number of spanning trees can be found by taking the determinant of a certain m …

Hello everyone. I'm really struggling with this question. All help appreciated. Find the minimum positive integer r for which there exists an r-regular graph G such that λ(G) ≥ κ( …

Hello everyone, I already asked this question on the TCS Stack Exchange, but it has not been resolved yet. Maybe readers of this forum will have other ideas or information, althou …

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 $ int …

I am seeking literature on 3D orthogonal drawings of knots, especially minimum bend drawings. An orthogonal drawing employs segments parallel to the axes of a Cartesian coordinate …

I begin with terminology I use in the question. A real square matrix $A$ is negative-stable if for every eigenvalue $\lambda$ of $A$, ${\mathrm{Re}}(\lambda) < 0$; $\ast$-n …

This question, is a slightly different disguise (see below), came up in discussions of this question about equitable partitions A $0,1$ vector in $\mathbb{Z}^n$ is any vector with …

We are talking about undirected simple graphs and partitions of their vertex sets into disjoint non-empty cells. Such a partition is equitable if for any two vertices $v,w$ in the …

Hello, I have the following conjecture: Write all numbers from $1$ to $n^2$ over an $n\times n$ board as usually. There not exists $n$ such that we can find a hamiltonian path on …

I would like to be able to find maximum values of degree-3 homogeneous polynomials, when the variables are non-negative real numbers that sum to 1. For example, For example, the m …

Consider a planar pointset in a rectangle, where every point has a color (an integer label). We need to select one point of every color, so as to minimize the cost of a planar MST …

If $G$ is 2 - self centered graph. then how to prove that $G$ has at least $2n - 5$ edges? where $n\geq 5$. I started by assuming if number of edges $\mid E\mid\leq 2n-6$ then the …