2
votes
0answers
24 views
Are combinatorial configurations whose Levi graphs may be represented as covering graphs over voltage graphs realizable with pseudolines?
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 …
2
votes
4answers
216 views
Finding all paths on undirected graph
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 …
1
vote
0answers
39 views
Drawing a combinatorial 3-configuration of points and lines with pseudolines
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 …
2
votes
2answers
168 views
Homology Question
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 …
3
votes
1answer
76 views
Counting Eulerian Orientation in a 4-regular undirected graph
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 …
1
vote
1answer
142 views
Maximum bipartite graph (1,n) “matching”
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 …
0
votes
0answers
56 views
Uniformly computable classes of graphs
[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, …
3
votes
1answer
69 views
Rado graph containing infinitely many isomorphic subgraphs
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 …
0
votes
2answers
162 views
Properties of Graphs with an eigenvalue of -1 (adjacency matrix)?
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 …
0
votes
1answer
312 views
Can every finite graph be represented by one prescribed sequence of natural numbers?
(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 …
-1
votes
0answers
190 views
don’t understand question: graphs with 2 or more nodes have 2 nodes with same degree [closed]
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 …
13
votes
4answers
582 views
The middle eigenvalues of an undirected graph
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 …
7
votes
2answers
153 views
Drawing 3-configurations of points and lines with straight lines
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 …
4
votes
2answers
127 views
Spectral properties of Cayley graphs
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 …
6
votes
2answers
243 views
Lagrange four-squares theorem: efficient algorithm with units modulo a prime?
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 …
