Questions tagged [special-graphs]
The special-graphs tag is intended for questions that are related to graphs with special properties, especially for named graphs.
5 questions
0
votes
1
answer
112
views
Degree Distribution of Planar Minimum Spanning Trees
Question:
how are the vertex degrees of MSTs of the corresponding points that are uniformly and independently distributed in a square region of the euclidean plane and the edges being weighted with ...
- 13.2k
1
vote
0
answers
62
views
LP Constraints for Bridgeless Cactus Graphs
When trying to determine the optimal bridgeless spanning cactus graph of a weighted, symmetric graph, I got stuck.
What I do not know how to capture, is
the variable number and sizes of the cycles
...
- 13.2k
2
votes
1
answer
96
views
Maximal Vertex Degree of MSTs in Euclidean Spaces
Are there any Euclidean spaces, in which the maximal vertex degree of MSTs (Minimum Spanning Trees) of a finite set of points and edge weights equal to Euclidean distance, isn't equal to the kissing ...
- 13.2k
2
votes
0
answers
47
views
What are Interesting Questions about Families of Graphs?
In my recreational occupation with the TSP I encountered a family of graphs, which I would like to call "Möbius Sponges" because they generalize the Möbius Ladder graphs in a way, that may provide an ...
- 13.2k
1
vote
1
answer
50
views
Relation of Convex Polygons to Halin Graphs
Can every Halin graph be visualized as the union of a planar, strictly convex polygon with its Voronoi Diagram?
It is true, that every union of a strictly convex planar polygon with its Voronoi ...
- 13.2k