All Questions
Tagged with eulerian-path combinatorics
36
questions
0
votes
1
answer
40
views
counting Eulerian circuits on complete directed graph
I have a complete directed graph $G$ (including self-loops). How can I count the number of Eulerian circuits on $G$?
For example, in the simple case of $n=2$, there are clearly 4 Eulerian circuits. ...
- 1
6
votes
1
answer
152
views
Is it possible to go over all lines of a grid with a pencil without lifting it or going over a drawn line?
Is it possible to go over all lines of an infinite grid with a pencil without lifting it or going over a drawn line ?
The pencil can cross through a segment already drawn but cannot go over an already ...
- 308
0
votes
2
answers
67
views
Confused about how to find de Bruijn sequence from Eulerian tour
I am not following how wikipedia constructs a de Bruijn sequence from an Eulerian tour here. When our Eulerian tour visits vertices $000,000, 001, 011, 111, 111, 110, 101, 011,
110, 100, 001, 010, 101,...
- 3,019
2
votes
2
answers
105
views
Combinatorics graphs for $2k+1$ representatives from $k $ different countries.
I'm having trouble with the following question :
Representatives from $1+2k$ countries come to an international conference, $k$ representatives from each country.
Is it possible to seat the $k(2k+1)$ ...
- 23
3
votes
1
answer
215
views
Enumerating “Cyclic Double Permutations”
This is a generalization of a question first asked by loopy walt on Puzzling Stack Exchange: https://puzzling.stackexchange.com/q/120243. I asked the following version of the question in the comments, ...
- 142
1
vote
1
answer
113
views
What rigid graphs can be decomposed into triangles such that each edge is in exactly one triangle?
Is there a general algorithm/condition to tell if a graph can be decomposed into triangles such that each edge is in exactly one triangle (the graph $G$ has a set of subgraphs such that each subgraph ...
3
votes
2
answers
182
views
Is this degree sequence planar?
For the degree sequence [6,6,4,4,4,4,2,2,2,2]. Then this graph has $f = 10$ by euler's formula. Let $T$ be the number of triangles. Then the inequalities $2e = 36 \geq 3T + 4(10 - T)$ shows that $T \...
- 651
1
vote
1
answer
27
views
Does there exist Eulerian quadrangulations that are not 1- or 2-degenerate?
I am looking for Eulerian planar quadrangulations that are not 1- or 2-degenerate, but I cannot seem to find such graphs.
Note: a graph is Eulerian if and only if every vertex has an even degree. ...
user931598
0
votes
0
answers
39
views
Why is this graph a connected Eulerian one?
In the well-known article of Oystein Ore titled "A problem regarding the tracing of graphs", Elemente der Mathematik, 6 (1951), 49-53, he proves that an Euler graph $G$ is arbitrarily ...
- 5,782
1
vote
2
answers
87
views
Property of a connected graph with $\text{deg(all nodes)}=\text{even}$
In my lecture nodes it is proposed that for a connected graph $G$ with the degree of all nodes being even, there exist two paths between any two nodes $x,y\in G$ with no common edges. From the very ...
- 175
5
votes
2
answers
1k
views
How can one justify if the graph is planar from adjacency matrix?
Given an adjacency matrix of a graph $G$, I was asked to do the following without drawing the graph:
A) Find the vertex of largest degree.
B) Does the graph have an Euler Circuit?
C) Is the graph ...
- 12.7k
1
vote
1
answer
121
views
Binary subsequence of size three, graph with euler cycle
Alan Tucker's Applied Combinatorics state, "A set of eight binary digits (0 or 1) are equally spaced about the edge of a disk. We want to choose the digits so that they form a circular sequence ...
3
votes
3
answers
353
views
3-regular graph and two-way Euler circuit
A town-planner has built an isolated city whose road network consists of $2N$ roundabouts, each connecting exactly three roads. A series of tunnels and bridges ensure that all roads in the town meet ...
- 2,813
0
votes
1
answer
438
views
Prove that de-bruijn graph has eulerian cycle?
Let $G_{2,n}$ be a de-bruijn graph.
We remove the vertex 11...11 and the vertex 00...00 and all edges connected to them.
Q: ...
- 421
0
votes
1
answer
616
views
Any graph with an Euler circuit is connected.
So I started with defining an Euler circuit as a closed walk containing at least one edge, not repeating any edge, and ending the walk on the same vertex as it was started. Is this a full proof, ...
- 57