This question is related to this previous question. Many combinatorial configurations have Levi graphs which may be represented as derived graphs obtained from voltage graphs over …

I have an undirected, unweighted graph, and I'm trying to come up with an algorithm that, given 2 unique nodes on the graph, will find all paths connecting the two nodes, not inclu …

This question is related to the question of drawing a combinatorial 3-configuration of points and lines with straight lines. We only relax the condition and admit drawings with pse …

We can define the (first) homology of a surface $S$ by working with graphs embedded in $S$. That is, we take any (oriented) graph which is 2-cell embedded in $S$, and take cycles …

We would like to know how hard it is to count Eulerian orientation in an undirected 4-regular graph. For a given edge orientation to be Eulerian, we mean that every vertex has 2 in …

Last month I discovered a nice question on stackoverflow and thought the 1,n matching problem could be solved via introducing a 1,k tree matching. Look here for my question, but as …

[Follow-up to Can every finite graph be represented by one prescribed sequence of natural numbers?, reformulated thanks to a hint from Jacques Carette] Let $V(n,\nu)$ and $E(n, …

The Rado graph contains every finite graph as an induced subgraph. It surely contains some finite graphs infinitely often as an induced subgraph, e.g. $K_2$. Does it contain all fi …

I am wondering if there are special classes of graphs that have eigenvalue of -1 for the adjacency matrix. I know that the complete graphs, Kn, have this property, but am wonderin …

(This is a follow-up to my previous question Can every finite graph be represented by an arithmetic sequence of natural numbers?) Since it is obviously false that every finite gra …

This is a question from the book "Introduction to the theory of computation" by Michael Sisper. Problem 0.12 page 27 asks "Show that every graph with 2 or more nodes contains two …

Let $ \lambda_1 \ge \lambda_2 \ge \dots \lambda_{2n} $ be the collection of eigenvalues of an adjacency matrix of an undirected graph $G$ on $2n$ vertices. I am looking for any w …

It is well-known that the black-and-white coloring of the Heawood graph on 14 vertices determines a combinatorial 3-configuration with 7 "points" and 7 "lines", known as Fano plane …

Let $G$ be a finite group. Do eigenvalues of its Cayley graph say anything about the algebraic properties of $G$? The spectrum of Cayley graph may depend on the presentation, so it …

I'm looking at algorithms to construct short paths in a particular Cayley graph defined in terms of quadratic residues. This has led me to consider a variant on Lagrange's four-squ …