Questions tagged [graph-theory]
Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.
25,013 questions
0
votes
0
answers
6
views
Interesting theorems involving simple/Eulerian/bipartite graphs and Dijkstra’s algorithm (for a discrete math exam)?
In my discrete mathematics course, our professor said that for the graph theory part of the final exam we only need the following five notions:
Simple graph
Eulerian graph
Euler tour
Bipartite graph
...
- 19
1
vote
0
answers
19
views
Restrictions of Knight's Tour on Circular Board
Does a closed knight’s tour exist on an n-vertex “circular” chessboard with wrap-around moves?
I’m interested in variants of the knight’s tour, but on a “circular board” rather than a rectangular one. ...
- 11
0
votes
1
answer
53
views
Fundamental group of planar topological graphs
I am trying to do the following exercise on homotopy theory:
“Prove that every finite, connected topological graph $\Gamma\subset \mathbb{R}^2$ is homotopically equivalent to the wedge sum (pointed ...
- 871
1
vote
1
answer
33
views
Any 'locally butterfly' graph be constructed as line graph from a 3-regular, triangle-free graph: Can this be generalized to locally windmill graphs?
A simple graph is called locally butterfly, if the closed neighbourhoods of all vertices (set of all vertices at distance 1 and adjacencies between these and the original vertex) are isomorphic to the ...
- 2,451
-2
votes
0
answers
46
views
Generalization of "Neighbours in a matrix"
Lately, I was doing problems on the book "The Art of Mathematics : Coffee time in Memphis".
One certain problem caught my attention, the problem $21$, Neighbors in a matrix. Basically it ...
4
votes
1
answer
61
views
Minimum cardinality of the set of values for a sequence($a_1,a_2...a_{2025}$) with distinct cyclic ratios
Let $n = 2025$. We are given a sequence of positive integers $a_1, a_2, \dots, a_n$.
Let the cyclic ratios be defined as:
$$r_i = \frac{a_i}{a_{i+1}} \quad \text{for } 1 \le i \le n-1, \quad \text{and}...
4
votes
0
answers
50
views
Optimal signaling to recover an element’s position in a k-set
Given integers $n$ and $k$, Alice is given $k$ numbers $1 \le a_1 < a_2 < \cdots < a_k \le n$. She then writes down a message $x\ (1 \le x \le m)$. Bob is given the message $x$ and one ...
- 595
0
votes
0
answers
37
views
Is Exact Matching with more than two colours NP-hard?
I'm interested in the following problem: given a (multi-)graph with each edge coloured by one of 3 colours, find a perfect matching with exactly k_i edges of colour i in {1,2,3}. I'm also interested ...
- 353
3
votes
0
answers
90
views
Cases $n=7,8$ of a conjecture on semigroups
[Crossposted at mathoverflow and AoPS].
I would like to prove cases $n=7,8$ of this conjecture (general question asked here): given any commutative semigroup $S$ of order $n \ge 1$, there exist $a, b \...
- 2,405
2
votes
0
answers
52
views
Size of family of pairs of edges overlapping at exactly 1 vertex in a non two colorable hypergraph
Show that every n-uniform non 2 colorable hypergraph $H$ contains atleast $\frac{n}{2} {2n-1 \choose n-1}$ unordered pairs of edges each overalapping at exactly 1 vertex. I came across this problem in ...
3
votes
1
answer
73
views
Invariant trees of outer automorphism of free groups
Gaboriau-Jaeger-Levitt-Lustig (Theorem II.1) constructed an invariant $\mathbb{R}$-tree $T$ with $F_n$ action given any outer automorphism of free groups $\Phi\in \mathrm{Out}(F_n)$. They showed that $...
- 925
-1
votes
0
answers
24
views
Graphs where nodes are connected but distant [closed]
Is it possible to make a graph consisting of 2n nodes such that every node is connected to every other node in at least n steps except n of the other nodes?
For example with 1, we make the graph with ...
- 45
3
votes
1
answer
148
views
Maximum number of points having a specific point as their nearest neighbor in $\mathbb{R}^2$ [duplicate]
Problem Statement:
Let $S = \{P_1, P_2, \dots, P_n\}$ be a set of $n$ distinct points in the Euclidean plane ($\mathbb{R}^2$), where $n \ge 10$.
We define a mapping $f: S \to S$ such that for every ...
3
votes
2
answers
148
views
A family of lines with more than four points is 2-colorable
Let $E$ be a finite set of points and $\mathcal{F}$ be a collection of subsets of $E$ (lines) such that
each line has cardinal at least 4
two distinct lines intersects at exactly one point.
Show ...
- 79
1
vote
0
answers
20
views
Formula for number of unlabelled trees of n vertices [closed]
How do we prove that no closed-form expression exists for the number of non-isomorphic unlabeled trees of n vertices? How do we also prove that no closed-form expression can give the degree sequences(...
